1、會(huì)計(jì)學(xué)1 節(jié)節(jié) 二叉樹和樹二叉樹和樹 2 第1頁(yè)/共26頁(yè) 3 第2頁(yè)/共26頁(yè) 4 線性結(jié)構(gòu)樹型結(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è)后繼) 對(duì)比對(duì)比樹型結(jié)構(gòu)樹型結(jié)構(gòu)和和線性結(jié)構(gòu)線性結(jié)構(gòu)的結(jié)構(gòu)特的結(jié)構(gòu)特 點(diǎn)點(diǎn) 第3頁(yè)/共26頁(yè) 5 結(jié)點(diǎn)結(jié)點(diǎn): :數(shù)據(jù)元素+ +若干指向子樹的分支 結(jié)點(diǎn)的度結(jié)點(diǎn)的度: :分支的個(gè)數(shù) 樹的度樹的度: :樹中所有結(jié)點(diǎn)的度的最大值 葉子結(jié)點(diǎn)葉子結(jié)點(diǎn): :度為零的結(jié)點(diǎn) 分支結(jié)點(diǎn)分支結(jié)點(diǎn): :度大于零的結(jié)點(diǎn) D HIJ M 基本術(shù)

2、語(yǔ)基本術(shù)語(yǔ) 第4頁(yè)/共26頁(yè) 6 (從根到結(jié)點(diǎn)的)路徑路徑： 孩子孩子結(jié)點(diǎn)、雙親雙親結(jié)點(diǎn) 兄弟兄弟結(jié)點(diǎn)、堂兄弟 祖先祖先結(jié)點(diǎn)、子孫子孫結(jié)點(diǎn) 由從根根到該結(jié)點(diǎn) 所經(jīng)分支和結(jié)點(diǎn)構(gòu) 成 A BCD EFGHIJ MKL 結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次: :假設(shè)根結(jié)點(diǎn)的層次為1 1,第l 層 的結(jié)點(diǎn)的子樹根結(jié)點(diǎn)的層次為l+1 1 樹的深度：樹的深度：樹中葉子結(jié)點(diǎn)所在的最大層次 第5頁(yè)/共26頁(yè) 7 一、二叉樹的定義和基本術(shù)語(yǔ)一、二叉樹的定義和基本術(shù)語(yǔ) 二、二叉樹的幾個(gè)基本性質(zhì)二、二叉樹的幾個(gè)基本性質(zhì) 三、二叉樹的存儲(chǔ)結(jié)構(gòu)三、二叉樹的存儲(chǔ)結(jié)構(gòu) 第6頁(yè)/共26頁(yè) 8 第7頁(yè)/共26頁(yè) 9 二叉樹二叉樹的定義的定義

3、二叉樹是n（n0）個(gè)元素的有限集，它或?yàn)榭諛淇諛?，或是由一個(gè)根結(jié)點(diǎn)根結(jié)點(diǎn)加上兩棵兩棵分別稱為左子樹左子樹和右子樹的、互不交的互不交的二叉樹二叉樹組成。 根結(jié)點(diǎn) 左子樹 右子樹 A B C D E F G HK L B 第8頁(yè)/共26頁(yè) 10 二叉樹二叉樹可以表現(xiàn)出可以表現(xiàn)出五種基本形態(tài)五種基本形態(tài)： 空樹空樹 N 只含根結(jié)點(diǎn)只含根結(jié)點(diǎn) 右子樹為空樹右子樹為空樹 N L 左子樹為空樹左子樹為空樹 N R 左右子樹均不為空樹左右子樹均不為空樹 N LR 第9頁(yè)/共26頁(yè) 11 二叉樹二叉樹的基本操作：的基本操作： v 查查 找找 類類 的的 操操 作作 v 插插 入入 類類 的的 操操 作作 v

4、刪刪 除除 類類 的的 操操 作作 第10頁(yè)/共26頁(yè) 12 Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T); InOrderTraverse(T); PostOrderTraverse(T); LevelOrderTraverse(T); 查找類的操作：查找類的操作： 第11頁(yè)/共26頁(yè) 13 InitBiTree( A

5、ssign(T, CreateBiTree( InsertChild(T, p, LR, c); 插入類的操作：插入類的操作： 第12頁(yè)/共26頁(yè) 14 ClearBiTree( DestroyBiTree( DeleteChild(T, p, LR); 刪除類的操作：刪除類的操作： 第13頁(yè)/共26頁(yè) 15 二、二叉樹的幾個(gè)基本性質(zhì)二、二叉樹的幾個(gè)基本性質(zhì) 第14頁(yè)/共26頁(yè) 16 用歸納法證明用歸納法證明： 歸納基歸納基： 歸納假設(shè)：歸納假設(shè)： 歸納證明：歸納證明： i = 1 層時(shí)，只有一個(gè)根結(jié)點(diǎn)： 2i-1 = 20 = 1； 假設(shè)對(duì)所有的 j，1 j i，命題成立； 二叉樹上每個(gè)結(jié)點(diǎn)

6、至多有兩棵子樹， 則第 i 層的結(jié)點(diǎn)數(shù) = 2i-2 2 = 2i-1 。 第15頁(yè)/共26頁(yè) 17 證明：證明： 基于上一條性質(zhì)，深度為 k 的二叉 樹上的結(jié)點(diǎn)數(shù)至多為 20+21+ +2k-1 = 2k-1 。 第16頁(yè)/共26頁(yè) 18 證明：證明： 設(shè)設(shè) 二叉樹上結(jié)點(diǎn)總數(shù) n = n0 + n1 + n2 又又 二叉樹上分支總數(shù) b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1 由此，由此， n0 = n2 + 1 。 第17頁(yè)/共26頁(yè) 19 兩類兩類特殊特殊的二叉樹：的二叉樹： 滿二叉樹滿二叉樹：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。 完全二叉樹完

7、全二叉樹：樹中所含的 n 個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)為編號(hào)為 1 至至 n 的結(jié)點(diǎn)的結(jié)點(diǎn)一一對(duì)應(yīng)。 a b c defg hi j 1 23 4567 89101112131415 第18頁(yè)/共26頁(yè) 20 v 性質(zhì)性質(zhì) 4 ： 具有具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的個(gè)結(jié)點(diǎn)的完全二叉樹的深度 為為 log2n +1 。 證明：證明： 設(shè)設(shè)完全二叉樹的深度為 k 則根據(jù)第二條性質(zhì)得 n 2k-1，得n 2k 前k-1層是滿二叉樹，因而2k-1 -1n，得 2k-1 n，從而得到2k-1 n2k 即 k-1 log2 n n，則該結(jié)點(diǎn)無(wú)左孩子， 否則，編號(hào)為 2i 的結(jié)點(diǎn)為其左孩子左孩子結(jié)點(diǎn)； (3) 若 2i+1n，則該結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)， 否則，編號(hào)為2i+1 的結(jié)點(diǎn)為其右孩子右孩子結(jié)點(diǎn)。 1 23 4567 89101112 13 14 15 第21頁(yè)/共26頁(yè) 23 u 二叉樹順序存儲(chǔ)表示二叉樹順序存儲(chǔ)表示 u 二叉樹鏈?zhǔn)酱鎯?chǔ)表示二叉樹鏈?zhǔn)酱鎯?chǔ)表示 第22頁(yè)/共26頁(yè) 24 const MAXSIZE = 100; / 暫定二叉樹的最大結(jié)點(diǎn)數(shù) typedef struct TElemType *data; / 存儲(chǔ)空間基址 int nodenum; /樹中結(jié)點(diǎn)數(shù) SqBiTree ; u 二叉樹順序存儲(chǔ)表示二叉樹順序存儲(chǔ)表示 第23頁(yè)/共26頁(yè) 25 例如例如: :