如给定一棵二叉树的先序序列和中序序列如下：
先序序列：ABDEHIJKCFG
中序序列：DBHEJIKAFEG
如何建立唯一确定的二叉树呢？
思路和方法：
通过先序序列找到根结点和末尾元素，因为先序和中序最后遍历的都是右子树,所以末尾相同元素即为根节点的右子树，不断对比，每找到一棵子树的根结点就用斜线将其左右与其他元素断开分成一颗颗子树。
步骤如下：
先序序列：A B D E H I J K C F G
中序序列：D B H E J I K A F C G
- 在先序中找到根结点A，对应在中序中将A的左右断开
先序：A B D E H I J K C F G
中序：D B H E J I K A F C G
- 对比先序和中序的末尾，找到相同的字母即为根节点的右子树
这里C F G即是构成根结点右子树
- B为A的子树，也即A子树的根结点,B两边断开后发现D为左子树，E为右子树
中序中H比E先遍历，说明H为E的左子树，E为子树结点
- H I 为E的左右孩子，根据中序遍历知道，J在I前面遍历，说明J为I的左孩子，I为根结点
最终结果：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/150463.html
