数据结构中序遍历，中序遍历如果运算级相同该怎么画二叉树？

来源：蜘蛛抓取(WebSpider) 时间：2018-11-01 14:17 标签： 数据结构中序遍历
数据结构已知一棵二叉树的前序遍历的结果序列是ABCDEFGHIJ,中序遍历的结果是... 数据结构 已知一棵二叉树的前序遍历的结果序列是ABCDEFGHIJ,中序遍历的结果是

可选中1个或多个下面的关键词搜索相关资料。也可直接点“搜索资料”搜索整个问题

二叉树遍历时，只有知道前序遍历和中序遍历（后序遍历和中序遍历）才能唯一確定这颗树所以你的答案应该是多种。

如果仅有“已知一棵二叉树的前序遍历的结果序列是ABCDEFGHIJ”,则中序遍历的结果是不能确定的

最近看了一下大学的数据结构?学到了以前没学到的东西看到了二叉树那一块，感觉二叉树是个很重要的东西就看了一下底层是怎么实现的，虽然能看懂书上用c语言寫的伪代码但是不能运行，身为一个Java程序员既然别人能用其他的语言能实现，自己也去试着写了一下

首先给出二叉树的节点代码

然後模拟一个栈的代码，会在后面非递归的时候用到

由于只是去遍历所有节点没有考虑性能上的问题，只是让大家了解思路底层用ArrayList去实現栈功能

* 从栈顶pop出一个节点并得到这个节点 * 判断栈里是否还有数据 * 查看当前栈顶的元素

先看下先序遍历的流程图，接下来的代码也会根据此图是遍历


先序遍历顾名思义就是先会遍历根节点->左孩子->右孩子。遍历是从根节点开始遇到每个节点时，其遍历过程为：

先序遍历递歸实现代码：

先序遍历非递归实现代码

中序遍历是指对树中任一节点的访问是在遍历完其左子树后进行的访问此结点后再对其右子树遍曆。遍历从根节点开始遇到每个结点时，其遍历过程为：

中序遍历递归实现代码：

中序遍历非递归实现代码：

在沿左子树深入时进入┅个结点就将其压人堆栈。若是先序遍历则在入栈之前访问之；
当沿左分支深人不下去时，则返回即从堆栈中弹出前面压人的结点；若为中序遍历，则此时访问
该结点然后从该结点的右子树继续深入；若为后序遍历，则将此结点二次入栈然后从该结点的
右子树继续罙入，与前面类同仍为进入一个结点入栈一个结点，深入不下去再返回直到第二次
从栈里弹出该结点，才访问之
因此，按照上述描述的过程使用堆栈可以直接实现相应的非递归算法。先序和中序算法相
对间果些而后序遍历因为需要两次将一个结点人栈，情况稍复雜些下面只以中序遍所头份
介绍二叉树遍历的非递归算法。
在按中序遍历二叉树时遇到一个结点，就把它入栈并去遍历它的左子树，当左子树遍历结束后从栈顶弹出这个结点并访问它，然后按其右指针再去中序遍历该结点的右子树

后序遍历是指对树中任一节点的訪问是在遍历完其左、右子树后进行的。遍历从根节点开始遇到每个结点时，其遍历过程为：

后序遍历递归实现代码：

后序遍历非递归實现代码：

第一种思路：对于任一结点P将其入栈，然后沿其左子树一直往下搜索直到搜索到没有左孩子的结点，此时该结点出现在栈頂但是此时不能将其出栈并访问，因此其右孩子还为被访问所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩孓时该结点又出现在栈顶，此时可以将其出栈并访问这样就保证了正确的访问顺序。可以看出在这个过程中，每个结点都两次出现茬栈顶只有在第二次出现在栈顶时，才能访问它因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。

第二种思路：对于任┅节点将其左子树入栈，直到左子树为空查看当前栈顶得元素是否有右子树或者当前右子树不等于前一访问节点，如有重复之前将其左子树入栈，没有访问当前节点，并把此节点出栈并把当前节点作为访问过的节点。

层序遍历用到了队列Java中有现成的队列，所以僦选择了链表式的队列

先写到这吧，等学到了再更新

二叉树的遍历本质上其实就是入棧出栈的问题递归算法简单且容易理解，但是效率始终是个问题非递归算法可以清楚的知道每步实现的细节，但是乍一看不想递归算法那么好理解各有各的好处吧。接下来根据下图讲讲树的遍历

1、先序遍历：先序遍历是先输出根节点，再输出左子树最后输出右子樹。上图的先序遍历结果就是：ABCDEF

 2、中序遍历：中序遍历是先输出左子树再输出根节点，最后输出右子树上图的中序遍历结果就是：CBDAEF

3、後序遍历：后序遍历是先输出左子树，再输出右子树最后输出根节点。上图的后序遍历结果就是：CDBFEA

其中后序遍历的非递归算法是最复雜的，我用了一个标识符isOut来表明是否需要弹出打印因为只有当节点的左右子树都打印后该节点 才能弹出栈打印，所以标识isOut为1时打印isOut初始值为0，这主要是为了处理非叶子节点由后序遍历的原理决定，左右子树都被打印该节点才能打印所以该节点肯定会被访问2次，第一佽的时候不要打印第二次打印完右子树的时候打印。叶子节点打印完后将isOut置为1（纯粹是自己想的，应该还有逻辑更简单的算法）

C++中可鉯使用类模板从而使节点值的类型可以不止限定在整型：

我要回帖

更多关于 数据结构中序遍历 的文章

 

随机推荐