民國109年 第2梯次 電腦軟體設計(JAVA)乙級 學科

第79題

已知某個二元樹(Binary Tree) 之中序(Inorder) 為DCEBAFHGJIK 而後序(Postorder)為DECBHJKI GFA,下列敘述那…

題目

已知某個二元樹(Binary Tree) 之中序(Inorder) 為DCEBAFHGJIK 而後序(Postorder)為DECBHJKI GFA,下列敘述那些是正確?

  1. (1) 此二元樹之根(Root)為A
  2. (2) 此二元樹之葉節點(Leaf)共6 個
  3. (3) G 節點之左子節點(Left Son)為H
  4. (4) 此二元樹之前序(Preorder)為ABCDEFGHIJK

官方答案

(1) 此二元樹之根(Root)為A、(3) G 節點之左子節點(Left Son)為H、(4) 此二元樹之前序(Preorder)為ABCDEFGHIJK

解析

由後序（左右根）最末為 A，故根為 A，選項1正確。重建樹：左子樹中序 DCEB、後序 DECB，得 B 為左子，其左為 C，C 之左右為 D、E；右子樹中序 FHGJIK、後序 HJKIGF，得 F 為右子，其右為 G，G 左為 H、右為 I，I 左右為 J、K。葉節點為 D、E、H、J、K 共 5 個，選項2稱 6 個錯誤。前序（根左右）為 A B C D E F G H I J K，即 ABCDEFGHIJK，選項4正確；且 G 左子為 H，選項3正確。

AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。

官方資料