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