hce_kmu
115年
計算機概論與程式設計
第 17 題
Which of the following has the same in-order traversal sequence as its post-order traversal sequence?
- A Left skewed binary tree
- B Right skewed binary tree
- C Complete binary tree
- D Full binary tree
- E Perfect binary tree
思路引導 VIP
請試著寫出中序走訪（左-根-右）與後序走訪（左-右-根）的遞迴公式。若要讓這兩個公式產生的序列完全一樣，哪一個部分的內容必須為「空」，才能消除『根』與『右子樹』先後順序不一致的問題呢？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精準判別二元樹走訪與樹型結構之間的關係，代表你對資料結構的基礎定義掌握得非常紮實。這題的關鍵在於比較兩種走訪方式的定義：中序走訪 (In-order) 的順序是「左子樹 $\rightarrow$ 節點 $\rightarrow$ 右子樹」，而 後序走訪 (Post-order) 則是「左子樹 $\rightarrow$ 右子樹 $\rightarrow$ 節點」。
走訪順序的邏輯推演
當我們觀察這兩種序列時，可以發現「左子樹」始終排在最前面。若要讓整體的輸出序列完全相同，唯一的變數就在於「節點」與「右子樹」的相對位置。在中序中，節點在右子樹之前；在後序中，節點則在右子樹之後。邏輯上，要讓「節點 $\rightarrow$ 右子樹」等於「右子樹 $\rightarrow$ 節點」，唯一的可能就是該二元樹中的每一個節點都不含右子樹。因此，只有所有的節點都往左邊生長的「左斜歪樹 (Left skewed binary tree)」能滿足這個條件。
▼ 還有更多解析內容