問題詳情

20.給一二元樹 (binary tree)，已知此樹的 preorder(前序) traversal為 A，B，D，C，E，G，F， inorder(中序) traversal 為 D，B，A，G，E，C，F，則它的 postoder(後序) traversal 為何？
(A) D，A，B，G，E，F，C
(B) D，B，G，E，F，C，A
(C) D，B，E，G，F，C，A
(D) D，B，G，E，F，A，C

參考答案

答案：B
難度：適中0.579
書單：沒有書單，新增

用户評論

【用戶】不叫賭俠的陳小刀

【年級】高三下

【評論內容】根據二元樹的前序(preorder)遍歷和中序(inorder)遍歷序列，可以推導出其後序(postorder)遍歷序列。根據前序遍歷序列 "A，B，D，C，E，G，F"，我們可以知道根節點是 "A"。根據中序遍歷序列 "D，B，A，G，E，C，F"，我們可以得到以下結論：根節點的左子樹為 "D，B"。根節點的右子樹為 "G，E，C，F"。接下來，我們對左子樹和右子樹進行遞迴處理，得到以下子樹的後序遍歷序列：左子樹: D，B右子樹: G，E，C，F最後，將根節點 "A" 放在後序遍歷序列的最後。因此，整個二元樹的後序遍歷序列為 "D，B，G，E，C，F，A"。所以，答案是 (B) D，B，G，E，F，C，A。

【用戶】不叫賭俠的陳小刀

【年級】高三下

【評論內容】根據二元樹的前序(preorder)遍歷和中序(inorder)遍歷序列，可以推導出其後序(postorder)遍歷序列。根據前序遍歷序列 "A，B，D，C，E，G，F"，我們可以知道根節點是 "A"。根據中序遍歷序列 "D，B，A，G，E，C，F"，我們可以得到以下結論：根節點的左子樹為 "D，B"。根節點的右子樹為 "G，E，C，F"。接下來，我們對左子樹和右子樹進行遞迴處理，得到以下子樹的後序遍歷序列：左子樹: D，B右子樹: G，E，C，F最後，將根節點 "A" 放在後序遍歷序列的最後。因此，整個二元樹的後序遍歷序列為 "D，B，G，E，C，F，A"。所以，答案是 (B) D，B，G，E，F，C，A。