【正文】 若 D= ， 則 R= ， 稱 Binary為空二叉樹； 若 D≠ ， 則 R={H}， H是如下二元關(guān)系： (1) 在 D中存在唯一的稱為根的數(shù)據(jù)元素 root， 它在關(guān)系 H下無前驅(qū)； (2) 若 D{root}≠ ， 則存在 D{root}的一個(gè)劃分 {Dl， Dr}， 且 Dl∩D r= ； (3) 若 Dl≠ ,則 Dl中 存在唯一的元素 x1,root,x1 H, 且存在 Dl上的關(guān)系Hl?H,若 Dr ≠ ,則 Dr中存在唯一的元素 xr,root,xr H,且存在 Dr上的關(guān)系Hr?H。不能隨意顛倒。 (2) 當(dāng) n1時(shí)，其余的結(jié)點(diǎn)最多分為 2個(gè)互不相交的子集 T1, T2, 每個(gè)又都是二叉樹，分別稱為根的 左子樹 和 右子樹 . 二叉樹（ Binary Tree） 例 二叉樹的定義 A B C D E F G H K 根結(jié)點(diǎn) 左子樹 右子樹 二叉樹 注意： 二叉樹不是樹，它是另外單獨(dú)定義的一種樹形結(jié)構(gòu)，并非一般樹的特例。 }ADT Tree 基本操作 : ? 樹的表示方法： 1. 樹形表示： 樹（ Tree） 的定義和基本術(shù)語 A B C D E F H I J G 2. 括號(hào)表示 (廣義表表示 )： (A(B(E))(C(F))(D(G(H)(I)(J)))) T1 T3 T2 樹根 3. 凹入表表示 (目錄表示法 )： A B C D E F H I J G A B E C F D G H I J 樹（ Tree） 的定義和基本術(shù)語 4. 文氏圖表示 (集合表示 ): A B C D E F H I J G A B E C F D G H I J 樹（ Tree） 的定義和基本術(shù)語 二叉樹是另一種樹形結(jié)構(gòu)。 TraverseTree(T)； 初始條件；樹 T存在 。T， amp。 操作結(jié)果：插入 c為 T中 p所指結(jié)點(diǎn)的第 i棵子樹 。T， amp。 操作結(jié)果：若 cur_e有右兄弟，則返回它的右兄弟， 否則 返回 “ 空 ” 。 操作結(jié)果：若 cur_e是 T的非葉子結(jié)點(diǎn) ， 則返回它的 最左孩子 ， 否則返回 “ 空 ” 。 操作結(jié)果：若 cur_e是 T的非根結(jié)點(diǎn) ， 則返回它的雙親 ， 否則返回 “ 空 ” 。 操作結(jié)果：結(jié)點(diǎn) cur_e 賦值為 value。 操作結(jié)果：返回 cur_e的值 。 操作結(jié)果：返回 T的根 。 操作結(jié)果；返回 T的深度 。 操作結(jié)果：若 T為空樹 ， 則返回 TRUE， 否則 FALSE。 操作結(jié)果：將樹 T清為空樹 。 ClearTree(amp。T， definition) 初始條件： definition給出樹 T的定義 。 操作結(jié)果 ， 銷毀樹 T。 DestroyTree(amp。 數(shù)據(jù)關(guān)系 R： 若 D為空集，則稱為 空樹 ； 若 D僅含一個(gè)數(shù)據(jù)元素，則 R為空集，否則 R={H}， H是如下二元關(guān)系： (1) 在 D中存在唯一的稱為根的數(shù)據(jù)元素 root， 它在關(guān)系 H下 無前驅(qū)； (2) 若 D{root}≠ ， 則存在 D{root}的一個(gè)劃分 D1， D2， … ， Dm， (m0)， 對任意 j≠k(1≤j,k≤m)有 Dj∩Dk= , 且對任意的 i(1≤i≤m)， 唯一存在數(shù)據(jù)元素 xi∈ Di， 有 root， xi∈ H； ??(3) 對應(yīng)于 D{root}的劃分 ， H—{root， x1， …， root， xm} 有唯一的一個(gè)劃分 H1,H2， …， Hm(m0)， 對任意 j≠k( 1≤j ， k≤m) 有 Hj∩H k= ,且對任意 i(1≤i≤m),H i是 Di上的二元 關(guān)系 ,(Di,{Hi})是一棵符合本定義的樹 ,稱為根 root的子樹 . ?基本操作 : InitTree(amp。 祖先、后代（ ancestor） :一個(gè)結(jié)點(diǎn)是它所有子樹中的結(jié)點(diǎn) 的祖先，這些結(jié)點(diǎn)是它的后代 (子孫 )。 樹的定義和基本術(shù)語 二叉樹 遍歷二叉樹和線索二叉樹 樹和森林 Huffman樹及其應(yīng)用 第六章 樹與二叉樹 內(nèi)蒙古大學(xué) 理工學(xué)院 計(jì)算機(jī)學(xué)院 生命科學(xué)學(xué)院 外國語學(xué)院 人文學(xué)院 數(shù)學(xué)系 物理系 電子系 計(jì)算機(jī)系 計(jì)算中心 網(wǎng)絡(luò)中心 漢語系 歷史系 哲學(xué)系 生物系 環(huán)境系 動(dòng)物中心 生物工程中心 資源所 英語系 日語系 行政機(jī)構(gòu) 樹形結(jié)構(gòu)是一種非線性結(jié)構(gòu)，應(yīng)用十分廣泛。 如：行政機(jī)構(gòu)、家譜、磁盤目錄等 磁盤目錄 根 Root 分枝 Branch 葉 Leaf 根 根結(jié)點(diǎn) 分枝 分枝結(jié)點(diǎn) 葉 葉結(jié)點(diǎn) 樹（ Tree） 的定義和基本術(shù)語 ?樹的定義 ：樹是 n（ n=0） 結(jié)點(diǎn)的有限集， 在任意非空樹中： (1) 有且僅有一個(gè)特定的結(jié)點(diǎn)稱為根（ Root） 的結(jié)點(diǎn) . (2) 當(dāng) n1時(shí)，其余的結(jié)點(diǎn)可分為 m個(gè)互不相交的子 集 T1, T2, … , T m, 每個(gè)子集又都是樹，稱為根 的 子樹（ Sub tree） . 樹（ Tree） 的定義和基本術(shù)語 樹的定義具有遞歸性 Tree=D, {R} D={Book, C1, C2, C3, , , , , , , } R={Book,C1, Book,C2, Book,C3, C1, C1, C2, C2, C2, , , , } Book C1 C2 C3 Chapter Section Section 例 樹（ Tree） 的定義和基本術(shù)語 ?術(shù)語主要來源于家譜和樹： 雙親、父母（ Parent）；子女、孩子（ Child）： 若〈 a,b〉 ? R， 則稱 a是 b的雙親， b是 a 的子女 (孩子 ). 葉結(jié)點(diǎn)（ Leaf） ： 度為 0的結(jié)點(diǎn)； 分枝結(jié)點(diǎn)（ Branch node） ： 度大于 0的結(jié)點(diǎn)； 結(jié)點(diǎn)度（ Degree） ： 該結(jié)點(diǎn)所擁有的子女?dāng)?shù)； 樹的度 ：樹內(nèi)各結(jié)點(diǎn)度的最大值； 結(jié)點(diǎn)的層次（ Level） ： 設(shè)根結(jié)點(diǎn)的層次為 1，其它任一結(jié)點(diǎn) 所在的層次是其雙親的層次加 1； 樹（ Tree） 的定義和基本術(shù)語 ?樹是一種層次結(jié)構(gòu) （ hiberarchy） 1 2 3 4 5 樹（ Tree） 的定義和基本術(shù)語 堂兄弟（ Cousin） ： 雙親在同一層的結(jié)點(diǎn)之間互稱堂兄弟； 路徑（ Path） ： 如果有結(jié)點(diǎn)序列 n1,n2,n3,…,n k， 并且前 1個(gè)結(jié) 點(diǎn)是后 1個(gè)結(jié)點(diǎn)的雙親；它的長度是 k1。 有序樹（ Ordered tree） ： 每個(gè)結(jié)點(diǎn)的子女由左到右是有次 序的稱有序樹；否則是無序樹； 樹（ Tree） 的定義和基本術(shù)語 A B C A C B 無序 有序 深度（ Depth） ： 樹中結(jié)點(diǎn)的最大層次；或稱為高； 兄弟（ Sibling)： 具有同一雙親的結(jié)點(diǎn)互稱兄弟； A B C D E F G H I J K L M 結(jié)點(diǎn) A的度： 3 結(jié)點(diǎn) B的度： 2 結(jié)點(diǎn) M的度： 0 葉子： K， L， F， G， M， I， J 結(jié)點(diǎn) A的孩子： B， C， D 結(jié)點(diǎn) B的孩子： E， F 結(jié)點(diǎn) I的雙親： D 結(jié)點(diǎn) L的雙親： E 結(jié)點(diǎn) B， C， D為兄弟 結(jié)點(diǎn) K， L為兄弟 樹的度： 3 結(jié)點(diǎn) A的層次： 1 結(jié)點(diǎn) M的層次： 4 樹的深度： 4 結(jié)點(diǎn) F， G為堂兄弟 結(jié)點(diǎn) A是結(jié)點(diǎn) F， G的祖先 T1 T2 T3 T4 T5 T6 樹（ Tree） 的定義和基本術(shù)語 ?森林（ Forest） ： 是 m(m 0)棵互不相交的樹的集合 (例如刪除樹根后的子樹構(gòu)成一個(gè)森林 ) ?A root B C D E F G H I J M K L F 任何一棵非空樹是一個(gè)二元組 Tree = （ root， F） 其中： root 被稱為根結(jié)點(diǎn)， F 被稱為子樹森林 ?抽象數(shù)據(jù)類型樹的定義： 樹（ Tree） 的定義和基本術(shù)語 ADT Tree{ 數(shù)據(jù)對象 D： D是具有相同特性的數(shù)據(jù)元素的集合。T) 操作結(jié)果：構(gòu)造空樹 T。T) 初始條件：樹 T存在 。 CreateTree(amp。 操作結(jié)果：按 definition構(gòu)造樹 T。T) 初始條件；樹 T存在 。 TreeEmpty(T) 初始條件：樹 T存在 。 TreeDepth(T) 初始條件：樹 T存在 。 基本操作 : Root(T) 初始條件：樹 T存在 。 Value(T， cur_e) 初始條件：樹 T存在 ， cur_e是 T中某個(gè)結(jié)點(diǎn) 。 Assign(T， cur_e， value) 初始條件：樹 T存在 ， cur_e是 T中某個(gè)結(jié)點(diǎn) 。 Parent(T， cur_e)； 初始條件：樹 T存在 ， cur_e是 T中某個(gè)結(jié)點(diǎn) 。 基本操作 : LeftChild(T， cur_e)； 初始條件：樹 T存在 ， cur_e是 T中某個(gè)結(jié)點(diǎn) 。 RightSibling(T， cur_e)； 初始條件：樹 T存在 ， cur_e是 T中某個(gè)結(jié)點(diǎn) 。 基本操作 : InsertChild(amp。P， i， c)； 初始條件：樹 T存在 ,p指向 T中某個(gè)結(jié)點(diǎn) ， i指結(jié)點(diǎn)的度 , 非空樹 c與 T不相交 。 DeleteChild(amp。p， i)； 初始條件：樹 T存在 ， p指向 T中某個(gè)結(jié)點(diǎn) ， i指結(jié)點(diǎn)的度 , 操作結(jié)果：刪除 T中 p所指結(jié)點(diǎn)的第 i棵子樹 。 操作結(jié)果：按某種次序?qū)?T的每個(gè)結(jié)點(diǎn)進(jìn)行遍歷 。 二叉樹的定義 二叉樹： 是 n（ n=0） 結(jié)點(diǎn)的有限集，在任意非空樹中： (1) 有且僅有一個(gè)特定的稱為根（ Root） 的結(jié)點(diǎn) 。它的子樹有順序規(guī)定，分為左子樹和右子樹。 二叉樹的 5種基本形態(tài)： 1 空 2 只有根 3 右子樹空 4 左子樹空 5 左、右子樹非空 具有 3個(gè)結(jié)點(diǎn)的 二叉樹 可能有幾種不同形態(tài)？ 抽象數(shù)據(jù)類型二叉樹的定義： ADT BinaryTree{ 數(shù)據(jù)對象 D： D是具有相同特性的數(shù)據(jù)元素的集合 。H={root,xl,root,xr,Hl,Hr} (4)(Dl,{Hl})是一顆符合本定義的二叉樹 ， 稱為根的左子樹 (Dr,{Hr})是一顆符合本定義的二叉樹 ， 稱為根的右子樹 二叉樹的定義 ?????????基本操作 : InitBiTree(amp。 操作結(jié)果：構(gòu)造空二叉樹 T。T)。 操作結(jié)果：銷毀二叉樹 T。T,definition)。 操作結(jié)果：按 definition構(gòu)造二叉樹 T。T)； 初始條件：二叉樹 T存在 。 BiTreeEmpty(T)； 初始條件：二叉樹 T存在 。 操作結(jié)果：返回 T的深度 。