作者：解学武

后序遍历二叉树，指的是从根结点出发，按照以下步骤访问树中的每个结点：

1. 优先进入当前结点的左子树，以同样的步骤遍历左子树中的结点；
2. 如果当前结点没有左子树，则进入它的右子树，以同样的步骤遍历右子树中的结点；
3. 直到当前结点的左子树和右子树都遍历完后，才访问该结点。

以下图所示的二叉树为例： 后序遍历这棵二叉树的过程是：

从根节点 1 出发，进入该结点的左子树；
    进入结点 2 的左子树，遍历左子树中的结点：
        进入结点 4 的左子树，但该结点没有左孩子；
        进入结点 4 的右子树，但该结点没有右子树；
        访问结点 4；
    进入结点 2 的右子树，遍历右子树中的结点：
        进入结点 5 的左子树，但该结点没有左孩子；
        进入结点 5 的右子树，但该结点没有右孩子；
        访问结点 5；
    访问结点 2；
进入结点 1 的右子树，遍历右子树中的结点：
    进入结点 3 的左子树，遍历左子树中的结点：
        进入结点 6 的左子树，但该结点没有左孩子；
        进入结点 6 的右子树，但该结点没有右子树；
        访问结点 6；
    进入结点 3 的右子树，遍历右子树中的结点：
        进入结点 7 的左子树，但该结点没有左孩子；
        进入结点 7 的右子树，但该结点没有右孩子；
        访问结点 7；
    访问结点 3；
访问结点 1。

最终，后序遍历图 1 中的二叉树，访问各个结点的顺序是：

4 5 2 6 7 3 1

递归后序遍历二叉树

后序遍历二叉树，最常用的实现方式就是递归。

对于顺序表存储的二叉树，递归实现后序遍历的 C 语言程序为：

void PostOrderTraverse(BiTree T, int p) {
    if ((p * 2 + 1 < NODENUM) && (T[p * 2 + 1] != 0)) {
        PostOrderTraverse(T, 2 * p + 1);
    }
    if ((p * 2 + 2 < NODENUM) && (T[p * 2 + 2] != 0)) {
        PostOrderTraverse(T, 2 * p + 2);
    }
    printf("%d ", T[p]);
}

对于链表存储的二叉树，递归实现后序遍历的 C 语言程序为：

void PostOrderTraverse(BiTree T) {
    if (T) {
        PostOrderTraverse(T->lchild);//遍历左孩子
        PostOrderTraverse(T->rchild);//遍历右孩子
        printf("%d ", T->data);
    }
}

以上给出的是后序遍历二叉树的 C 语言关键代码，猛击这里获取完整源码。

非递归后序遍历二叉树

递归的底层实现过程是借助栈存储结构完成的，因此我们可以手动模拟一个栈结构，实现二叉树的后序遍历。

后序遍历是在遍历完当前结点的左右孩子之后才访问该结点，所以需要在当前结点进栈时为其配备一个标志位。当遍历该结点的左孩子时，设置当前结点的标志位为 0；当要遍历该结点的右孩子时，设置当前结点的标志位为 1，进栈。

这样当遍历完该结点的左右子树并将其弹栈时，查看该结点标志位的值：如果是 0，表示该结点的右孩子还没有遍历；如果是 1，说明该结点的左右孩子都遍历完成，可以访问此结点。

对于顺序表存储的二叉树，非递归实现后序遍历的 C 语言程序为：

#include <stdio.h>
#define NODENUM 7
#define ElemType int
//自定义 BiTree 类型，表示二叉树
typedef ElemType BiTree[NODENUM];
int top = -1;//表示栈顶
typedef struct SNode {
    int p;   //结点所在顺序表的下标
    int tag; //标记值
}SNode;
//存储二叉树
void InitBiTree(BiTree T) {
    ElemType node;
    int i = 0;
    printf("按照层次从左往右输入树中结点的值，0 表示空结点，# 表示输入结束:");
    while (scanf("%d", &node))
    {
        T[i] = node;
        i++;
    }
}
// 弹栈函数
void pop() {
    if (top == -1) {
        return;
    }
    top--;
}
//入栈
void push(SNode* a, SNode sdata) {
    a[++top] = sdata;
}
void PostOrderTraverse(BiTree Tree) {
    SNode a[20] = {0};//定义一个顺序栈
    int tag; //记录结点的标记位
    SNode sdata;
    int p = 0;
    while (p < NODENUM || top != -1) {
        //压入结点的左子树
        while (p < NODENUM && Tree[p] != 0) {
            sdata.p = p;
            sdata.tag = 0;
            push(a, sdata);
            p = p * 2 + 1;//继续遍历左孩子
        }
        //取栈顶元素
        sdata = a[top];
        pop();
        p = sdata.p;
        tag = sdata.tag;
        //如果tag==0，说明该结点还没有遍历它的右孩子
        if (tag == 0) {
            sdata.p = p;
            sdata.tag = 1;
            push(a,sdata);
            p = p * 2 + 2;//继续遍历右子树
        }
        //如果取出来的栈顶元素的tag==1，说明此结点左右子树都遍历完了，可以访问该结点了
        else
        {
            printf("%d ", Tree[p]);
            p = NODENUM;//重置 p 的值，防止下次进入第一个循环
        }
    }
}

int main() {
    BiTree T = { 0 };
    InitBiTree(T);
    PostOrderTraverse(T);
    return 0;
}

运行结果为：

按照层次从左往右输入树中结点的值，0 表示空结点，# 表示输入结束:1 2 3 4 5 6 7 #
4 5 2 6 7 3 1

对于链表存储的二叉树，非递归实现后序遍历的 C 语言程序为：

#include <stdio.h>
#include <stdlib.h>
#define TElemType int

int top = -1;//表示栈顶

typedef struct BiTNode {
    TElemType data;//数据域
    struct BiTNode* lchild, * rchild;//左右孩子指针
}BiTNode, * BiTree;

//后序遍历非递归算法
typedef struct SNode {
    BiTree p;
    int tag;
}SNode;

void CreateBiTree(BiTree* T) {
    int num;
    scanf("%d", &num);
    //如果输入的值为 0，表示无此结点
    if (num == 0) {
        *T = NULL;
    }
    else
    {
        //创建新结点
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = num;
        CreateBiTree(&((*T)->lchild));//创建该结点的左孩子
        CreateBiTree(&((*T)->rchild));//创建该结点的右孩子
    }
}

//弹栈函数
void pop() {
    if (top == -1) {
        return;
    }
    top--;
}

//入栈
void push(SNode* a, SNode sdata) {
    a[++top] = sdata;
}

//后序遍历二叉树
void PostOrderTraverse(BiTree Tree) {
    SNode a[20];//定义一个顺序栈
    BiTNode* p = NULL;//临时指针
    int tag; //记录结点的标记位
    SNode sdata;
    p = Tree;
    while (p || (top != -1)) {
        while (p) {
            //为该结点入栈做准备
            sdata.p = p;
            sdata.tag = 0;//由于遍历是左孩子，设置标志位为0
            push(a, sdata);//压栈
            p = p->lchild;//以该结点为根结点，遍历左孩子
        }
        sdata = a[top];//取栈顶元素
        pop();//栈顶元素弹栈
        p = sdata.p;
        tag = sdata.tag;
        //如果tag==0，说明该结点还没有遍历它的右孩子
        if (tag == 0) {
            sdata.p = p;
            sdata.tag = 1;
            push(a, sdata);//更改该结点的标志位，重新压栈
            p = p->rchild;//以该结点的右孩子为根结点，重复循环
        }
        //如果取出来的栈顶元素的tag==1，说明此结点左右子树都遍历完了，可以访问该结点了
        else {
            printf("%d ", p->data);
            p = NULL;
        }
    }
}

//后序遍历二叉树，释放树占用的内存
void DestroyBiTree(BiTree T) {
    if (T) {
        DestroyBiTree(T->lchild);//销毁左孩子
        DestroyBiTree(T->rchild);//销毁右孩子
        free(T);//释放结点占用的内存
    }
}

int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    PostOrderTraverse(Tree);
    DestroyBiTree(Tree);
    return 0;
}

运行结果：

1 2 4 0 0 5 0 0 3 6 0 0 7 0 0
4 5 2 6 7 3 1

声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。