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

第74題

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

題目

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

  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。以中序 DCEBAFHGJIK 可知 A 左邊為 DCEB、右邊為 FHGJIK。左子樹後序 DECB 得根 B，中序 DCEB 中 B 居末，故 B 無右子；再得 C 為根、D 與 E 為其左右葉。右子樹後序 HJKIGF 得根 F，中序 F 在最前故 F 無左子；再得 G 為根，左 H、右子樹 JIK，其根為 I，左右為 J、K。葉節點為 D、E、H、J、K 共 5 個，非 6 個。G 的左子確實為 H。前序走訪得 ABCDEFGHIJK。

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

官方資料