數(shù)據(jù)結(jié)構(gòu)zmz二叉樹PPT學(xué)習(xí)教案

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)zmz二叉樹二叉樹請(qǐng)安靜 6.1樹的定義和基本術(shù)語第1頁/共44頁 1數(shù)據(jù)的邏輯結(jié)構(gòu) 2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 3、對(duì)數(shù)據(jù)的操作：檢索、排序、插入、刪除、修改A線性結(jié)構(gòu) B非線性結(jié)構(gòu)A 順序存儲(chǔ) B 鏈?zhǔn)酱鎯?chǔ) 線性表?xiàng)ｊ?duì)列樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)主要問題 第2頁/共44頁五子棋游戲.樹的實(shí)例第3頁/共44頁/ (root)libuseretcbinmathdsswyintaoxieStack.cppQueue.cppTree.cpp人類的族譜各種社會(huì)關(guān)系各類分類編碼編譯程序的語法樹Internet中的DNS（域名系統(tǒng)）UNIX文件系統(tǒng)結(jié)構(gòu)樹的實(shí)例第4頁/共44頁v定義：樹(tr

2、ee)是n(n0)個(gè)結(jié)點(diǎn)的有限集，其中：l n=0，稱為空樹l 有且僅有一個(gè)特殊的結(jié)點(diǎn)，稱為樹的根(root)l 當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的子集T1,T2,Tm，其中每一個(gè)集合本身又是一棵樹，稱為根的子樹(subtree)v特點(diǎn)：l 樹中至少有一個(gè)結(jié)點(diǎn)根l 樹的定義是遞歸定義的，各子樹也滿足上面定義。樹的定義 第5頁/共44頁線性結(jié)構(gòu) 樹型結(jié)構(gòu) 第一個(gè)數(shù)據(jù)元素 (無前驅(qū)) 根結(jié)點(diǎn) (無前驅(qū))最后一個(gè)數(shù)據(jù)元素 (無后繼)多個(gè)葉子結(jié)點(diǎn) (無后繼)其它數(shù)據(jù)元素 (一個(gè)前驅(qū)、 一個(gè)后繼)其它數(shù)據(jù)元素 (一個(gè)前驅(qū)、 多個(gè)后繼)第6頁/共44頁A只有根結(jié)點(diǎn)的樹 ABCDEFGHIJKL

3、M有子樹的樹 根 子樹 葉子葉子葉子 第7頁/共44頁ADT Tree 數(shù)據(jù)對(duì)象D: D是具有相同特性的數(shù)據(jù)元素的集合 數(shù)據(jù)關(guān)系R: 若D為空集，則稱為空樹 否則: (1) 在D中存在唯一的稱為根的數(shù)據(jù)元素root； (2) 當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為m (m0)個(gè)互不相交的 有限集T1, T2, , Tm，其中每一棵子集本身又是 一棵符合本定義的樹，稱為根root的子樹 基本操作： 查找類操作 插入類操作 刪除類操作 ADT Tree樹的抽象數(shù)據(jù)類型定義第8頁/共44頁基本操作：TreeEmpty(T)初始條件：樹T已存在操作結(jié)果：空樹，返回 TRUE;否則 FALSETreeDepth(T)

4、初始條件：樹T已存在操作結(jié)果：返回 T 的深度查找類：Root(T)初始條件：樹T已存在操作結(jié)果：返回T的根Value(T, cur_e)初始條件：樹T已存在,cur_e是T中結(jié)點(diǎn)操作結(jié)果：返回cur_e 的值Parent(T, cur_e)初始條件：樹T已存在,cur_e是T中結(jié)點(diǎn)操作結(jié)果：若cur_e是T中非根結(jié)點(diǎn),返回其雙親;否則,返回空樹的抽象數(shù)據(jù)類型定義第9頁/共44頁LeftChild(T, cur_e)初始條件：樹T已存在,cur_e是T中結(jié)點(diǎn)操作結(jié)果：若cur_e是T中非葉子結(jié)點(diǎn),返回其最左孩子;否則,返回空RightChild(T, cur_e)初始條件：樹T已存在,cur_

5、e是T中結(jié)點(diǎn)操作結(jié)果：若cur_e是T中非葉子結(jié)點(diǎn),返回其最右孩子;否則,返回空TraverseTree(T, visit()初始條件：樹T已存在操作結(jié)果：按某種次序?qū) 的每個(gè)元素調(diào)用函數(shù)visit()查找類：基本操作：樹的抽象數(shù)據(jù)類型定義第10頁/共44頁插入類：InsertChild(&T, &p,i,c)初始條件：樹T存在,p指向T中結(jié)點(diǎn),1i p指結(jié)點(diǎn)度+1,非空樹c與T不相交操作結(jié)果：將以c為根的樹插入為T中p指結(jié)點(diǎn)的第i棵子樹CreateTree(&T, definition)初始條件： definition給出樹的定義操作結(jié)果：按definition構(gòu)造樹TAssign(T,

6、cur_e, value)初始條件：樹T已存在,cur_e是T中結(jié)點(diǎn)操作結(jié)果：結(jié)點(diǎn)cur_e賦值為valueInitTree(&T)操作結(jié)果：構(gòu)造空樹T基本操作：樹的抽象數(shù)據(jù)類型定義第11頁/共44頁DeleteChild(&T, &p,i)初始條件：樹T存在,p指向T中結(jié)點(diǎn),1i p指結(jié)點(diǎn)度操作結(jié)果：刪除T中p指結(jié)點(diǎn)的第i棵子樹ClearTree(&T)初始條件：樹T 已存在操作結(jié)果：將樹T 清為空樹DestroyTree(&T)初始條件：樹T 已存在操作結(jié)果：銷毀樹T刪除類：基本操作：樹的抽象數(shù)據(jù)類型定義第12頁/共44頁樹的基本術(shù)語 第13頁/共44頁樹的基本術(shù)語 第14頁/共44頁任何

7、一棵非空樹是一個(gè)二元組 Tree = （root，F(xiàn)）其中：root 被稱為根結(jié)點(diǎn) F 被稱為子樹森林 樹的基本術(shù)語 第15頁/共44頁樹的表示 JIACBDHGFEKLM第16頁/共44頁GCKLEFBMHJIDA嵌套集合表示法 圖型表示法 樹的表示 JIACBDHGFEKLM第17頁/共44頁(A(B(E(k,L),F),C(G),D(H(M),I,J)括號(hào)(廣義表)表示法 圖型表示法 樹的表示 JIACBDHGFEKLM第18頁/共44頁圖型表示法 ABCDEFGHIJKLM凹入表示法 樹的表示 JIACBDHGFEKLM第19頁/共44頁結(jié)點(diǎn)A的度： 結(jié)點(diǎn)B的度： 結(jié)點(diǎn)M的度： 葉子：

8、 結(jié)點(diǎn)A的孩子： 結(jié)點(diǎn)B的孩子： 結(jié)點(diǎn)I的雙親： 結(jié)點(diǎn)L的雙親： 結(jié)點(diǎn)B，C，D為結(jié)點(diǎn)K，L為樹的度： 結(jié)點(diǎn)A的層次： 結(jié)點(diǎn)M的層次： 樹的深度：結(jié)點(diǎn)F，G為結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的結(jié)點(diǎn)F，G 是A結(jié)點(diǎn)的ABCDEFGHIJKLM3 2 0 B, C, D E, F 31 4 4 K, L, F, G, M, I, J D E 兄弟 兄弟 堂兄弟 祖先 子孫 請(qǐng)同學(xué)回答 第20頁/共44頁請(qǐng)安靜 6.2二 叉 樹第21頁/共44頁第22頁/共44頁空二叉樹 左、右子樹均非空 DRL只有根結(jié)點(diǎn)二叉樹 D右子樹為空 DL左子樹為空 DR二叉樹的定義 第23頁/共44頁有何區(qū)別？試分別畫出具有3個(gè)結(jié)點(diǎn)的

9、樹和3個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。二叉樹的定義 第24頁/共44頁第25頁/共44頁在二叉樹的第 i 層上至多有_個(gè)結(jié)點(diǎn)(i1) 第一層： 第二層： 第三層： 第i層：只有一個(gè)根結(jié)點(diǎn)：21-1 = 20 = 1； 二叉樹上每個(gè)結(jié)點(diǎn)至多有兩棵子 樹，則第 i 層的結(jié)點(diǎn)數(shù) = 2i-1 。 二叉樹的性質(zhì) 最多：20 2 = 21 = 2； 最多：21 2 = 22 = 4； 2i-1第26頁/共44頁二叉樹的性質(zhì) 思考：具有 n 個(gè)節(jié)點(diǎn)的二叉樹的深度 最小 _ ，最大_高度 h 的二叉樹最多有2h-1個(gè)節(jié)點(diǎn)（性質(zhì)2） n 2h-1 h log2(n+1) 解答：性質(zhì)2：12311458912 1

10、3671014 15深度為 k 的二叉樹上至多含 _個(gè)結(jié)點(diǎn)（k1） 證明：基于上一條性質(zhì)，深度為 k 的二叉樹上的結(jié)點(diǎn)數(shù)至多為 20+21+ +2k-1 = 2k-1 2k-1第27頁/共44頁 性質(zhì)3：對(duì)任何一棵二叉樹T，如果其葉子結(jié)點(diǎn)數(shù) 為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1 證明： 設(shè) n1 為度為1的節(jié)點(diǎn)數(shù) 二叉樹中所有節(jié)點(diǎn)的度2 結(jié)點(diǎn)總數(shù) n=n0+n1+n2 除根節(jié)點(diǎn)外，其余節(jié)點(diǎn)都是“別人”的孩子 又 葉子（n0）沒有孩子！ 所有的孩子數(shù)n-1=n1+2n2n=n1+2n2+1=n0+n1+n2 n0=n2+1 123456二叉樹的性質(zhì) 第28頁/共44頁特點(diǎn)：每一層上的結(jié)

11、點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù) 123114589121367101415滿二叉樹及其編號(hào) 指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹 特殊形式的二叉樹 第29頁/共44頁 完全二叉樹定義：深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為特點(diǎn) 葉子結(jié)點(diǎn)只可能在最后層和倒數(shù)第二層上出現(xiàn) 特殊形式的二叉樹第30頁/共44頁1231145891213671014151231145891267101234567123456 完全二叉樹中可能有度為1的結(jié)點(diǎn)嗎？第31頁/共44頁性質(zhì)4：123114589126710證明：設(shè)完全二叉樹的深度為 k 根據(jù)第二條性

12、質(zhì)得 n 2k -1 且 (2k-1 -1)+1 n 即 log2 n 1,則其雙親是i/2 (2)如果2in,則結(jié)點(diǎn)i無左孩子;否則其左孩子是2i (3)如果2i+1n,則結(jié)點(diǎn)i無右孩子;否則其右孩子是2i+1 第34頁/共44頁第35頁/共44頁第36頁/共44頁二叉樹的存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)第37頁/共44頁實(shí)現(xiàn)：按結(jié)點(diǎn)層次編號(hào)，依次存放二叉樹中的數(shù)據(jù)元素（用數(shù)組實(shí)現(xiàn)）二叉樹的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)第38頁/共44頁abcdefg 1 2 3 4 5 6 7 8 9 10 11a b c d e 0 0 0 0fg該存儲(chǔ)結(jié)構(gòu)能否反映結(jié)點(diǎn)之間的關(guān)系？0二叉樹的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)第39頁/共44頁思考：二叉樹的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)第40頁/共44頁 1 2 3 4 5 6 7 8 9 10 11a b c 0 d ef0 0g h0二叉樹的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu) 1 2 3 4 5 6 7 8 9 10 11 12a b c d 0 e 0 0 00 00f第41頁/共44頁lchild d