6.8.4 中序遍历算法

那么二叉树的中序遍历算法是如何呢？哈哈，别以为很复杂，它和前序遍历算法仅仅只是代码的顺序上的差异。

/* 二叉树的中序遍历递归算法 */
void InOrderTraverse(BiTree T){
    if (T == NULL)
        return;
    /* 中序遍历左子树 */
    InOrderTraverse(T->lchild);
    /* 显示结点数据，可以更改为其他对结点操作 */
    printf("%c", T->data);
    /* 最后中序遍历右子树 */
    InOrderTraverse(T->rchild);
}

换句话说，它等于是把调用左孩子的递归函数提前了，就这么简单。我们来看看当调用InOrder-Traverse(T)函数时，程序是如何运行的。

1. 调用InOrderTraverse(T)，T的根结点不为null，于是调用InOrderTraverse(T->lchild);访问结点B。当前指针不为null，继续调用InOrderTraverse(T->lchild);访问结点D。不为null，继续调用InOrderTraverse(T->lchild);访问结点H。继续调用InOrderTraverse(T->lchild);访问结点H的左孩子，发现当前指针为null，于是返回。打印当前结点H，如图6-8-14所示。

1. 然后调用InOrderTraverse(T->rchild);访问结点H的右孩子K，因结点K无左孩子，所以打印K，如图6-8-15所示。

1. 因为结点K没有右孩子，所以返回。打印结点H函数执行完毕，返回。打印字母D，如图6-8-16所示。

1. 结点D无右孩子，此函数执行完毕，返回。打印字母B，如图6-8-17 所示。

1. 调用InOrderTraverse(T->rchild);访问结点B的右孩子E，因结点E无左孩子，所以打印E，如图6-8-18所示。

1. 结点E无右孩子，返回。结点B的递归函数执行完毕，返回到了最初我们调用In-OrderTraverse的地方，打印字母A，如图6-8-19所示。

1. 再调用InOrderTraverse(T->rchild);访问结点A的右孩子C，再递归访问结点C的左孩子F，结点F的左孩子I。因为I无左孩子，打印I，之后分别打印F、C、G、J。步骤省略。

综上，中序遍历这棵二叉树的节点顺序是：HKDBEAIFCGJ。