6
A
回答
16
這是序遍歷算法:
Preorder(T)
if (T is not null)
print T.label
Preorder(T.left)
Preorder(T.right)
讓我們試着去尋找的NNLLNL
輸入的算法。
顯然首先打印根的標籤。所以你知道根有標籤N
。現在算法在左子樹上遞歸。根據輸入,這也是N
。在左邊的子樹上遞增,即L
。現在你必須回溯,因爲你已經到了一片葉子。輸入中的下一個位置也是L
,所以當前節點有一個標有L
的右側子節點。回溯一次。再次回溯,因爲你已經添加了當前節點的所有孩子(最多2個孩子)。現在你又在根。你必須正確,因爲你已經離開了。根據輸入,這是N
。所以根的正確孩子是N
。那個左邊的孩子將是L
。這是你的樹:
N
/ \
N N
/\ /
L L L
請注意,該解決方案不一定是唯一的,但這會給你一個可能的解決方案。
僞代碼:
k = 0
input = ... get preorder traversal vector from user ...
Reconstruct(T)
if input[k] == N
T = new node with label N
k = k + 1
Reconstruct(T.left)
Reconstruct(T.right)
else
T = new node with label L
T.left = T.right = null
k = k + 1
調用具有空節點。
後續問題:給定包含不同節點標籤的二叉樹的前序遍歷和次序遍歷,如何唯一地重構樹?
相關問題
- 1. 抽象語法樹構造和遍歷
- 2. 從給定的Inorder/Preorder/Postorder遍歷中可以構造樹的數目
- 3. 從給定的預先遍歷構建二叉樹
- 4. 構造給定的二叉樹Post order
- 5. 從給定的前序遍歷構造BST?
- 6. 在不構造樹的情況下從LevelOrder遍歷中查找PostOrder遍歷
- 7. MATLAB樹構造
- 8. 從Java中的Post-order遍歷構造二進制搜索樹
- 9. 如何從等級遍歷構造完整樹
- 10. 從有序和水平遍歷構造二叉樹
- 11. 從有序和後序遍歷構造二叉樹
- 12. 後綴樹構造
- 13. 遍歷狀結構樹
- 14. C:鑄造新的結構VS鑄造給定結構
- 15. SQL中的構造樹
- 16. 如何構建一個給定水平順序遍歷的樹?
- 17. EXC_BAD_ACCESS二叉樹構造
- 18. 樹形圖構造函數
- 19. 表達式樹構造?
- 20. 二叉樹,構造函數
- 21. 如何構造節點樹?
- 22. 編程構造歷史
- 23. C使用結構指針構造樹
- 24. 構造NSData以構造?
- 25. 構造從構造繼承
- 26. 如何使用級別順序遍歷序列構造二叉樹
- 27. 遍歷樹的結構和作用
- 28. 由特定構造函數構造的結構圖addalltypesof
- 29. 構造綁定標
- 30. 「僞造」 JavaScript構造
你可以給一個輸入和輸出的樣本?預計哪種格式? – 2011-02-05 18:03:08
在發佈之前,通常認爲最好是至少將您的家庭作業複述一遍。告訴我們一些關於你試過的東西以及你卡在哪裏的幫助。這是一個問題和答案的地方,而不僅僅是「爲我寫代碼」。 – 2011-02-05 18:03:36