编程论坛 » 数据结构与算法 » 先序、中序、后序遍历的递归算法

srgzyq 发表于 2008-5-14 09:31

先序、中序、后序遍历的递归算法

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define OK 1
#define ERROR 0
#define NULL 0
#define OVERFLOW -2

typedef int Status;
typedef char TElemType;

/*二叉树的二叉链表存储表示*/
typedef struct BiTNode{
        TElemType data;
        struct BiTNode *lchild, *rchild;        //左右孩子指针
}BiTNode, *BiTree;

/*建立二叉链表*/
Status CreateBiTree(BiTree &T){
        //按先序次序输入二叉树中结点值，空格表示空树
        //构造二叉链表表示的二叉树
        char ch;
        scanf("%c",&ch);
       
        //ch=getchar();
        if(ch==' ')
                T=NULL;
               
        else
        {
                if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
                T->data=ch;
                CreateBiTree(T->lchild);
                CreateBiTree(T->rchild);
        }
        return OK;
}

/*打印二叉树的内容*/
Status PrintElement(char ch)
{
        printf("%c",ch);

        return OK;
}

/*先序遍历二叉树，递归算法*/
Status PreOrderTraverse(BiTree T,Status(*PrintElement)(TElemType e))
{
        if(T)
        {
                if(PrintElement(T->data))
                        if(PreOrderTraverse(T->lchild,PrintElement))
                                if(PreOrderTraverse(T->rchild,PrintElement))
                                        return OK;
                return ERROR;
        }
        else return OK;
}
/*中序遍历二叉树，递归算法*/
Status InOrderTraverse(BiTree T,Status(*PrintElement)(TElemType e))
{
        if(T)
        {
                if(InOrderTraverse(T->lchild,PrintElement))
                        if(PrintElement(T->data))
                                if(InOrderTraverse(T->rchild,PrintElement))
                                        return OK;
                return ERROR;
        }
        else return OK;
}

/*后序遍历二叉树，递归算法*/
Status PostOrderTraverse(BiTree T,Status(*PrintElement)(TElemType e))
{
        if(T)
        {
                if(PostOrderTraverse(T->lchild,PrintElement))
                        if(PostOrderTraverse(T->rchild,PrintElement))
                                if(PrintElement(T->data))
                                        return OK;
                return ERROR;
        }
        else return OK;
}


int main()
{        BiTree T;
        printf("请输入二叉树:");
        printf("\n");
        CreateBiTree(T);
       
        printf("先序遍历:");
        printf("\n");
        PreOrderTraverse(T,PrintElement);
       
        printf("\n");
        printf("中序遍历:");
        printf("\n");
        InOrderTraverse(T,PrintElement);
       
        printf("\n");
        printf("后序遍历:");
        printf("\n");
        PostOrderTraverse(T,PrintElement);
        printf("\n");
        return 0;

}

srgzyq 发表于 2008-5-14 09:32

可以输入 ABC##DE#G##F###
进行测试 注"#"为空格

查看完整版本: 先序、中序、后序遍历的递归算法