已知数的前序遍历、中序遍历结果,重建二叉树

先回顾一下二叉树的前序、中序和后序:


二叉树

前序:VLR
中序:LVR
后序:LRV
假设前序、中序遍历结果如下,开始重建二叉树:
前序序列:[ ABHFDECKG ]
中序序列:[ HBDFAEKCG ]

1、可以确定根节点是A,然后在中序中根据 A 的位置,可以确定 L(HBDF)和 R(EKCG)。取出 A,画出二叉树

重建二叉树-1

2、继续根据前序:VLR,中序:LVR 的规则拆分左子树 L(HBDF)。
左子树的前序:B H F D 中序 :H B D F ,确认B 为根节点,H为左节点,DF为右节点
重建二叉树-2

3、下面,我们拆分右子树R(EKCG)
右子树 前序:E C K G; 中序: E K C G
我们可以根据前序,确认E为根节点,没有左节点,只有右节点(KCG)
重建二叉树-3

4、继续拆分右子树
右子树前序: C K G; 中序: K C G
我们可以根据前序,确认C为根节点,左节点K,右节点 G
到此二叉树重建完成。
重建二叉树-4

(例子参考自百度经验)

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容