第4單元非線性數(shù)據(jù)結(jié)構(gòu)樹、二叉樹主講：劉志強(編輯修改稿)
2024-11-29 15:15 本頁面
【文章內(nèi)容簡介】 普通樹 二叉樹 （ a） （ b） （ c） （ d） （ e） O O O O O O 有兩種不同形式 （ a） （ b） O O O O O O O O O O O O O O O 有五種不同形式 下一頁 上一頁 停止放映 第 33 頁 二叉樹與樹的區(qū)別（二） ? 觀念 – 二叉樹的子樹有順序關(guān)系 ， 分左子樹和右子樹 ， 而樹則無此區(qū)分 ； – 二叉樹的分支度一定為 0、 1或 2，而樹的度可大于 2。 下一頁 上一頁 停止放映 第 34 頁 二叉樹的性質(zhì) ? 性質(zhì)一 二叉樹的第 i層上至多有 2i1 個結(jié)點 （ i ? 1） 。 利用歸納法證明： – i=1時 ， 只有一個結(jié)點 ， 對的； – 假設(shè)對所有的 j， 1? j ? i， 命題成立 ， 即在第 j層上 ， 至多有 2j1 個結(jié)點 。 – 由歸納假設(shè) ， 第 i1層上至多有 2i2 個結(jié)點 。由于二叉樹的每個結(jié)點的度至多為 2， 故第 i層上的最大結(jié)點數(shù)為第 i1層上的最大結(jié)點數(shù)的 2倍 ， 即 2 2i2 = 2i1。 下一頁 上一頁 停止放映 第 35 頁 二叉樹的性質(zhì)（二） 性質(zhì)二 深度為 k的二叉樹上最多含有 2k1個結(jié)點 （ k ? 1） 。 由性質(zhì)一可見 ， 深度為 k的二叉樹的最大結(jié)點數(shù)為： k i=1 i=1 k ? （ 第 i層上的最大結(jié)點數(shù) ） = ? 2i1 = 2k1 下一頁 上一頁 停止放映 第 36 頁 驗證二叉樹的性質(zhì) 1 2 3 8 6 5 7 4 10 9 11 12 13 14 15 該二叉樹的第 3層有 231 個結(jié)點。 該二叉樹深度為 4,最多有 241 個結(jié)點。 下一頁 上一頁 停止放映 第 37 頁 二叉樹的存儲結(jié)構(gòu) ? 順序存儲 （ 一維數(shù)組 ） ? 記錄數(shù)組結(jié)構(gòu) ? 鏈?zhǔn)酱鎯Y(jié)構(gòu) – 二叉鏈表 – 三叉鏈表 下一頁 上一頁 停止放映 第 38 頁 順序存儲法（一維數(shù)組） ? 若一個二叉樹的樹高為 n，則對一個滿二叉樹，其結(jié)點個數(shù)為 2n1。存入時按從左到右，從低階層到高階層的順序存放。 A B C D E F G 0 1 2 3 4 5 6 7 A B C D E F G 0 1 2 3 4 5 6 7 A B E A B E 滿樹 非滿樹 下一頁 上一頁 停止放映 第 39 頁 順序存儲（一維數(shù)組） 存儲描述為： define MAXSIZE 100； typedef TElemType SBTree[MAXSIZE]； SBTree bt； 不便查找 。 a1 a2 a3 a4 ... an 下一頁 上一頁 停止放映 第 40 頁 記錄數(shù)組結(jié)構(gòu) ? 存儲結(jié)構(gòu)描述 : define MAXSIZE 100。 typedef struct SBNode { TElemType data 。 int Lchild,Rchild。 } SBNode。 typedef struct｛ SBNode nodes[MAXSIZE]。 } SBTree。 下一頁 上一頁 停止放映 第 41 頁 記錄數(shù)組結(jié)構(gòu)舉例 1 2 6 3 4 5 1 2 6 2 3 4 3 0 5 4 0 0 5 0 0 6 0 0 結(jié)點 左子 右子 特點 : 找子方便 ,找父結(jié)點不便 . 下一頁 上一頁 停止放映 第 42 頁 二叉鏈表存儲結(jié)構(gòu) data leftp rightp 左指針 數(shù)據(jù) 右指針 A B C D E F G A B D C E F G ^ ^ ^ ^ ^ ^ ^ ^ 特點 : 找子易 , 找父難 . 下一頁 上一頁 停止放映 第 43 頁 三叉鏈表存儲結(jié)構(gòu) parent data rightp 左指針 數(shù)據(jù) 父結(jié)點 右指針 A B C D E F G C ^ ^ ^ ^ ^ ^ 特點 : 找子、找父都易。 leftp ^ ^ A B D E G ^ F 下一頁 上一頁 停止放映 第 44 頁 特殊二叉樹 滿二叉樹 完全二叉樹 平衡二叉樹 二叉排序樹 下一頁 上一頁 停止放映 第 45 頁 滿二叉樹 若 k為二叉樹 T的深度 ， 且 T中共有 2k1個結(jié)點 （ k ? 1） ， 則稱 T為滿二叉樹 。 （ a） 滿二叉樹 （ b） 非滿二叉樹 O O O O O O O O O O O O O 下一頁 上一頁 停止放映 第 46 頁 滿二叉樹的性質(zhì) 若對滿二叉樹從第 1層開始 ,自上而下 、 從左至右給每個結(jié)點從 1開始編號的話 ， 則稱深度為 k的滿二叉樹的結(jié)點編號滿足： – 對某結(jié)點 i（ 1? i ? 2k1 1） ， 其左子樹根的編號為 2*i（ 偶數(shù) ） ， 其右子樹根的編號為 2*i+1（ 奇數(shù) ） ； （ 非葉結(jié)點 ） – 若 i1,則結(jié)點 i父結(jié)點的編號為 i/2(整除 )。 根據(jù)這一性質(zhì) ， 可用一維數(shù)組存儲滿二叉數(shù)的結(jié)點數(shù)據(jù) 。知道一個結(jié)點的編號 ， 經(jīng)計算就能求出左 、 右子樹的根及父結(jié)點的編號 。 下一頁 上一頁 停止放映 第 47 頁 滿二叉樹存儲舉例 1 4 3 2 5 7 6 1 2 3 4 5 6 7 1 2 3 4 5 6
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1