申論題 - 阿摩線上測驗

申論題資訊

試卷：111年 - 111 地方政府特種考試_三等_資訊處理：資料結構#112604
科目：公職◆資料結構
年份：111年
排序：0

三、回顧二元樹結構，其為m路樹（m-aryTrees，亦稱多元樹、m元樹）的一個特例，請回答下列相關問題：

(三)基於此m路樹結構及二元搜尋樹（BinarySearchTree）的概念，我們可以定義出一個多元搜尋樹。當m=4的時候，可以稱此搜尋樹為四元搜尋樹。請給出(2,4)-樹((2,4)-tree)的定義並比較與四元搜尋樹的差異。（10分）

詳解提供者：114年高考上榜

1.每一個節點最多有 m 個子節點，以(2,4) tree 而言，最多有 4 個節點。

2.每一個非葉子節點（除根節點）最少有 ⌈m/2⌉ 個子節點，以(2,4) tree 而言，至少有 2 個

節點。

3.如果根節點不是葉子節點，那麼它至少有兩個子節點
4.所有的葉子節點都在同一層；(2,4)樹所有的葉子節點都在同一層；但四元搜尋樹則不要求。