【正文】 （ root， F） 其中： root 被稱為根結(jié)點 F 被稱為子樹森林 森林（ Forest）： 是 m（ m≥ 0）棵互 不相交的樹的集合 A root B C D E F G H I J M K L F ? ADT Tree { 數(shù)據(jù)對象 ： D是具有相同特性的數(shù)據(jù)元素的集合。 兄弟（ sibling）： 同一個雙親的孩子之間互為兄弟。 結(jié)點的層次（ level）： 根為第一層，依次類推。 結(jié)點的度（ degree of node）： 一個結(jié)點的子樹個數(shù)。 (3) 若 n1，除根結(jié)點之外的其余數(shù)據(jù)元素被分成 m(m0)個互不相交的集合 T1， T2， … ， Tm，其中每一個集合 Ti(1≤i≤m)本身又是一棵樹。數(shù)據(jù)結(jié)構(gòu) 常靜 Email: 第六章 樹和二叉樹 二叉樹 樹的定義和基本術(shù)語 遍歷二叉樹和線索二叉樹 樹和森林 第六章 樹和二叉樹 樹的定義和基本術(shù)語 樹的例子（ 1）： 第一節(jié) 樹的定義 樹的例子（ 2）： 第一節(jié) 樹的定義 1．樹的定義 樹 (Tree)是 n(n≥0)個有限數(shù)據(jù)元素的集合。樹 T1， T2， … ， Tm稱為這個根結(jié)點的子樹。 終端結(jié)點（ terminal node） (葉子（ leaf ) ）： 度為 0的結(jié)點。 樹的深度（ depth）（高度（ height））： 樹中結(jié)點的最大層次 有序樹： 樹中結(jié)點的子樹是有次序的。 堂兄弟： 雙親在同一層的結(jié)點互為堂兄弟。 數(shù)據(jù)關(guān)系 ： 若 D 為空集，則稱為 空樹 ； 若 D 中僅含一個數(shù)據(jù)元素，則關(guān)系 R為空集； 否則 R={H}， (1) 在 D中存在唯一的稱為 根 的數(shù)據(jù)元素 root，它在關(guān)系 H下無前驅(qū)； (2) 當(dāng) n1時，其余數(shù)據(jù)元素可分為 m(m0) 個互不相交的 (非空 )有限集 T1,T2,…,Tm, 其中每一個子集本身又是一棵符合本定義的樹，稱為根 root 的 子樹 ，每一棵子樹的根 xi 都是根 root 的后繼，即 root,xi H,i=1,2,…,m 。 CreateTree(amp。 {銷毀結(jié)構(gòu) } DestroyTree(amp。 第三節(jié) 樹的抽象數(shù)據(jù)類型 ? TreeEmpty(T)。 初始條件：樹 T存在。 操作結(jié)果：返回 T 的根。 第三節(jié) 樹的抽象數(shù)據(jù)類型 ? Parent(T, cur_e)。 初始條件：樹 T 存在， cur_e 是 T 中某個結(jié)點。 操作結(jié)果：若 cur_e 有右兄弟，則返回它的 右兄弟 ，否則返回 空 。一旦 visit() 失敗，則操作失敗。 ClearTree(amp。 InsertChild(amp。 操作結(jié)果： 插入 c 為 T 中 p 所指結(jié)點的第 i 棵子樹。 初始條件：樹 T 存在， p 指向 T 中某個結(jié)點， 1≤i≤p 指結(jié)點的度。 ? 二叉樹也可以用遞歸的形式定義。 A B C D E F G H K 根結(jié)點 左子樹 右子樹 二叉樹的五種基本形態(tài)： N 空樹 只含根結(jié)點 N N N L R R 右子樹為空樹 L 左子樹為空樹 左右子樹均不為空樹 ADT BinaryTree { 數(shù)據(jù)對象 ： D 是具有相同特性的數(shù)據(jù)元素的集合。T)。 初始條件： definition 給出二叉樹 T 的定義。 初始條件：二叉樹 T 存在。 操作結(jié)果：若 T為空二叉樹，則返回 TRUE，否則返回 FALSE。 Root(T)。 初始條件：二叉樹 T 存在， e 是 T 中某個結(jié)點。 操作結(jié)果：若 e是 T的非根結(jié)點，則返回它的雙親，否則返回 空 。若 e 無左孩子，則返回 空 。若 e 無右孩子，則返回 空 。若 e 是其雙親的左孩子或無左兄弟，則返回 空 。若 e 是其雙親的右孩子或無右兄弟，則返回 空 。一旦 visit() 失敗，則操作失敗。一旦 visit() 失敗，則操作失敗。一旦 visit() 失敗，則操作失敗。一旦 visit() 失敗，則操作失敗。 操作結(jié)果：將二叉樹 T 清為空樹 。 初始條件：二叉樹 T 存在， e 是 T 中某個結(jié)點。 初始條件：二叉樹 T 存在， p 指向 T 中某個結(jié)點，LR 為 0 或 1，非空二叉樹 c 與 T 不相交且右子樹為空。T, p, LR)。 ? 性質(zhì) 2 深度為 k的二叉樹中至多含有 2k1 個結(jié)點， (k≥1)。 （ 2） 在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干結(jié)點后得到的二叉樹仍然是一棵完全二叉樹。 // 0號單元存儲根結(jié)點 SqBiTree bt。 lchild data rchild 結(jié)點結(jié)構(gòu) : C 語言的類型描述如下 : 第三節(jié) 二叉樹的存儲結(jié)構(gòu) A D E B C F ? ? ? ? ? ? ? root ? 2．三叉鏈表 parent lchild data rchild 結(jié)點結(jié)構(gòu) : 第三節(jié) 二叉樹的存儲結(jié)構(gòu) typedef struct TriTNode { // 結(jié)點結(jié)構(gòu) TElemType data。 parent lchild data rchild 結(jié)點結(jié)構(gòu) : C 語言的類型描述如下 : 第三節(jié) 二叉樹的存儲結(jié)構(gòu) 第六章 樹和二叉樹 遍歷二叉樹和線索二叉樹 按某條搜索路徑巡訪樹中每個結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次。 }else return OK。 }else return OK。 }else return OK。ch)。 CreateBiTree(Tlchild)。 ? 線索二叉樹的表示 : ? 若結(jié)點有左子樹 ， 則其 LCHILD域指示其左孩子 ，否則令 LCHILD域指示其前驅(qū)； ? 若結(jié)點有右子樹 ， 則其 RCHILD域指示其右孩子 ，否則令 RCHILD域指示其后繼 。 – 如根結(jié)點 “ ”的前驅(qū)是 “ d” 。 //左右孩子指針 PointerTag LTag,RTag。 if (!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit (OVERFLOW)。 //右指針回指 if (!T)Thrtlchild=Thrt。 //中序遍歷進(jìn)行中序線索化 prerchild=Thrt。 }//InOrderThreading 第二節(jié) 線索二叉樹 中序遍歷進(jìn)行中序線索化 void InThreading(BiThrTree p){ // 一個全程指針 pre if (p){ InThreading(plchild)。 prerchild=p。 第一節(jié) 樹的存儲結(jié)構(gòu) //樹的雙親表存儲表示 // define MAX_TREE_SIZE 100 typedef struct PTNode { TElemType data。 int r， n。 int child1。 typedef struct{ PTNode nodes[MAX_TREE_SIZE]。 R A B / C D / E / F G / H / K / 1 2 3 / 4 5 / 6 / 7 8 9 / [ ]。 struct CTNode *next。 //孩子鏈表頭指針 }CTBox。 第一節(jié) 樹的存儲結(jié)構(gòu) 三、孩子兄弟表示法 樹的二叉樹表示法 (二叉鏈表示法 ) ? //樹的二叉鏈表 (孩子兄弟 )存儲表示 typedef struct CSNode { ELemType data。 ? (1)若 F為空 ， 即 m=0,則 B為空樹； ? (2)若 F非空 ， 即 m0， 則 B的根 root即為森林中第一棵樹的根 ROOT(T1)； ? B的左子樹 LB是從 T1中根結(jié)點的子樹森林F1={T11,T12, … ,T1m1}轉(zhuǎn)換而成的二叉樹 。={T2,T3, … ，Tm}是由 B的右子樹 RB轉(zhuǎn)換而成的森林 。 二、中序遍歷森林： 若森林非空，則 （ 1）中序遍歷第一棵樹的根結(jié)點的子樹森林； （ 2）訪問森林中第一棵樹的根結(jié)點； （ 3）中序遍歷除去第一棵樹之后的森林。 k=1 第一節(jié) 赫夫曼樹及其應(yīng)用 a b c d 7 5 2 4 WPL=7x3+5x3+2x1+4x2 = 46 例：下面兩棵二叉樹的四個葉子結(jié)點 a,b,c,d的權(quán)值為 4 c d a b 7 5 2 4 (a)WPL=7x2+5x2+2x2+4x2 = 36 (b)WPL=7x1+5x2+2x2+4x2 = 35 第一節(jié) 赫夫曼樹及其應(yīng)用 a b c d 7 5 2 4 最優(yōu)二叉樹的定義 ? 假設(shè)有 n個權(quán)值 {ω 1, ω 2, … , ω n}， 試構(gòu)造一棵有 n個葉子結(jié)點 的二叉樹 ， 每個葉子結(jié)點帶權(quán)為 ω i, 則其中： 帶權(quán)路徑長度 WPL最小的二叉樹稱做最優(yōu)二叉樹 ， 或赫夫曼樹 第一節(jié) 赫夫曼樹及其應(yīng)用 例下面三棵二叉樹的四個葉子結(jié)點 a,b,c,d的權(quán)值為 4 a b c d 7 5 2 4 a b c d 7 5 2 4 c d a b 7 5 2 4 (a)WPL=7x2+5x2+2x2