某二叉樹的前序遍歷是abdgcefh,中序遍歷是dgbaechf,則起後序遍歷的結點訪問順序是什麼,為什麼

2021-06-13 06:38:06 字數 2864 閱讀 4340

1樓:匿名使用者

不太記得了,應該是

g d b a e h f c

二叉樹的3中遍歷,知道任何其中2種,就可以建立這個二叉樹。

自然就可以得到第3中的遍歷了。

具體方法可以翻書或網上查詢相關資料。

2樓:匿名使用者

前序是"根左右",由此可判斷a為根節點,再看中序:由於a為根,所以在中序中根據"左根右"原則a前的即為a的左子樹(dgb),右邊的即為右子樹(echf).再看左子樹:

由前序知b為左子樹的根節點,結合中序中dgb知,下級根節點只能為d,而g為最終d的右子樹,即左面的情況為(自下而上)g(右節)-d(根)-b(根)-a(根),這是用排除法得出的.再看右子樹:由相同的方法(根左右)知,右子樹的根為c,前序中為ce,中序為ec很明顯知e為c的左子樹而fh為c的右子樹,同樣根據fh與hf在前序和中序的情況可知,f為根而h為左子樹,即右子樹的情況為(自下而上):

h(左)-f(右根)-e(左根)-c(根)-a(總根).你要在題目中總結經驗和方法,找到這個規律就很簡單了.後序的正確順序應該是(左右根):

gdbhefca明白?行的話幫分.謝謝!!!

3樓:匿名使用者

gdbehfca

-----a

----/-\

---b---c

--/---/-\

-d---e---f

--\-----/

---g---h

若某二叉樹的前序遍歷訪問順序是abdgcefh,中序遍歷訪問順序是dgbaechf,則其後續遍歷的結點訪問順序是?

4樓:匿名使用者

嗯,你第一步的劃分是正確的

a為根,dgb為左子樹,echf為右子樹

接下來看左子樹的前序版遍歷為bdg

b首先被訪問

可以權知道b為左子樹的根,與a相連

再看左子樹的中序遍歷dgb

d和g都在b之前就被訪問

所以b和g應該在b的左子樹上

形狀如下

---a

--/--b

-/dg

而dg的確定再根據前序遍歷

d先被訪問

則d為根

再看中序遍歷也是d先被訪問

可以確定g為d的右子樹

左邊就可以確定出來了

如果上面看懂了

右邊就很簡單,一樣的道理

前序遍歷cefh

確定c為右子樹的根

再看中序遍歷echf

e為c的左子樹,hf為c的右子樹

hf的確定在看前序遍歷f先被訪問

f為根中序遍歷h先被訪問

h為f的左子樹

整棵樹就出來了

如下圖在做後序就是小菜一碟了

5樓:

依據前序抄遍歷的順序,得出a為根節bai點通過中序遍歷的順du

序確定a的左右子樹zhi

分別為bdg和cefh

再依次通過前序遍歷的順序和中

dao序遍歷的順序確定各子樹的分支,得原二叉樹為a/ \

b c

/ / \

d e f

\ /

g h

則其後序遍歷為gdbehfca選a

6樓:匿名使用者

給你個程式吧

知道 前序遍歷 和 中序遍歷 求 後續遍歷。

#include

using namespace std;

char a[20],b[20];

void work(char a,char b,int l)關鍵就是找到每專顆子樹的根節點屬,遞迴。

7樓:匿名使用者

做這種bai題目最好畫出圖

du形。

其實這題你把圖zhi畫出來就很容dao易懂了,這是根據前序,內中序遍容歷得出的圖。

a/ \

b c

/ / \

d e f/g

某二叉樹的前序遍歷節點訪問順序是abdgcefh 中序遍歷節點訪問順序是dgbaechf 則其後序遍歷的節點訪問順序

8樓:oo灰原oo哀

依據前序遍

bai歷的順序,得du

出a為根節點

通過中序zhi遍歷的順序確定a的左右子dao樹分別版為bdg和cefh

再依次通過前權序遍歷的順序和中序遍歷的順序確定各子樹的分支,得原二叉樹為

a/ \

b c

/ / \

d e f

\ /

g h

則其後序遍歷為gdbehfca選a

某二叉樹前序遍歷結點訪問順序abdgcefh,終序遍歷的順序為dgbaechf,則後序遍歷的訪問順序是什麼啊?

9樓:匿名使用者

----------- a------------ b-------c----------- d----- e----f

----------- ----g h----

後續遍歷: gdbehfca

思路:根據前

序確定a是根,根據中序確定dgb是左節點,echf是右節點。

根據前序確定左邊第二級b是根,根據中序確定dg是左節點;右邊同理。

根據前序確定左邊第**d是根,根據中序確定g是右節點;其他同理。

某二叉樹的先序遍歷序列是abdgcefh,中序遍歷序列是dg

分析過程 以下面的例題為例進行講解 已知一棵二叉樹的先序遍歷序列和中序遍歷序列分別是abdgcefh dgbaechf,求二叉樹及後序遍歷序列。分析 先序遍歷序列的第乙個字元為根結點。對於中序遍歷,根結點在中序遍歷序列的中間,左邊部分是根結點的左子樹的中序遍歷序列,右邊部分是根結點的右子樹的中序遍歷...

先序線索二叉樹的遍歷,後序線索二叉樹怎麼畫啊

include include typedef enum pointertag 指標標誌 typedef char datatype typedef struct bithretreebithretree bithretree pre 全域性變數,用於二叉樹的線索化 bithretree creat...

資料結構二叉樹的遍歷,C語言資料結構 二叉樹的遍歷

前序 根,左兒子,右兒子 中序 左兒子,根,右兒子 後序 左兒子,右兒子,根 首先是要牢記一上幾句話 比如這棵樹的中許遍歷,a有左兒子,先不訪問a,以此類推,直到d沒有左兒子,訪問d,然後訪問d的根b,然後應該訪問b的右兒子,但是b沒有,所以訪問b的根a,訪問完a以後訪問a的右子樹。先看c,c有左兒...