数据结构—二叉树遍历—非递归算法

谁践踏了优雅 2022-08-22 13:22 190阅读 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];
        }
    }
    
    /*
    先访问根节点，再访问左子树，最后访问右子树。
         先将根节点进栈，在栈不空时循环：
             出栈p,访问*p节点；
             若其右孩子节点不空将右孩子节点进栈；
             若其左孩子节点不空将左孩子节点进栈。
    */
    void PreOrder1(BTNode *b)   //先序非递归遍历算法
    {
        BTNode *St[MaxSize],*p;
        int top=-1;            //根节点进栈
        if(b!=NULL)
        {
            top++;
            St[top]=b;
            while(top>-1)    //栈不为空时进栈
            {
                p=St[top];    //退栈并访问该节点
                top--;
                cout<<p->data;
                if(p->rchild!=NULL)  //右孩子节点进栈
                {
                    top++;
                    St[top]=p->rchild;
                }
                if(p->lchild!=NULL)   //左孩子节点进栈
                {
                    top++;
                    St[top]=p->lchild;
                }
            }
            cout<<endl;
        }
    }
    
    /*
    用指针指向当前要处理的节点。先扫描（并非访问）根节点的所有左节点，并将它们一一进栈，
    当无左节点时表示栈顶节点无左子树，然后出栈这个节点，并访问它，将p指向刚出栈节点的右孩子，
    对右节点进行同样的处理。
    */
    void InOrder(BTNode *b)   //中序遍历非递归算法
    {
        BTNode *St[MaxSize],*p;
        int top=-1;
        if(b!=NULL)
        {
            p=b;
            while(top>-1||p!=NULL)   //处理*b节点的左子树
            {
                while(p!=NULL)     //扫描*p的所有左节点并进栈
                {
                    top++;
                    St[top]=p;
                    p=p->lchild;
                }
                //执行到此处时，栈顶元素没有左孩子或左子树均已访问过
                if(top>-1)
                {
                    p=St[top];   //出栈*p节点
                    top--;
                    cout<<p->data;   //访问之
                    p=p->rchild;    //转向处理*p的右孩子节点
                }
            }
            cout<<endl;
        }
    }
    
    /*
    后序遍历中，第一个访问的节点是二叉树的最左下节点。
    采用一个栈保存需要返回的节点指针，先扫描根节点的所有左孩子节点并一一进栈，
    出栈一个节点*b作为当前节点，然后扫描该节点的右子树。当一个节点的左右孩子节点均
    访问后再访问该节点，如此重复操作，直到栈空为止。
    */
    void PostOrder(BTNode *b)   //后序遍历的非递归算法
    {
        BTNode *St[MaxSize],*p;
        int top=-1,flag;
        if(b!=NULL)
        {
            do
            {
                while(b!=NULL)     //扫描*p的所有左节点并进栈
                {
                    top++;
                    St[top]=b;
                    b=b->lchild;
                }
                //执行到此处时，栈顶元素没有左孩子或者左子树均已访问过
                p=NULL;        //p指向栈顶节点的前一个已访问过的节点
                flag=1;        //表示*b的左孩子已访问或为空
                while(top!=-1&&flag)
                {
                    b=St[top];    //取出当前栈顶元素
                    if(b->rchild==p)
                    /*
                    若*p=NULL，表示b的右孩子不存在，而其左子树不存在或已访问，可以访问*b；
                    若*p!=NULL，表示b的右子树已访问，可以访问*b。
                    */
                    {
                        cout<<b->data;
                        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))");
        cout<<"先序遍历：";
        PreOrder1(b);
        cout<<"中序遍历：";
        InOrder(b);
        cout<<"后序遍历：";
        PostOrder(b);
        return 0;
    }

运行结果：

![Center][]

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