6.8.4　中序遍历算法

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所示。