【大话数据结构C语言】30 二叉树中序遍历算法

我的首发平台是公众号【CodeAllen】，学习交流QQ群：736386324

中序遍历的代码

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

看代码可以知道，对比先序遍历，等于是把调用左孩子的递归函数提前了

二叉树中序遍历的实现思想是：

1. 访问当前节点的左子树；
2. 访问根节点；
3. 访问当前节点的右子树；

以上图为例，采用中序遍历的思想遍历该二叉树的过程为：

1. 访问该二叉树的根节点，找到 1；
2. 遍历节点 1 的左子树，找到节点 2；
3. 遍历节点 2 的左子树，找到节点 4；
4. 由于节点 4 无左孩子，因此找到节点 4，并遍历节点 4 的右子树；
5. 由于节点 4 无右子树，因此节点 2 的左子树遍历完成，访问节点 2；
6. 遍历节点 2 的右子树，找到节点 5；
7. 由于节点 5 无左子树，因此访问节点 5 ，又因为节点 5 没有右子树，因此节点 1 的左子树遍历完成，访问节点 1 ，并遍历节点 1 的右子树，找到节点 3；
8. 遍历节点 3 的左子树，找到节点 6；
9. 由于节点 6 无左子树，因此访问节点 6，又因为该节点无右子树，因此节点 3 的左子树遍历完成，开始访问节点 3 ，并遍历节点 3 的右子树，找到节点 7；
10. 由于节点 7 无左子树，因此访问节点 7，又因为该节点无右子树，因此节点 1 的右子树遍历完成，即整棵树遍历完成；

图中二叉树采用中序遍历得到的序列为：4 2 5 1 6 3 7