二叉樹的前序序列和中序序列
- 電腦
- 關注:2.23W次
學數據結構的朋友應該都知道,二叉樹是數據結構比較重要的一個章節,今天我們來搞定 由二叉樹的前序序列和中序序列可唯一的確定一顆二叉樹
例如,前序序列{ABHFDECKG}和中序序列{HBDFAEKCG},構造二叉樹的過程
操作方法
(01)我們先回顧一下,二叉樹的前序、中序和後序前序:VLR中序:LVR後序:LRV
(02)前序序列{ 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,畫出二叉樹
(03)繼續根據 前序:VLR 中序:LVR 的規則拆分左子樹L(HBDF)左子樹的 前序:B H F D 中序 :H B D F ,確認B 為根節點,H為左節點,DF為右節點
(04)繼續根據 前序:VLR 中序:LVR 的規則拆分左子樹 L(HBDF),BH已經確定,下面拆分 右子樹DF根據 前序: F D 中序 : D F ,確認F為根節點,D為左節點,沒有右節點左子樹全部拆分
(05)下面,我們拆分右子樹R(EKCG)右子樹 前序:E C K G; 中序: E K C G我們可以根據前序,確認E為根節點,沒有左節點,只有右節點(KCG)
(06)繼續拆分右子樹右子樹 前序: C K G; 中序: K C G我們可以根據前序,確認C為根節點,左節點K,右節點 G這樣,我們的二叉樹就畫好啦。。
特別提示
前序:VLR 中序:LVR
- 文章版權屬於文章作者所有,轉載請註明 https://miaozhigu.com/sm/diannao/k9kmym.html