這點(diǎn)應(yīng)該懂吧
由后續(xù)訪問(wèn)序列可以看出最后一個(gè)被訪問(wèn)的必定是這個(gè)樹(shù)的根
而中序遍歷的序列可以看出,一棵樹(shù)當(dāng)根確定后,在根前面被訪問(wèn)的是他的左子樹(shù),后邊的是他的右子樹(shù)元素
弄懂了上邊兩點(diǎn)就開(kāi)始做題吧
由后序遍歷序列是DBCEFGHA
為了方便,我寫(xiě)小寫(xiě)字母了啊
可以看出整棵樹(shù)的根節(jié)點(diǎn)是a
再看中序遍歷序列EDCBAHFG
a是根節(jié)點(diǎn)
左子樹(shù)由a左邊的元素EDCB構(gòu)成
右子樹(shù)由a右邊的元素HFG構(gòu)成
也就是
a
/----\
EDCB--HFG
到這里應(yīng)該都懂吧
那接下來(lái)就著重講一下左子樹(shù)的確定
右子樹(shù)同理可得了
看左子樹(shù)有4個(gè)元素EDCB
后序遍歷序列是DBCE
最后訪問(wèn)e
可以確定a下邊連接的是e
根據(jù)中序遍歷序列EDCB
最先訪問(wèn)e
由于中序遍歷e前面沒(méi)有元素
可以確定e左子樹(shù)為空
即下面的樣子
a
/\
e
\
dbc
也就是還剩下dbc的順序沒(méi)理好
后序遍歷序列是dbc
最后訪問(wèn)c
則c為根節(jié)點(diǎn)
連接e
中序遍歷序列dcb
c前邊有d
后邊有b
哪么可以確定dcb這棵樹(shù)為
c
/\
d b
哪么整棵樹(shù)的左子樹(shù)就確定了
為
e
\
c
/\
d b
同理
右子樹(shù)應(yīng)為
h
\
g
/
f
則整棵樹(shù)就出來(lái)了
為下圖所示
得出整棵樹(shù)
前序遍歷自然不在話下
為aecdbhgf
------------------------
暈了,想偷下懶都不行呵
同理就是要你自己照著剛才的方法再推右邊啊
左邊在上邊已經(jīng)說(shuō)了
那我們來(lái)看右邊
右邊剩下HFG
后序遍歷序列是fgh
h最后被訪問(wèn)
可以確定h是右子樹(shù)的根
也就是與a連著的是h
接下來(lái)看中序遍歷順序是HFG
h前面沒(méi)有元素
說(shuō)明h的左子樹(shù)為空
剩下的g和f都是他的右子樹(shù)的元素
再看后續(xù)遍歷序列FG
g最后被訪問(wèn)
可以確定g是根節(jié)點(diǎn)連接h
然后看中序遍歷序列fg
f在前
哪么f應(yīng)該為g的左子樹(shù)
整棵樹(shù)就出來(lái)了
再不懂我也不知道怎么解釋了
額
-------------------------
好久沒(méi)做類(lèi)似的題
有點(diǎn)生疏了
若果有錯(cuò)
歡迎指出
