二叉树中序遍历

二叉树中序遍历

所谓二叉树遍历是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。

二叉树中序遍历的算法实现
　　
用二叉链表做为存储结构，中序遍历算法可描述为： 　　

void InOrder(BinTree T) 　　{ //算法里①~⑥是为了说明执行过程加入的标号 　　
① if(T) { // 如果二叉树非空 　　
② InOrder(T->lchild)； 　　
③ printf("%c"，T->data)； // 访问结点 　　
④ InOrder(T->rchild); 　　
⑤ } 　　
⑥ } // InOrder

二叉树中序遍历的原理

对一棵二叉树实施任何操作的前提是，在所选择的存储结构基础上，建立一棵给定的二叉树。其实，模仿二叉树遍历的递归算法可以非常方便的生成任意给定的二叉树。下面的算法给出了采用前序遍历顺序建立一棵给定二叉树的过程。由于一棵非空二叉树的前序遍历序列中，第一个节点一定是该二叉树的根节点，接下来应该是该二叉树左子树中所有节点前序遍历的结果，然后是该二叉树右子树中所有节点前序遍历的结果。因此，按前序遍历顺序建立二叉树时，应该将第一个输入的节点作为二叉树的根节点，后继输入的节点序列是二叉树左子树前序遍历的结果，由它们生成二叉树的左子树；再接下来输入的节点序列为二叉树右子树前序遍历的结果，应该由它们生成二叉树的右子树，而又由二叉树左子树前序遍历的结果生成二叉树左子树和由二叉树右子树前序遍历的结果生成二叉树的右子树的过程均与由整棵二叉树的前序遍历结果生成该二叉树的过程完全相同，只有所处理的对象范围不同，于是完全可以使用递归方法加以实现。

二叉树先序遍历的思路

因为是先序遍历所以是遵循先访问根节点，然后访问根节点的左子树，最后访问跟节点的右子树的规律。因此建立一棵二叉树，如果二叉树非空，访问完二叉树的根节点值后，进入此二叉树的左子树，此时要将此二叉树保存起来，以便访问完其左子树后，进入其右子树的访问，所以在二叉树设置一个回溯点，并将该回溯点进栈保存。在整个二叉树前序遍历的过程中，程序要做的工作始终分成两个部分：当前正在处理的树（子树）和保存在栈中待处理的部分（注：当栈元素位于栈顶即将出栈时，意味其根结点和左子树已访问完成，出栈后应该进入其右子树的访问），只有这两部分的工作均完成后，程序方能结束。

二叉树中序遍历的思路

按照二叉树中序遍历的定义，无论是访问整棵树还是其子树，均应该遵循先访问根结点的左子树，然后访问根结点，最后访问根结点的右子树的规律。因此对于一棵树t，如果t非空，首先应该进入t的左子树访问，此时由于t的根结点及右子树尚未访问，因此必须将t保存起来，放入栈中，以便访问完其左子树后从栈中取出t，进行其根结点及右子树的访问，在整个二叉树中序遍历的过程中，程序要做的工作始终分为两个部分：当前正在处理的树（子树）和保存在栈中待处理的部分（注：当栈中元素位于栈顶即将出栈时，意味着其左子树已访问完，出栈后应该立即访问其根结点，再进入其右子树的访问），只有这两部分的工作均完成后，程序方能结束。根据以上分析，得到二叉树中序遍历的非递归算法，在算法实现时，用了链式存储结构。