【正文】 數(shù)據(jù)結構 常靜 Email: 第六章 樹和二叉樹 二叉樹 樹的定義和基本術語 遍歷二叉樹和線索二叉樹 樹和森林 第六章 樹和二叉樹 樹的定義和基本術語 樹的例子（ 1）： 第一節(jié) 樹的定義 樹的例子（ 2）： 第一節(jié) 樹的定義 1．樹的定義 樹 (Tree)是 n(n≥0)個有限數(shù)據(jù)元素的集合。 (1)當 n＝ 0時，稱這棵樹為空樹。在一棵非空樹 T中： (2) 在 n0時，有且僅有一個特殊的數(shù)據(jù)元素稱為樹的根結點，根結點只有后繼結點，沒有前驅(qū)結點。 (3) 若 n1，除根結點之外的其余數(shù)據(jù)元素被分成 m(m0)個互不相交的集合 T1， T2， … ， Tm，其中每一個集合 Ti(1≤i≤m)本身又是一棵樹。樹 T1， T2， … ， Tm稱為這個根結點的子樹。 A C G T2 D H I T3 J M B E L K T1 F 空樹 僅有根結 點的樹 第一節(jié) 樹的定義 下面列出一些樹結構和非樹結構的示意圖： 第一節(jié) 樹的定義 2. 樹的表示方法 1) 直觀表示法（ a） 樹的直觀表示法是以倒著的分支樹的形式表示。 2) 嵌套集合表示法 (b) 3) 凹入表示法 (c) 4) 廣義表表示法 (d) （ a） （ b） （ d） （ c） 第一節(jié) 樹的定義 對比 樹型結構 和 線性結構的結構特點 第一節(jié) 樹的定義 線性結構 樹型結構 第一個數(shù)據(jù)元素 (無前驅(qū) ) 根結點 (無前驅(qū) ) 最后一個數(shù)據(jù)元素 (無后繼 ) 多個葉子結點 (無后繼 ) 其它數(shù)據(jù)元素 (一個前驅(qū)、 一個后繼 ) 其它數(shù)據(jù)元素 (一個前驅(qū)、 多個后繼 ) 結點（ node）： 樹中的每個元素及指向其子樹根的分支。 結點的度（ degree of node）： 一個結點的子樹個數(shù)。 終端結點（ terminal node） (葉子（ leaf ) ）： 度為 0的結點。 非終端結點（ nonterminal node）（分支結點）： 度不為0的結點。 樹的度（ degree of tree）： 樹內(nèi)各結點的度的最大值。 結點的層次（ level）： 根為第一層，依次類推。 樹的深度（ depth）（高度（ height））： 樹中結點的最大層次 有序樹： 樹中結點的子樹是有次序的。 無序樹： 樹中結點的子樹是無次序的。 第二節(jié) 基本術語 在樹結構中，結點之間的關系又可以用家族關系描述，定義如下： 孩子（ child）和雙親（ parent）： 結點子樹的根稱為這個結點的孩子，而這個結點又被稱為孩子的雙親。 兄弟（ sibling）： 同一個雙親的孩子之間互為兄弟。 堂兄弟： 雙親在同一層的結點互為堂兄弟。 祖先（ ancestor）： 從根結點到該結點路徑上的所有結點。反之，以某結點為根的子樹中的任一結點都稱為該結點的子孫 。 第二節(jié) 基本術語 任何一棵非空樹是一個二元組 Tree = （ root， F） 其中： root 被稱為根結點 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ù)元素的集合。 數(shù)據(jù)關系 ： 若 D 為空集，則稱為 空樹 ； 若 D 中僅含一個數(shù)據(jù)元素，則關系 R為空集； 否則 R={H}， (1) 在 D中存在唯一的稱為 根 的數(shù)據(jù)元素 root，它在關系 H下無前驅(qū)； (2) 當 n1時，其余數(shù)據(jù)元素可分為 m(m0) 個互不相交的 (非空 )有限集 T1,T2,…,Tm, 其中每一個子集本身又是一棵符合本定義的樹，稱為根 root 的 子樹 ，每一棵子樹的根 xi 都是根 root 的后繼，即 root,xi H,i=1,2,…,m 。 第三節(jié) 樹的抽象數(shù)據(jù)類型 ? 基本操作 ： {結構初始化 } InitTree(amp。T)。 操作結果：構造空樹 T。 CreateTree(amp。T,definition)。 初始條件： definition 給出樹 T的定義。 操作結果：按 definition 構造樹 T。 {銷毀結構 } DestroyTree(amp。T)。 初始條件：樹 T 存在。 操作結果：銷毀樹 T。 第三節(jié) 樹的抽象數(shù)據(jù)類型 ? TreeEmpty(T)。 初始條件：樹 T 存在。 操作結果：若 T 為空樹，則返回 TRUE，否則返回 FALSE。 TreeDepth(T)。 初始條件：樹 T存在。 操作結果：返回 T的 深度 。 Root(T)。 初始條件：樹 T 存在。 操作結果：返回 T 的根。 Value(T, cur_e)。 初始條件：樹 T 存在， cur_e 是 T 中某個結點。 操作結果：返回 cur_e 的值。 第三節(jié) 樹的抽象數(shù)據(jù)類型 ? Parent(T, cur_e)。 初始條件：樹 T 存在， cur_e 是 T 中某個結點。 操作結果：若 cur_e 是 T的非根結點，則返回它的 雙親 ，否則返回 空 。 LeftChild(T, cur_e)。 初始條件：樹 T 存在， cur_e 是 T 中某個結點。 操作結果：若 cur_e 是 T的非葉子結點，則返回它的最 左孩子 ，否則返回 空 。 RightSibling(T, cur_e)。 初始條件：樹 T 存在， cur_e 是 T 中某個結點。 操作結果：若 cur_e 有右兄弟，則返回它的 右兄弟 ，否則返回 空 。 TraverseTree(T, visit())。 初始條件：樹 T存在， visit 是對結點操作的應用函數(shù)。 操作結果：按某種次序?qū)? T 的每個結點調(diào)用函數(shù) visit() 一次且至多一次。一旦 visit() 失敗，則操作失敗。 ? Assign(T, cur_e, value)。 初始條件：樹 T存在， cur_e 是 T 中某個結點。 操作結果：結點 cur_e 賦值為 value。 ClearTree(amp。T)。 初始條件：樹 T 存在。 操作結果：將樹 T 清為空樹 。 InsertChild(amp。T, amp。p, i, c)。 初始條件：樹 T 存在， p 指向 T中某個結點， 1≤i≤p 所指結點的度＋ 1，非空樹 c 與 T 不相交。 操作結果： 插入 c 為 T 中 p 所指結點的第 i 棵子樹。 DeleteChild(amp。T, amp。p, i)。 初始條件：樹 T 存在， p 指向 T 中某個結點， 1≤i≤p 指結點的度。 操作結果： 刪除 T 中 p 所指結點的第 i 棵子樹。 } ADT Tree 第六章 樹和二叉樹 二叉樹 第一節(jié) 二叉樹的定義 ? 定義： 二叉樹 是另一種樹形結構。它與樹形結構的區(qū)別是： ? （ 1）每個結點最多有兩棵子樹； ? （ 2）子樹有左右之分。 ? 二叉樹也可以用遞歸的形式定義。即：二叉樹是 n（ n≥ 0）個結點的有限集合。當 n=0時，稱為 空二叉樹 ；當 n0時，有且僅有一個結點為二叉樹的 根 ，其余結點被分成兩個互不相交的子集，一個作為 左子集 ，另一個作為 右子集 ，每個子集又是一個二叉樹。 二叉樹或為 空樹 ，或是由一個 根結點 加上 兩棵 分別稱為 左子樹 和 右子樹的、 互不交的 二叉樹 組成。 A B C D E F G H K 根結點 左子樹 右子樹 二叉樹的五種基本形態(tài)： N 空樹 只含根結點 N N N L R R 右子樹為空樹 L 左子樹為空樹 左右子樹均不為空樹 ADT BinaryTree { 數(shù)據(jù)對象 ： D 是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關系 ： 若 D 為空集，稱 BinaryTree 為 空二叉樹 ； 否則 關系 R={H}： (1) 在 D 中存在唯一的稱為 根 的數(shù)據(jù)元素 root，它在關系 H 下無前驅(qū)； (2) D 中其余元素 必可分為 兩個互不相交的子集 L 和 R，每一個子集都是一棵符合本定義的二叉樹，并分別為 root 的 左子樹 和 右子樹 。如果左子樹 L 不空，則必存在一個根結點 ，它是 root 的 左后繼(root, ∈ H)，如果右子樹 R 不空，則必存在一個根結點 為 root 的 右后繼 (root, ∈ H)。 第一節(jié) 二叉樹的定義 ? 基本操作 ： {結構初始化 } InitBiTree(amp。T)。 操作結果：構造 空 二叉樹 T。 CreateBiTree(amp。T, definition)。 初始條件： definition 給出二叉樹 T 的定義。 操作結果：按 definition 構造二叉樹 T。 {銷毀結構 } DestroyBiTree(amp。T)。 初始條件：二叉樹 T 存在。 操作結果：銷毀二叉樹 T。 第一節(jié) 二叉樹的定義 ? BiTreeEmpty(T)。 初始條件：二叉樹 T 存在。 操作結果：若 T為空二叉樹，則返回 TRUE，否則返回 FALSE。 BiTreeDepth(T)。 初始條件：二叉樹 T 存在。 操作結果：返回 T 的深度。 Root(T)。 初始條件：二叉樹 T 存在。 操作結果：返回 T 的根。 Value(T, e)。 初始條件：二叉樹 T 存在， e 是 T 中某個結點。 操作結果：返回 e 的值。 第一節(jié) 二叉樹的定義 ? Parent(T, e)