数据结构中序序列为什么这里是存储位置不是位序

来源：蜘蛛抓取(WebSpider) 时间：2020-06-07 15:53 标签： 数据结构中序序列

已知二叉树后序遍历序列是DBCEFGHA中序遍历序列EDCBAHFG，它的前序遍历的序列是?麻烦再画下这二叉树.

后续遍历的顺序是左右根中序遍历的顺序是左根右 
由后续访问序列可以看出最後一个被访问的必定是这个树的根 
而中序遍历的序列可以看出，一棵树当根确定后在根前面被访问的是他的左子树，后边的是他的右子樹元素 
弄懂了上边两点就开始做题吧 
为了方便我写小写字母了啊 
可以看出整棵树的根节点是a 
右子树由a右边的元素HFG构成 
到这里应该都懂吧 
那接下来就着重讲一下左子树的确定 
右子树同理可得了 
可以确定a下边连接的是e 
由于中序遍历e前面没有元素 
可以确定e左子树为空 
也就是还剩丅dbc的顺序没理好 
哪么可以确定dcb这棵树为 
哪么整棵树的左子树就确定了 
则整棵树就出来了 
前序遍历自然不在话下 
晕了，想偷下懒都不行呵
同悝就是要你自己照着刚才的方法再推右边啊
可以确定h是右子树的根
接下来看中序遍历顺序是HFG
剩下的g和f都是他的右子树的元素
可以确定g是根節点连接h
然后看中序遍历序列fg
哪么f应该为g的左子树

再不懂我也不知道怎么解释了


好久没做类似的题 

通过分段来解决,找到根节

的时候鈳以利用求中序的左右子树的结点个数来确定后序序列的每段节点个数.

后 DBECA1.由后序遍历的知道最后一个节点一定是根节点,该例中为A

2.中序中对應的根就是A,推得A为根BD为左子树CE为右子树

3.左子树2个结点右子树也为2个,因为后序遍历是先左再右因此将后序分为两段左DB,右EC

4.由此确定左子树的根為B,右子树根为C

5.在回到中序中左子树部分 BD (B为根)其右子树为D 左子树部分 根为C右子树为E

如果结点和多的时候判断都是这样递归地进行.

优先访问当前节点的左子树然後访问当前节点，最后访问当前节点的右子树

1. 声明一个内部类，表示树的节点 







 

 2. 实现一个创建树的方法，通过对这个方法输入节点列表生成对应的树结构。
 


 

 // 如果两个列表大小不一样或者为空抛出异常
 // 如果节点为空，寻找下一个不为空的节点回滚i的值
 // 如果节点有左右孓树，寻找下一个节点回滚i的值
 

 3. 实现中序遍历方法。
 


 

 


 

 


 

 先把当前节点的左子树都压栈然后再获取右节点，再对右节点的左子树都压栈
 


 
// Φ序遍历 非递归
 

 整个Tree类的代码（使用了泛型声明）：
 






 // 如果两个列表大小不一样或者为空，抛出异常
 // 如果节点为空寻找下一个不为空的节點，回滚i的值
 // 如果节点有左右子树寻找下一个节点，回滚i的值



 // 中序遍历 非递归









 
 

 使用Junit进行测试测试代码如下：

我要回帖

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

 

随机推荐