数据结构—二叉树后序遍历求逆

一时失言乱红尘 2022-08-22 13:23 132阅读 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')
        {
            switch(ch)
            {
            case '(':
                top++;
                St[top]=p;
                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;
                else
                {
                    switch(k)
                    {
                    case 1:
                        St[top]->lchild=p;
                        break;
                    case 2:
                        St[top]->rchild=p;
                        break;
                    }
                }
            }
            j++;
            ch=str[j];
        }
    }
    
    /*
    将算法中访问节点的操作改为判断该节点是否为叶子节点，若是，输出栈中所有节点值。
    */
    void AllPath(BTNode *b)   
    {
        BTNode *St[MaxSize],*p;
        int flag,i,top=-1;
        if(b!=NULL)
        {
            do
            {
                while(b!=NULL)
                {
                    top++;
                    St[top]=b;
                    b=b->lchild;
                }
                p=NULL;
                flag=1;
                while(top!=-1&&flag)
                {
                    b=St[top];    //取出当前栈顶元素
                    if(b->rchild==p)
                    {
                        if(b->lchild==NULL&&b->rchild==NULL)
                        {
                            for(i=top;i>0;i--)
                                cout<<St[i]->data<<"->";
                            cout<<St[0]->data<<endl;
                        }
                        top--;
                        p=b;
                    }
                    else
                    {
                        b=b->rchild;
                        flag=0;
                    }
                }
            }while(top!=-1);
            cout<<endl;
        }
    }
    int main()
    {
        BTNode *b;
        CreateBTNode(b,"A(B(D(,G)),C(E,F))");
        AllPath(b);
        return 0;
    }

运行结果：

![Center][]

[Center]: /images/20220722/b5ef56e5a21c4363b6afe73b728e90c9.png