民國107年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第5題
某二元樹(Binary Tree)之中序走訪(Inorder Traversal)為GDBAEHCIFJ,而前序走訪(Preo rder Trav ersal)…
題目
某二元樹(Binary Tree)之中序走訪(Inorder Traversal)為GDBAEHCIFJ,而前序走訪(Preo rder Trav ersal)為ABDGCEHFIJ,對於該二元樹之性質,下列敘述何者是正確的?
- (1) 分支度為1 之節點共有 3 個
- (2) 分支度為2 之節點共有4 個
- (3) 葉節點(Leaf Node)共5 個
- (4) 二元樹共有5 層
官方答案
(1) 分支度為1 之節點共有 3 個
解析
由前序 A 為根，中序分割得左 GDB、右 EHCIFJ。重建：A 左=B，B 左=D，D 左=G；A 右=C，C 左=E、E 右=H，C 右=F、F 左=I、F 右=J。分支度 1 之節點為 D、B、E 共 3 個（選項 1 對）。分支度 2 者為 A、C、F 共 3 個（選項 2 誤為 4）；葉節點 G、H、I、J 共 4 個（選項 3 誤為 5）；樹高為 4 層（選項 4 誤為 5）。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。