【数据结构】二叉树的后序遍历

傷城~ 2022-09-30 13:59 135阅读 0赞

后序遍历的递归实现与先序和中序遍历类似，而非递归实现较为复杂，下面会进行详细说明。  
![这里写图片描述][SouthEast]  
如图二叉树，其后序遍历结果为：8 4 5 2 9 10 6 7 3 1

`递归实现`

void PostOrderTraversal(BinTree BT)
    {
        if(BT){
            PostOrderTraversal(BT->Left);
            PostOrderTraversal(BT->Right);
            printf("%d ", BT->Date);
        }
    }

`非递归实现`  
后序遍历的非递归实现较为复杂，这是因为后序遍历需要保证访问一个结点之前先访问其左孩子和右孩子，这为流程控制带来了难题。下面提供两种解决思路：

**思路一**  
当我们判断一个结点能否访问时：1.如果该结点是一个叶子结点（即它的左孩子和右孩子为空），则可以进行访问。 2.如果在访问该结点之前已经访问过了它的左孩子和右孩子（即访问的前一个结点是它的右孩子或访问的前一个结点是它的左孩子且它的右孩子为空），则可以访问。下面给出代码：

void PostOrderTraversal2(BinTree BT)
    {
        BinTree T,Pre;
        Stack S;
        S = CreateStack();
        T = BT;
        Pre = NULL;
        while(T || !IsEmpty(S)){
            while(T){
                Push(S,T);
                T = T->Left;
            }
            if(! IsEmpty(S)){
                T = Pop(S);
                if((T->Left == NULL && T->Right == NULL) || (Pre && (Pre == T->Right)) || (Pre && Pre == T->Left && !T->Right)){
                    printf("%d ", T->Date);
                    Pre = T;
                    T = NULL;
                }
                else{
                    Push(S,T);
                    T = T->Right;
                }
            }
        }
    }

**思路二**  
后序遍历时，我们会沿根节点的左子树深入，每遇到一个结点就将其入栈。无法沿左分支深入时，就将栈顶结点弹出，然后将其二次入栈，之后从该结点的右子树继续深入，与之前一样每遇到一个结点就入栈，无法再深入时则将栈顶结点弹出，当一个结点被二次弹出时则该结点可被访问。所以我们可以牺牲一些空间来记录结点是第几次被弹出。故我们对树的结构作如下修改：

typedef struct TreeNode * BinTree;
    struct TreeNode{
        int Date;
        int PopNum; //记录结点的出栈次数,创建结点时初始化为0
        struct TreeNode *Left;
        struct TreeNode *Right;
    };

遍历代码如下

void PostOrderTraversal3(BinTree BT)
    {
        BinTree T,Pre;
        Stack S;
        S = CreateStack();
        T = BT;
        while(T || !IsEmpty(S)){
            while(T){
                Push(S,T);
                T = T->Left;
            }
            if(! IsEmpty(S)){
                T = Pop(S);
                T->PopNum += 1;
                if(T->PopNum > 1){
                    printf("%d ", T->Date);
                    T = NULL;
                }
                else{
                    Push(S,T);
                    T = T->Right;
                }
            }
        }
    }

[SouthEast]: /images/20220705/68816685a4a4437cb9f95e60590e905f.png