1、會計學1 節節 二叉樹和樹二叉樹和樹 2 第1頁/共26頁 3 第2頁/共26頁 4 線性結構樹型結構 第一個數據元素 (無前驅) 根結點 (無前驅) 最后一個數據元素 (無后繼) 多個葉子結點 (無后繼) 其它數據元素 (一個前驅、 一個后繼) 其它數據元素 (一個前驅、 多個后繼) 對比對比樹型結構樹型結構和和線性結構線性結構的結構特的結構特 點點 第3頁/共26頁 5 結點結點: :數據元素+ +若干指向子樹的分支 結點的度結點的度: :分支的個數 樹的度樹的度: :樹中所有結點的度的最大值 葉子結點葉子結點: :度為零的結點 分支結點分支結點: :度大于零的結點 D HIJ M 基本術

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

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

4、刪刪 除除 類類 的的 操操 作作 第10頁/共26頁 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頁/共26頁 13 InitBiTree( A

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

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

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