数据结构—二叉树的遍历—递归

红太狼 2022-08-22 13:17 141阅读 0赞

/*
    二叉树的遍历。
    */
    #include <iostream>
    #include <malloc.h>
    #define MaxSize 100
    typedef char ElemType;
    using namespace std;
    typedef struct node
    {
        ElemType data;   //数据元素
        struct node *lchild;  //指向左孩子节点
        struct node *rchild;  //指向右孩子节点
    } BTNode;
    
    void CreateBTNode(BTNode *&b,char *str)   //创建二叉树
    {
        BTNode *St[MaxSize],*p;
        int top=-1,k,j=0;
        char ch;
        b=NULL;    //二叉树初始时为空
        ch=str[j];
        while(ch!='\0')    //循环扫描str中的每个字符
        {
            switch(ch)
            {
            case '(':   //开始处理左孩子节点
                top++;
                St[top]=p;
                k=1;   //将(之前的字符进栈，k=1
                break;
            case ')':   //退栈
                top--;
                break;
            case ',':   //开始处理右孩子节点
                k=2;
                break;
            default:
                p=(BTNode *)malloc(sizeof(BTNode));
                p->data=ch;
                p->lchild=p->rchild=NULL;
                if(b==NULL)     //若尚未建立根节点
                    b=p;       //*p为二叉树的根节点
                else            //已建立二叉树根节点
                {
                    switch(k)
                    {
                    case 1:
                        St[top]->lchild=p;
                        break;
                    case 2:
                        St[top]->rchild=p;
                        break;
                    }
                }
            }
            j++;
            ch=str[j];     //循环str中的每个字符
        }
    }
    
    void PreOrder(BTNode *b)  //先序遍历的递归算法
    {
        if(b!=NULL)
        {
            cout<<b->data;
        PreOrder(b->lchild);
        PreOrder(b->rchild);
        }
    }
    
    void InOrder(BTNode *b)   //中序遍历的递归算法
    {
        if(b!=NULL)
        {
            InOrder(b->lchild);
            cout<<b->data;
            InOrder(b->rchild);
        }
    }
    
    void PostOrder(BTNode *b)   //后序遍历的递归算法
    {
        if(b!=NULL)
        {
            PostOrder(b->lchild);
            PostOrder(b->rchild);
            cout<<b->data;
        }
    }
    int main()
    {
        BTNode *b;
        CreateBTNode(b,"A(B(D(,G)),C(E,F))");
        cout<<"先序遍历：";
        PreOrder(b);
        cout<<endl;
        cout<<"中序遍历：";
        InOrder(b);
        cout<<endl;
        cout<<"后序遍历：";
        PostOrder(b);
        cout<<endl;
        return 0;
    }

运行结果：

![Center][]

[Center]: /images/20220722/7d4d5e9a67a64fb699071003b6b2fb36.png