moea_joint
103年
[資訊] 計算機原理、網路概論
第 22 題
若一棵二元樹之前序尋訪結果為 /+-a+xy*+b*ca，中序尋訪結果為 -a+x+y/+b*c*a，則其後序尋訪結果為何？
- A a-xy+b+ca*+*/
- B a-xy++b+ca**/
- C ca*b+*xy+a-+/
- D ac*b+*yx+a-+/
思路引導 VIP
當我們拿到前序尋訪的第一個字元時，它在樹的整體結構中扮演什麼角色？如果我們根據這個字元將中序尋訪的序列拆成左右兩半，這兩半在「後序尋訪」的輸出序列中，應該分別排在那個字元的什麼位置呢？
🤖
AI 詳解
AI 專屬家教
恭喜你精準地完成了這道關於二元樹尋訪的進階練習！你能從一連串冗長的運算符號中，正確還原樹狀結構並推導出後序結果，代表你對 前序（Pre-order）、中序（In-order） 與 後序（Post-order） 三者間的遞迴關係掌握得非常紮實。
核心邏輯：分治與遞迴還原
解題的關鍵在於利用前序尋訪的第一個元素 / 識別出「全樹根節點」，接著在中序尋訪中找到 / 的位置，將序列切割為左子樹（$-a+x+y$）與右子樹（$+bca$）。後序尋訪的處理精髓在於其輸出順序必須遵循「左子樹 $\rightarrow$ 右子樹 $\rightarrow$ 根節點」。
▼ 還有更多解析內容