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

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

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

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

在理解本章后，还可查看：

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

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

代码如下：

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

递归执行过程图解：

原始二叉树：

1. 第一步调用InorderTraversal,由于根结点非空，开始执行InorderTraversal（BT->Left）,由于，BT->Left 不为空，开始第二步调用（此时处于结点B位置，但并未打印），开始执行InorderTraversal（BT->Left），开始第三步调用（此时处于结点D位置，但并未打印），开始执行InorderTraversal（BT->Left），开始第四步调用（此时处于结点H位置，但并未打印），开始执行InorderTraversal（BT->Left），此时BT->Left为空，立刻返回，第四步接着执行打印语句，打印结点H，结点H遍历完成。（图中序号代表调用的步数）

2.第四步打印语句执行完毕后，开始执行InorderTraversal（BT->Right），BT->Right 为空，立刻返回，第四步执行完毕，返回至第三步，第三步开始执行打印结点D，结点D遍历完成。

3.第三步执行完打印语句后，开始执行InorderTraversal（BT->Right），由于BT->Right 为空，立刻返回，第三步执行完毕，返回至第二步，开始执行打印结点B，结点B遍历完成。

4.第二步完成打印后开始执行 InorderTraversal（BT->Right），BT->Right 不为空，开始执行第三步调用（此时在结点E位置处，但并未打印），开始执行InorderTraversal（BT->Left），由于BT->Left 为空，立刻返回，开始执行打印结点E，结点E遍历完成。

5.第三步执行完打印后，开始执行 InorderTraversal（BT->Right），由于非空，开始第四步调用（此时在结点 I 位置处，但并未打印），开始执行InorderTraversal（BT->Left），为空，立刻返回，开始执行打印结点 I ，结点 I 遍历完成。

6.第四步执行完打印后，开始执行 InorderTraversal（BT->Right），非空，立刻返回，第四步执行完毕，返回至第三步，此前第三步已完成执行InorderTraversal（BT->Right），所以第三步执行完毕，返回至第二步，因为从右孩子返回，第二步也执行完毕，返回至第一步，从左孩子返回，开始打印结点A,结点A遍历完成。

7.第一步执行完打印后，开始执行InorderTraversal（BT->Right），不为空，开始执行第二步调用（此时在结点C位置，但并未打印），开始执行InorderTraversal（BT->Left），不为空，开始第三步调用（此时在F位置，但并未打印），开始执行InorderTraversal（BT->Left），为空，立刻返回，开始打印结点F，结点F遍历完成。

8.第三步打印完后开始执行InorderTraversal（BT->Right），为空，立刻返回，第三步执行完毕，从左孩子返回，开始打印结点C，结点C遍历完成。

9.第二步打印完后，开始执行InorderTraversal（BT->Right），不为空，开始第三步调用（此时在结点G位置，但并未打印），执行InorderTraversal（BT->Left），为空，立刻返回，从左孩子返回，执行打印结点G，结点G遍历完成。

10.第三步打印完后，开始执行InorderTraversal（BT->Right），非空，开始第四步调用（此时在结点J位置，但并未打印），执行InorderTraversal（BT->Left），为空，立刻返回，从左孩子返回，执行打印结点J，结点J遍历完成。

11.第四步打印完后，开始执行InorderTraversal（BT->Right），为空，立刻返回，第四步执行完毕，返回至第三步，从右孩子返回，第三步执行完毕，返回至第二步，从右孩子返回，第二步执行完毕，返回至第一步，从右孩子返回，第一步结束，整个递归过程完成。

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

感悟：

1.中序遍历不像前序遍历一样调用到哪里就打印哪里，它要一直往左调用，从左孩子返回就打印，从右孩子返回就结束该步，返回至上一步，一直到第一步执行完毕。

2.可以这样理解，从左子树为空返回的先打印，左子树执行完毕返回后打印，右子树为空就一直向上返回。

3.在理解了这种遍历顺序后，就很好理解如何用栈去实现了，栈中保留自己和自己的右孩子都未访问过的元素，正好与从左孩子返回就打印，右孩子返回就执行完毕的递归原理相对应。

此章结束。