图解树的后序遍历递归执行过程

本章建立在以下章节的基础上：

C数据结构与算法-基础整理-树-02：二叉树的建立及四种遍历方式

C数据结构与算法-基础整理-树-03：图解-通过前序遍历对递归执行原理的深入理解

C数据结构与算法-基础整理-树-04：图解-树的中序遍历

后序遍历函数递归执行过程图解

代码如下：

//后序遍历，递归实现
void PostorderTraversal(BinTree BT)
{
    if (BT == NULL) return;
    PostorderTraversal(BT->Left);
    PostorderTraversal(BT->Right);
    printf(" %c", BT->data);
    return;
}

递归执行过程图解：

原始二叉树：

1.第一步调用PostorderTraversal，执行PostorderTraversal（BT->Left），不为空，开始第二步调用（此时在B位置，但并未打印），开始执行PostorderTraversal（BT->Left），不为空，开始第三步调用（此时在D位置，但并未打印），开始执行PostorderTraversal（BT->Left），不为空，开始第四步调用（此时在H位置，但并未打印），开始执行PostorderTraversal（BT->Left），为空，立即返回，开始执行PostorderTraversal（BT->Right），为空，立刻返回，开始执行打印H结点，结点H遍历完成。

2.第四步打印结点后，执行完毕，返回第三步，此时第三步执行PostorderTraversal（BT->Right），由于为空，立即返回，右孩子返回，开始执行打印结点D，结点D遍历完成。

3.第三步打印完成后，执行完毕，返回至第二步，开始执行PostorderTraversal（BT->Right），非空，开始第三步调用（此时在E位置，但并未打印），执行PostorderTraversal（BT->Left），非空，立即返回，开始执行PostorderTraversal（BT->Right），非空，执行第四步调用（此时在 I 位置，但并未打印），执行ostorderTraversal（BT->Left），为空，立即返回，开始执行PostorderTraversal（BT->Right），为空，立即返回，开始执行打印节点 I  ，结点 I 遍历完成。

4.第四步打印完成后，返回第三步，右孩子返回，开始执行打印结点E，结点E遍历完成。

5.第三步打印完成后，返回至第二步，右孩子返回，打印结点B，结点B遍历完成。

6.第二步打印完成后，返回至第一步，开始执行PostorderTraversal（BT->Right），非空，开始第二步调用（此时在C位置，但并未打印），执行PostorderTraversal（BT->Left），非空，开始第三步调用（此时在F位置，但并未打印），开始执行PostorderTraversal（BT->Left），为空，立即返回，开始执行PostorderTraversal（BT->Right），为空，立即返回右孩子返回，开始执行打印结点F，结点F遍历完成。

7.第三步打印结点后，返回至第二步，左孩子返回，开始访问右孩子，开始执行PostorderTraversal（BT->Right），非空，开始第三步调用（此时在G位置，但并未打印），开始执行PostorderTraversal（BT->Left），为空，返回，开始执行PostorderTraversal（BT->Right），非空，开始第四步调用（此时在J位置，但并未打印），执行PostorderTraversal（BT->Left），为空，返回，开始执行PostorderTraversal（BT->Right），为空，返回，右孩子返回，开始打印结点J，结点J遍历完成。

8.第四步打印完成后，返回至第三步，右孩子返回，执行打印结点G，结点G遍历完成。

9.第三步打印完后，返回至第二步，右孩子返回，开始打印结点C，结点C遍历完成。

10.第二步打印完后，返回至第一步，右孩子返回，打印结点A，第一步执行完毕，递归过程结束。

遍历顺序：H->D->I->E->B->F->J->G->C->A

感悟：

1.第一次调用访问左孩子，从左孩子返回接着访问右孩子，从右孩子返回就打印自身，打印完后就返回。

2.与栈来实现后序遍历密不可分，与该节点第几次访问离不开关系，第一次访问就继续访问左孩子，第二次访问说明是从左孩子返回，那就接着访问右孩子，第三次访问说明是从右孩子返回，访问自身。

3.后序遍历实际上就是把孩子全部遍历完了再去遍历父结点。

此章结束。