二叉树的前序序列和中序序列

作者:暴躁小n | 创建时间: 2023-06-01
学数据结构的朋友应该都知道,二叉树是数据结构比较重要的一个章节,今天我们来搞定 由二叉树的前序序列和中序序列可唯一的确定一颗二叉树 例如,前序序列{ABHFDECKG}和中序序列{HBDFAEKCG},构造二叉树的过程...
二叉树的前序序列和中序序列

操作方法

我们先回顾一下,二叉树的前序、中序和后序 前序:VLR 中序:LVR 后序:LRV

前序序列{ A B H F D E C K G} 中序序列{ H B D F A E K C G} 这样我们可以确定,我们的根节点是 A,然后在中序中根据 A的位置,可以确定 L(HBDF)和 R(EKCG) 取出 A,画出二叉树

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

继续根据 前序:VLR  中序:LVR 的规则 拆分左子树  L(HBDF),B\H已经确定,下面拆分 右子树DF 根据 前序: F D   中序 : D F ,确认F为根节点,D为左节点,没有右节点 左子树全部拆分

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

继续拆分右子树 右子树 前序: C K G;  中序:  K C G 我们可以根据前序,确认C为根节点,左节点K,右节点 G 这样,我们的二叉树就画好啦。。

温馨提示

前序:VLR 中序:LVR
点击展开全文

更多推荐