[計算機軟件及應(yīng)用]數(shù)據(jù)結(jié)構(gòu)zmz_5二叉樹(編輯修改稿)
2025-02-15 17:31 本頁面
【文章內(nèi)容簡介】 H G F E K L M 結(jié)點 A的度： 結(jié)點 B的度： 結(jié)點 M的度： 葉子： 結(jié)點 A的孩子： 結(jié)點 B的孩子： 結(jié)點 I的雙親： 結(jié)點 L的雙親： 結(jié)點 B， C， D為 結(jié)點 K， L為 樹的度： 結(jié)點 A的層次： 結(jié)點 M的層次： 樹的深度： 結(jié)點 F， G為 結(jié)點 A是結(jié)點 F， G的 結(jié)點 F， G 是 A結(jié)點的 A B C D E F G H I J K L M 3 2 0 B, C, D E, F 3 1 4 4 K, L, F, G, M, I, J D E 兄弟 兄弟 堂兄弟 祖先 子孫 請同學回答 請安靜 167。 二 叉 樹 二叉樹 為何要重點研究每結(jié)點最多只有兩個 “ 叉 ” 的樹 ？ ? 二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強； ? 可以證明，所有樹都能轉(zhuǎn)換為唯一的一棵二叉樹與其對應(yīng)，不失一般性。 二叉樹的定義 二叉樹的性質(zhì) 二叉樹的存儲結(jié)構(gòu) ? 定義：二叉樹是 n(n?0)個結(jié)點的有限集，它或為 空樹 (n=0)，或由一個根結(jié)點和兩棵分別稱為 左子樹 和 右子樹 的互不相交的二叉樹構(gòu)成 ? 特點 ? 每個結(jié)點 至多 有二棵子樹 (不存在度大于 2的結(jié)點 ) ? 子樹有 左、右之分 ，且其次序不能任意顛倒 ? 基本形態(tài) ? 空二叉樹 左、右子樹均非空 D R L 只有根結(jié)點二叉樹 D 右子樹為空 D L 左子樹為空 D R 二叉樹的定義 ? 有關(guān)二叉樹下列說法正確的是（ ） A．二叉樹的度為 2 B．一棵二叉樹的度可以小于 2 C．二叉樹中至少有一個結(jié)點的度為 2 D．二叉樹中任何一個結(jié)點的度都為 2 ? 問：一棵度為 2的樹和一棵二叉樹有何區(qū)別？ ? 試分別畫出具有 3個結(jié)點的樹和 3個結(jié)點的二叉樹的所有不同形態(tài)。 二叉樹的定義 二叉樹的抽象數(shù)據(jù)類型定義 ADT BinaryTree{ 數(shù)據(jù)對象 D: 數(shù)據(jù)關(guān)系 R: 基本操作 P： }ADT BinaryTree 若 D=Φ，則 R= Φ ； 若 D≠Φ，則 R= {H}；存在二元關(guān)系： ① root 唯一 //關(guān)于根的說明 ② Dl∩Dr= Φ //關(guān)于子樹不相交的說明 ③ …… //關(guān)于二元關(guān)系的說明 ④ …… //關(guān)于左子樹和右子樹的說明 D是具有相同特性的數(shù)據(jù)元素的集合。 //至少有 20個 ?性質(zhì) 1： 在二叉樹的第 i 層上至多有 ___個結(jié)點 (i≥1) 第一層 ： 第二層： 第三層： 第 i層： 只有一個根結(jié)點： 211 = 20 = 1； 二叉樹上每個結(jié)點至多有兩棵子 樹， 則第 i 層的結(jié)點數(shù) = 2i1 。 二叉樹的性質(zhì) 最多： 20 ? 2 = 21 = 2； 最多： 21 ? 2 = 22 = 4； 2i1 二叉樹的性質(zhì) ?思考 ： 具有 n 個節(jié)點的二叉樹的深度 最小 ________ ，最大 ________ ∵ 高度 h 的二叉樹最多有 2h1個節(jié)點（性質(zhì) 2） ∴ n ≤ 2h1 ∴ h ≥ log2(n+1) 解答 ： ?性質(zhì) 2： 1 2 3 11 4 5 8 9 12 13 6 7 10 14 15 深度為 k 的二叉樹上至多含 ____個結(jié)點（ k≥1） 證明：基于上一條性質(zhì)，深度為 k 的二叉樹上的結(jié)點數(shù)至多為 20+21+ ? ? ? ? ? ? +2k1 = 2k1 2k1
教學課件相關(guān)推薦
鄂ICP備17016276號-1