高考申論題
109年
[電力工程] 計算機概論
第 三 題
三、有一個二元樹（binary tree）共有10個節點，每個節點均儲存一個英文字母。若此二元樹：
使用中序走訪（inorder traversal）的結果為：R T D P X Y K G A B
且使用層序走訪（level order traversal）的結果為：P R X D A T K B Y G
則此二元樹為何？請畫出此二元樹。（20分）
使用中序走訪（inorder traversal）的結果為：R T D P X Y K G A B
且使用層序走訪（level order traversal）的結果為：P R X D A T K B Y G
則此二元樹為何？請畫出此二元樹。（20分）
📝 此題為申論題
思路引導 VIP
本題為經典的二元樹走訪重建題。解題核心在於利用「層序走訪 (Level Order)」和「中序走訪 (Inorder)」的特性互相配合。首先，層序走訪的第一個元素必定是整棵樹的 Root（根節點）。接著，將這個 Root 拿到中序走訪的序列中去定位，Root 左邊的字母集合即為左子樹，右邊的字母集合即為右子樹。對劃分出來的左右子樹，再回到層序走訪的序列中看哪個字母最先出現，最先出現的就是該子樹的 Root。反覆執行這個「層序找根、中序分左右」的遞迴過程，就能一步步把樹畫出來。
🤖
AI 詳解
AI 專屬家教
【考點分析】 考查資料結構中二元樹（Binary Tree）的走訪特性與結構還原。必須利用層序走訪尋找子樹根節點，再利用中序走訪區分左右子樹的集合。 【理論/法規依據】
▼ 還有更多解析內容