題組內容

三、關於二元樹（Binary Tree）的觀念，請回答下列問題：

(三)有一個二元樹（Binary Tree）有 10 個節點（Node），下列為此二元樹的中序走訪（Inorder Traversal）和前序走訪（Preorder Traversal）： 中序走訪（Inorder Traversal）：abcedfjgih 前序走訪（Preorder Traversal）：jcbadefigh 請畫出此二元樹。

詳解 (共 1 筆)

詳解 提供者：SjH
Step 1：找出Root：前序第一個是 j，所以 j 是根。在中序中找到 j，並將中序由j為中心分為：左邊 abcedf，右邊是 gih。
ㅤㅤ
Step 2 ：處理左子樹：前序接下來的 6 個依序為： cbadef，第一個字母 c 為左子樹根，並將中序由c 分左邊 ab、右邊 edf。
  1. 左側（中序 ab，前序 ba）：前序首 b 為根，b 的左子為 a。
  2. 右側（中序 edf，前序 def）：前序首 d 為根，d 的左子為 e，右子為 f。
Step 3 ：處理右子樹：前序最後一段是：igh，所以 i 為右子樹根，並將中序由 i 分左邊g、右邊h。
ㅤㅤ
完成樹狀圖如下：
ㅤㅤ
   69a158ca22f3d.jpg