[笔记]已知二叉树的两种遍历顺序求第三种遍历顺序 | 祭夜博客
  • 欢迎光临，这个博客颜色有点多
> 猿之力 > C/C++ > [笔记]已知二叉树的两种遍历顺序求第三种遍历顺序

[笔记]已知二叉树的两种遍历顺序求第三种遍历顺序

C/C++ msojocs 5年前 (2019-08-13) 2528次浏览 已收录 1个评论 扫描二维码
文章目录[隐藏]

类型

  1. 已知先序与中序遍历，求后序遍历
  2. 已知中序与后序遍历，求先序遍历
  3. 但是已知先序与后序遍历，不可求得中序
  4. 也就是必须知道中序！
思路类似，都是先求原始二叉树，再求第三者

1.已知先中，求后序

栗子1：

先序：ABCDEFGH

中序：BDCEAFHG

解题

1.因为先序是先访问根节点，所以A为根节点；

2.因为中序是在树的两边中间访问根节点，并且按大致从左往右的顺序，

所以，BDCE分布在根节点A的左子树，FHG分布在根节点A的右子树；

3.BDCE在先序中是先访问B的，所以B是A的左子树部分的根节点；

因为中序访问时根节点B大致在中间，所以DCE就属于B的右子树部分；

4.同理，C是DCE部分的根节点；D是C的左子树部分，E是C的右子树部分；

5.同样的，也可以判断出A的右子树部分FHG的情况。

答案


栗子2：

先序：ABDGHCEFI

中序：GDHBAECIF

答案


2.已知中后，求先序

提示：
后序遍历是最后访问根节点的

栗子

中序：BDCEAFHG

后序：DECBHGFA

答案


 

 

祭夜の咖啡馆 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：[笔记]已知二叉树的两种遍历顺序求第三种遍历顺序
喜欢 (0)赏
[1690127128@qq.com]
分享 (0)
cqcadmin
关于作者：
作者主页 赞助作者

您必须 登录 才能发表评论！

(1)个小伙伴在吐槽
  1. 最讨厌做这种题目了呀
    超人下拉系统2019-08-30 13:58 Windows 7 | Chrome 55.0.2883.87