[計(jì)算機(jī)軟件及應(yīng)用]數(shù)據(jù)結(jié)構(gòu)06gj(已修改)
2024-10-31 04:11 本頁面
【正文】 第六章 樹和二叉樹 樹的結(jié)構(gòu)特點(diǎn) 樹型結(jié)構(gòu)是以分支關(guān)系定義的層次結(jié)構(gòu)， 任意一棵非空樹中：（ 1）有且僅有一個(gè)特定 的稱為根的結(jié)點(diǎn)；（ 2）當(dāng) n1時(shí)，其余結(jié)點(diǎn)為分為 m個(gè)互不相交的有限集 T1,T2,T m,每一個(gè)子集本身 也是一棵樹。 樹型結(jié)構(gòu)在編譯程序中，可用來表示源程序 的語法結(jié)構(gòu)。 在數(shù)據(jù)庫系統(tǒng)中，樹型結(jié)構(gòu)也是信 息的重要組織形式之一。 是一類重要的 非線性結(jié)構(gòu) , 是以 分支關(guān)系 定義的 層次結(jié)構(gòu) 。 A B C D E F G H I J A (a) (b) (c) 樹的例子 : 樹型結(jié)構(gòu) 現(xiàn)實(shí)世界： 如家譜、行政組織機(jī)構(gòu)等。 計(jì)算機(jī)領(lǐng)域： 編譯程序、數(shù)據(jù)庫系統(tǒng)等。 樹 (Tree)的定義 ： n個(gè)結(jié)點(diǎn)組成的有限集合。 滿足如下兩個(gè)條件（非空樹）： A B C D E F G H I J 樹的定義和基本術(shù)語 (2)當(dāng) n1時(shí)，根結(jié)點(diǎn)以外的其它結(jié)點(diǎn)可分 m(m0)個(gè)互不相交的有限集合 T1, T2, … Tm。 其中 Ti稱為 子樹 。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有 0個(gè)或多個(gè)直接后繼。 (1)有且僅有一個(gè)特定的 根 (Root)結(jié)點(diǎn) ； (A(B(E(K,L),F),C(G),D(H(M),I,J)) 嵌套括號(hào)表示法 I J F K L G M C C D B E A 嵌套集合 凹入表 樹形表示 A B C D E F G H I J K L M 樹的表示方法 1. 結(jié)點(diǎn) 2. 結(jié)點(diǎn)的度 3. 葉子 (終端結(jié)點(diǎn) ) 4. 分枝結(jié)點(diǎn) (非終端結(jié)點(diǎn) ) 5. 樹的度 6. 孩子結(jié)點(diǎn) 雙親結(jié)點(diǎn) 7. 兄弟結(jié)點(diǎn) 祖先結(jié)點(diǎn) 子孫結(jié)點(diǎn) 8. 層次 樹的高度 (深度 ) 9. 有序樹 無序樹 10. 森林 (樹林 ) A B C D E F G H I J K L M 基本術(shù)語 InitTree(amp。T) 構(gòu)造空樹 T。 Root(T) 求樹 T的根結(jié)點(diǎn)。 Parent(T,x) 求樹 T中值為 x的結(jié)點(diǎn)的雙親。 Child(T,x,i) 求樹 T中值為 x的結(jié)點(diǎn)的第 i個(gè)孩子。 AddChild(T,y,i,x) 樹 T中將值為 x的結(jié)點(diǎn)作為值 y的結(jié)點(diǎn)的第 i個(gè)孩子插入到樹中。 DelChild(T,x,i)刪除值為 x的結(jié)點(diǎn)的第 i個(gè)孩子。 Traverse(T) 遍歷或訪問樹 T。 樹的基本運(yùn)算 二叉樹的定義 每個(gè)結(jié)點(diǎn)至多只有兩棵子樹，并且， 二叉樹 二叉樹的子樹有左右之分，其次序不 能任意顛倒。 二叉樹的 5種形式 (a) 空二叉樹 (b) 僅有根結(jié)點(diǎn)的二叉樹 (c) 右子樹為空的二叉樹 (e) 左子樹為空的二叉樹 (d) 根和左右子樹 A A B A B A C B 二叉樹的性質(zhì) 性質(zhì) 1： 第 i層上至多有 2i1個(gè)結(jié)點(diǎn) (i≥ 1)。 性質(zhì) 2： 深度為 k的二叉樹至多有 2k－ 1個(gè)結(jié)點(diǎn) 性質(zhì) 3： 對(duì)任何一棵二叉樹，如果其終端結(jié)點(diǎn)數(shù) 為 n0，度為 2的結(jié)點(diǎn)數(shù)為 n2，則 n0＝ n2+1. 性質(zhì) 4： 具有 n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 └log2n┘＋ 1。 二叉樹的性質(zhì)（續(xù)） 性質(zhì) 5： n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號(hào) ,則對(duì)任一結(jié)點(diǎn) i (1≤i≤n)，有： (1)如果 i＝ 1，則結(jié)點(diǎn) i無雙親，是二叉樹的根； 果 i1，則其雙親是結(jié)點(diǎn) └i/2┘。 (2)如果 2in，則結(jié)點(diǎn) i為葉子結(jié)點(diǎn)，無左孩子； 否則 (即： 2i≤n)，其左孩子是結(jié)點(diǎn) 2i。 (3)如果 2i＋ 1n，則結(jié)點(diǎn) i無右孩子； 否則 (即： 2i+1≤n) ，其右孩子是結(jié)點(diǎn) 2i＋ 1。 (a) 滿二叉樹 2 4 5 3 6 7 1 (b)完全二叉樹 2 4 5 3 6 1 (c)非完全二叉樹 2 4 5 3 7 1 (d)非完全二叉樹 2 3 6 7 1 特殊形態(tài)的二叉樹 二叉樹的抽象定義 ADT BinaryTree{ 數(shù)據(jù)對(duì)象 D： D是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系 R：若 D=空集， R為空集，稱為空二叉 樹； 若 D為非空， R為二元關(guān)系。 基本操作 P： …… } ADT BinaryTree InitBiTree(amp。T) 構(gòu)造空二叉樹 T。 DestroyBiTree(amp。T)銷毀二叉樹 T。 Root(T) 求 T的根結(jié)點(diǎn)。 Parent(T,e) 求 T中值為 e的結(jié)點(diǎn)的雙親。 LChild(T,e)/RChild(T,e) 求 T中值為 e的結(jié)點(diǎn)的左 /右孩子。 LBrother(T,e)/RBrother(T,e) 求 T中值為 e的結(jié)點(diǎn)的左 /右兄弟。 二叉樹的基本操作 二叉樹的基本操作（續(xù)） Traverse(T) 遍歷二叉樹 T。 AddLChild(amp。T,x,y)/AddRChild(amp。T,x,y) 在 T中，將值為 y的結(jié)點(diǎn)作為值為 x的結(jié)點(diǎn)的左 / 右孩子插入。 DelLChild(amp。T,x)/DelRChild(amp。t,x) 在 T中，刪除值為 x的結(jié)點(diǎn)的左 /右孩子。 順序存儲(chǔ)結(jié)構(gòu) 順序存放到一個(gè)一維數(shù)組中。 define MAX_TREE_SIZE 100 typedef TElemType SqBiTree[MAX_TREE_SIZE ]。 SqBiTree bt。 a b c d e f g h i j k l l k j i h g f e d c b a 0 1 2 3 4 5 6 7 8 9 10 11 完全二叉樹
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1