1 回答

TA貢獻1868條經驗 獲得超4個贊
由中序遍歷和層次遍歷能夠唯一確定一顆二叉樹。從下面的算法可知,每一步構造得到的二叉樹結果是唯一的。
以下構造部分的答案來自百度知道:
假定樹的層次遍歷ABCDEFG HIJ中序遍歷DBGEHJACIF
兩種遍歷順序要結合著分析,才能畫出這顆樹的圖
比如,層次遍歷,先訪問到A節點,說明A是樹的根節點
那么在中序遍歷結果里看:
DBGEHJ在A前面,說明這些節點,都在A左子樹上
CIF在A的后面,說這些節點,都在A的右子樹上
那么,樹可以先這樣畫:
__________A________
________/____\_____
_____DBGEHJ__CIF___
再看層次遍歷,A后面是B,說明B是A左子樹的根節點
從上圖中的先序遍歷順序DBGEHJ中看到:
D在B的前面,說明D在B的左子樹上
GEHJ在B的后面,說明它們在B的右子樹上
那么,樹又可以畫成:
_________A________
_______/____\_____
_____B________CIF__
____/__\____________
___D__GEHJ_________
如此循環,直到將整個樹都畫完全
結果如下:
_____________A_______________
___________/____\_____________
________B_________C__________
______/___\_________\_________
_____D_____E_________F_______
__________/__\_________\______
_________G____H_________I____
_______________\______________
_________________J____________
- 1 回答
- 0 關注
- 746 瀏覽
添加回答
舉報