【正文】 儲(chǔ) 27 A B C D E F G H I J K L 1 2 3 4 5 6 7 8 9 10 11 12 完全二叉樹(shù) J 1 2 3 4 5 6 7 8 9 10 11 12 E F H I K L A B D C G 28 一般二叉樹(shù) 1 2 3 4 5 7 11 A B C E G F D A B C D E F G 1 2 3 4 5 6 7 8 9 10 11 編號(hào)規(guī)則： 根結(jié)點(diǎn)的編號(hào)為 1；對(duì)于編號(hào)為 i的結(jié)點(diǎn)，左孩子如果存在，則編號(hào)為 2i，右孩子如果存在則編號(hào)為 2i+1。 26 將二叉樹(shù)的所有結(jié)點(diǎn)，按一定的順序存儲(chǔ)在一片連續(xù)的存儲(chǔ)單元中，使用結(jié)點(diǎn)之間的相對(duì)位置表示結(jié)點(diǎn)之間的關(guān)系。 用歸納法證明其中的 (2)和 (3)，再導(dǎo)出 (1)。 23 結(jié)點(diǎn)號(hào)與結(jié)點(diǎn)位置一一對(duì)應(yīng) ? 性質(zhì) 4 ： 具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的 深度為 ? log2n? +1 證明： 設(shè) 完全二叉樹(shù)的深度為 k 則根據(jù)第二條性質(zhì)得 2k1 1n ≤ 2k 1,即 2k1≤ n 2k 即 k1 ≤ log2 n k 因?yàn)? k 只能是整數(shù)，因此， k =?log2n? + 1 24 ?性質(zhì) 5 ： 若對(duì)含 n 個(gè)結(jié)點(diǎn)的 完全二叉樹(shù) 從上到下且從左至右進(jìn)行 1 至 n 的編號(hào)，則對(duì)完全二叉樹(shù)中任意一個(gè)編號(hào)為 i 的結(jié)點(diǎn)： (1) 若 i=1，則該結(jié)點(diǎn)是二叉樹(shù)的根，無(wú)雙親 , 否則，編號(hào)為 ?i/2? 的結(jié)點(diǎn)為其 雙親 結(jié)點(diǎn) 。 22 1 2 3 4 5 6 7 8 9 10 11 12 13 14 關(guān)系： 滿(mǎn)二叉樹(shù) 必為 完全二叉樹(shù)； 而完全二叉樹(shù)不一定是滿(mǎn)二叉樹(shù)。 19 ?性質(zhì) 2 ： 深度為 k 的二叉樹(shù)上至多含 2k1 個(gè)結(jié)點(diǎn)（ k≥ 1） 證明： 基于性質(zhì) 1，深度為 k 的二叉樹(shù)上的結(jié)點(diǎn)數(shù)至多為 20+21+ ? ? ? ? ? ? +2k1 = 2k1 20 ? 性質(zhì) 3 ： 對(duì)任何一棵二叉樹(shù)，若它含有 n0 個(gè)葉子結(jié)點(diǎn)、 n2 個(gè)度為 2 的結(jié)點(diǎn)，則必存在關(guān)系式： n0 = n2+1 證明： 設(shè) 二叉樹(shù)上結(jié)點(diǎn)總數(shù) n = n0 + n1 + n2 又 二叉樹(shù)上分支總數(shù) b = n1 + 2n2 而 b = n1 = n0 + n1 + n2 1 由此， n0 = n2 + 1 21 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 滿(mǎn)二叉樹(shù) 兩類(lèi)特殊的二叉樹(shù) 滿(mǎn)二叉樹(shù)： 深度為 k 且含有 2k1個(gè)結(jié)點(diǎn)的二叉樹(shù)。 (i≥ 1) 用歸納法 證明 ： 歸納基 ： 歸納假設(shè)： 歸納證明： i = 1 層時(shí)，只有一個(gè)根結(jié)點(diǎn)， 2i1 = 20 = 1； 假設(shè)對(duì)所有的 j， 1≤ j ? i， 命題成立 。將二叉樹(shù) bt置為空樹(shù)。按某個(gè)次序依次訪(fǎng)問(wèn)二叉樹(shù)中每個(gè)結(jié)點(diǎn)一次且僅一次。若結(jié)點(diǎn) x為葉子結(jié)點(diǎn)或 x不在 bt中，則返回“空”。若結(jié)點(diǎn) x為葉子結(jié)點(diǎn)或 x不在 bt中，則返回“空”。若結(jié)點(diǎn) x是二叉樹(shù)的根結(jié)點(diǎn)或二叉樹(shù) bt中無(wú)結(jié)點(diǎn) x，則返回“空”。 (6) Parent（ bt， x）： 求雙親函數(shù)。 (5) Root(bt)： 求二叉樹(shù) bt的根結(jié)點(diǎn)。 (3) Destory（ bt）： 銷(xiāo)毀二叉樹(shù) bt。 A B C D E F G H K 根結(jié)點(diǎn) 左子樹(shù) 右子樹(shù) 二叉樹(shù)中不存在度大于 2的結(jié)點(diǎn)，并且二叉樹(shù)的子樹(shù)有 左子樹(shù)和右子樹(shù) 之分！ 15 二、二叉樹(shù)的基本操作 ： (1)Initiate（ bt）：將 bt初始化為空二叉樹(shù)。 9 結(jié)點(diǎn) : 結(jié)點(diǎn)的度 : 樹(shù)的度 : 葉子結(jié)點(diǎn) : 分支結(jié)點(diǎn) : 數(shù)據(jù)元素 +若干指向子樹(shù)的分支 分支的個(gè)數(shù) 樹(shù)中所有結(jié)點(diǎn)的度的 最大值 度為零的結(jié)點(diǎn) 度大于零的結(jié)點(diǎn) 三、樹(shù)的基本術(shù)語(yǔ) 10 D H I J M 孩子 結(jié)點(diǎn) 、 雙親 結(jié)點(diǎn) 、 兄弟 結(jié)點(diǎn) 、 堂兄弟 結(jié)點(diǎn)、 祖先 結(jié)點(diǎn) 、 子孫 結(jié)點(diǎn) 結(jié)點(diǎn)的層次 : 樹(shù)的深度： A B C D E F G H I J M K L 從根結(jié)點(diǎn)開(kāi)始定義 ,根結(jié)點(diǎn)的層次為 1，根的直接后繼的層次為 2，依此類(lèi)推。按照某種次序?qū)?shù) Tree的每個(gè)結(jié)點(diǎn)調(diào)用 Visit（）函數(shù)訪(fǎng)問(wèn)一次且最多一次。刪除 Tree中 p所指向結(jié)點(diǎn)的第 i棵子樹(shù)。將 Child插入 Tree中，做 p所指向結(jié)點(diǎn)的子樹(shù)。若 x不是其雙親的最后一個(gè)孩子結(jié)點(diǎn)，則返回 x后面的下一個(gè)兄弟結(jié)點(diǎn)，否則返回“空”。若 x為非葉子結(jié)點(diǎn)，則返回它的第一個(gè)孩子結(jié)點(diǎn)，否則返回“空”。若 x為非根結(jié)點(diǎn)，則返回它的雙親，否則返回“空”。 (5) Root（ Tree）： 返回樹(shù) Tree的根。 (3) CreateTree（ Tree）： 創(chuàng)建樹(shù) Tree。 二、樹(shù)的抽象數(shù)據(jù)類(lèi)型定義 6 基本操作 ： (1) InitTree（ Tree）： 將 Tree初始化為一棵空樹(shù)。若 D中僅含有一個(gè)數(shù)據(jù)元素，則 R為空集，否則 R={H}，H是如下的二元關(guān)系： (1) 在 D中存在唯一的稱(chēng)為根的數(shù)據(jù)元素 root，它在關(guān)系 H下 沒(méi)有前驅(qū) 。 4 A B C D E F G H I J M K L A( ) T1 T3 T2 樹(shù)根 例如 : B(E, F(K, L)), C(G), D(H, I, J(M)) 5 數(shù)據(jù)對(duì)象 D：一個(gè)集合，該集合中的所有元素具有相同的特性。 (2) 其余 n1個(gè)結(jié)點(diǎn)可以劃分成 m(m≥0)個(gè)互不相 交的有限集 T1， T2， T3， … ， Tm，其中 Ti又 是一棵樹(shù)，稱(chēng)為 根 root的 子樹(shù) 。 樹(shù)的定義與基本概念 二叉樹(shù)的類(lèi)型定義 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 二叉樹(shù)的遍歷 樹(shù)、森林和二叉樹(shù)的關(guān)系及轉(zhuǎn)換 哈夫曼樹(shù)與哈夫曼編碼 2 樹(shù)的定義與基本概念 一、樹(shù)的基本概念 二、樹(shù)的抽象數(shù)據(jù)類(lèi)型定義： 三、樹(shù)的基本術(shù)語(yǔ) 3 一、 樹(shù)的基本概念 樹(shù)： 是 n(n≥0)個(gè)結(jié)點(diǎn)的有限集合 T。當(dāng) n=0時(shí)稱(chēng) 為空樹(shù)；當(dāng) n0時(shí)，該集合滿(mǎn)足如下條件 ： (1)其中必有一個(gè)稱(chēng)為 根 (root)的特定結(jié)點(diǎn)，它沒(méi) 有直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。每棵子樹(shù)的 根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但有零個(gè)或 多個(gè)直接后繼。 數(shù)據(jù)關(guān)系 R： 若 D為空集，則為空樹(shù)。 (2) 除 root以外， D中每個(gè)結(jié)點(diǎn)在關(guān)系 H下都有且 僅有一個(gè)前驅(qū) 。 (2) DestoryTree（ Tree）： 銷(xiāo)毀樹(shù) Tree。 (4) TreeEmpty（ Tree）： 若 Tree為空，則返回TRUE，否則返回 FALSE。 (6) Parent（ Tree， x）： 樹(shù) Tree存在， x是 Tree中的某個(gè)結(jié)點(diǎn)。 7 (7) FirstChild（ Tree， x）： 樹(shù) Tree存在， x是Tree中的某個(gè)結(jié)點(diǎn)。 (8) NextSibling（ Tree， x）： 樹(shù) Tree存在， x是 Tree中的某個(gè)結(jié)點(diǎn)。 (9) InsertChild（ Tree， p， Child）： 樹(shù) Tree存在， p指向 Tree中某個(gè)結(jié)點(diǎn)，非空樹(shù) Child與Tree不相交。 8 (10) DeleteChild（ Tree， p， i）： 樹(shù) Tree存在，p指向 Tree中某個(gè)結(jié)點(diǎn)， 1≤i≤d， d為 p所指向結(jié)點(diǎn)的度。 (11) TraverseTree（ Tree， Visit（））： 樹(shù) Tree存在， Visit（）是對(duì)結(jié)點(diǎn)進(jìn)行訪(fǎng)問(wèn)的函數(shù)。若 Visit（）失敗，則操作失敗。 樹(shù)中葉子結(jié)點(diǎn)所在的最大層次 11 任何一棵非空樹(shù)是一個(gè)二元組 Tree =（ root， F） 其中： root 被稱(chēng)為根結(jié)點(diǎn)， F 被稱(chēng)為子樹(shù)森林 森林： 是 m（ m≥ 0）棵互不相交的樹(shù)的集合 A root B E F K L C G D H I J M F 12 線(xiàn)性結(jié)構(gòu) 樹(shù)型結(jié)構(gòu) 第一個(gè)數(shù)據(jù)元素 (無(wú)前驅(qū) ) 根結(jié)點(diǎn) (無(wú)前驅(qū) ) 最后一個(gè)數(shù)據(jù)元素 (無(wú)后繼 ) 多個(gè)葉子結(jié)點(diǎn) (無(wú)后繼 ) 其它數(shù)據(jù)元素 (一個(gè)前驅(qū)、 一個(gè)后繼 ) 其它數(shù)據(jù)元素 (一個(gè)前驅(qū)、 多個(gè)后繼 ) 對(duì)比 樹(shù)型結(jié)構(gòu) 和 線(xiàn)性結(jié)構(gòu) 的結(jié)構(gòu)特點(diǎn) 13 二叉樹(shù)的類(lèi)型定義 二、二叉樹(shù)的基本操作 一、二叉樹(shù)的定義 三、二叉樹(shù)的性質(zhì) 14 二叉樹(shù)或?yàn)?空樹(shù) ；或是由一個(gè) 根結(jié)點(diǎn) 加上 兩棵 分別稱(chēng)為