后序遍历二叉树详解（图文并茂，C语言实现）

后序遍历指首先后序遍历左子树，然后后序遍历右子树，在左子树、右子树为空或已遍历时访问根，即 LRD。若二叉树为空，则什么也不做。

图解后序遍历二叉树的过程

一棵二叉树的后序遍历过程如下：
1) 后序遍历 A 的左子树：


2) 后序遍历 B 的左子树：


3) 后序遍历 D 的左子树，D 的左子树为空，后序遍历 D 的右子树，D 的右子树也为空，访问 D，返回 B：


4) 后序遍历 B 的右子树：


5) 后序遍历 E 的左子树，E 的左子树为空，后序遍历 E 的右子树，E 的右子树也为空，访问 E，此时 B 的左、右子树都已被遍历，访问 B，返回 A：


6) 后序遍历 A 的右子树：


7) 后序遍历 C 的左子树：


8) 后序遍历 F 的左子树，F 的左子树为空，后序遍历 F 的右子树：


9) 后序遍历 G 的左子树，G 的左子树为空，后序遍历 G 的右子树，G 的右子树也为空，访问 G，此时 F 的左、右子树都已被遍历，访问 F，返回 C：


10) 后序遍历 C 的右子树，C 的右子树为空，此时 C 的左、右子树都已被遍历，访问 C，此时 A 的左、右子树都已被遍历，访问 A，遍历结束：


后序遍历序列为 D E B G F C A。

后序遍历的C语言实现

实现后序遍历二叉树的关键代码如下：

void posorder(Btree T) { //后序遍历
    if(T) {
        posorder(T->lchild);
        posorder(T->rchild);
        cout << T->data << " ";
    }
}

实现后序遍历二叉树的完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#define TElemType char
//构造结点的结构体
typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;

// 初始化树的函数
void CreateBiTree(BiTree *T) {
    *T = (BiTNode *)malloc(sizeof(BiTNode)); // 创建根节点A
    (*T)->data = 'A';
    (*T)->lchild = (BiTNode *)malloc(sizeof(BiTNode)); // 创建左子节点B
    (*T)->rchild = (BiTNode *)malloc(sizeof(BiTNode)); // 创建右子节点C
    (*T)->lchild->data = 'B';
    (*T)->lchild->lchild = (BiTNode *)malloc(sizeof(BiTNode)); // 创建B的左子节点D
    (*T)->lchild->rchild = (BiTNode *)malloc(sizeof(BiTNode)); // 创建B的右子节点E
    (*T)->rchild->data = 'C';
    (*T)->rchild->lchild = (BiTNode *)malloc(sizeof(BiTNode)); // 创建C的左子节点F
    (*T)->rchild->rchild = NULL; // C的右子节点为空
    (*T)->lchild->lchild->data = 'D';
    (*T)->lchild->lchild->lchild = NULL;
    (*T)->lchild->lchild->rchild = NULL;
    (*T)->lchild->rchild->data = 'E';
    (*T)->lchild->rchild->lchild = NULL;
    (*T)->lchild->rchild->rchild = NULL;
    (*T)->rchild->lchild->data = 'F';
    (*T)->rchild->lchild->lchild = NULL;
    (*T)->rchild->lchild->rchild = (BiTNode *)malloc(sizeof(BiTNode));// 创建F的右子节点G
    (*T)->rchild->lchild->rchild->data = 'G';
    (*T)->rchild->lchild->rchild->lchild = NULL;
    (*T)->rchild->lchild->rchild->rchild = NULL;
}

//模拟操作结点元素的函数，输出结点本身的数值
void displayElem(BiTNode* elem){
    printf("%c ",elem->data);
}
//后序遍历
void PostOrderTraverse(BiTree T){
    if (T) {
        PostOrderTraverse(T->lchild);//遍历左孩子
        PostOrderTraverse(T->rchild);//遍历右孩子
        displayElem(T);//调用操作结点数据的函数方法
    }
    //如果结点为空，返回上一层
    return;
}
int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("后序遍历: \n");
    PostOrderTraverse(Tree);
}

运行结果为：

后序遍历:
D E B G F C A