二叉樹的基本知識

1、數(shù)據(jù)對象 D：D是具有一樣特性的數(shù)據(jù)元素的集合。 假設(shè)D為空集，那么稱為空樹； 否那么: (1) 在D中存在唯一的稱為根的數(shù)據(jù)元素root, (2) 當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為m (m0)個(gè)互 不相交的有限集T1, T2, , Tm, 其中每一 棵子集本身又是一棵符合本定義的樹， 稱為根root的子樹。 數(shù)據(jù)關(guān)系 R：第二頁，共36頁。結(jié)點(diǎn):結(jié)點(diǎn)的度:樹的度:葉子結(jié)點(diǎn):分支結(jié)點(diǎn):數(shù)據(jù)元素+假設(shè)干指向子樹的分支分支的個(gè)數(shù)樹中所有結(jié)點(diǎn)的度的最大值度為零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)DHIJM第三頁，共36頁。(從根到結(jié)點(diǎn)的)途徑：孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)、兄弟結(jié)點(diǎn)、堂兄弟祖先結(jié)點(diǎn)、子孫結(jié)點(diǎn)結(jié)點(diǎn)的層次:樹的深度： 由

2、從根到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成ABCDEFGHIJMKL假設(shè)根結(jié)點(diǎn)的層次為1,第l 層的結(jié)點(diǎn)的子樹根結(jié)點(diǎn)的層次為l+1樹中葉子結(jié)點(diǎn)所在的最大層次第四頁，共36頁。任何一棵非空樹是一個(gè)二元組 Tree = root，F(xiàn)其中：root 被稱為根結(jié)點(diǎn)， F 被稱為子樹森林森林：是 mm0棵互不相交的樹的集合ArootBEFKLCGDHIJMF第五頁，共36頁。 二叉樹或?yàn)榭諛?；或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。ABCDEFGHK根結(jié)點(diǎn)左子樹右子樹EFG第六頁，共36頁。兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。完全二叉樹：樹中所含的

3、n 個(gè)結(jié)點(diǎn)和滿二叉樹中編號為 1 至 n 的結(jié)點(diǎn)一一對應(yīng)。123456789 10 11 12 13 14 15abcdefghij第七頁，共36頁。二叉樹的五種根本形態(tài)：NLRLR空樹只含根結(jié)點(diǎn)NNN右子樹為空樹左子樹為空樹左右子樹均不為空樹第八頁，共36頁。 二叉樹的主要根本操作：查 找 類插 入 類刪 除 類第九頁，共36頁。 Root(T) / 求樹的根結(jié)點(diǎn) 查找類：Value(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的元素值 Parent(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)LeftChild(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的最左孩子 RightSibling(T, cur_e

4、) / 求當(dāng)前結(jié)點(diǎn)的右兄弟TreeEmpty(T) / 斷定樹是否為空樹 TreeDepth(T) / 求樹的深度TraverseTree( T, Visit() ) / 遍歷第十頁，共36頁。InitTree(&T) / 初始化置空樹 插入類：CreateTree(&T, definition) / 按定義構(gòu)造樹Assign(T, cur_e, value) / 給當(dāng)前結(jié)點(diǎn)賦值InsertChild(&T, &p, i, c) / 將以c為根的樹插入為結(jié)點(diǎn)p的第i棵子樹第十一頁，共36頁。 ClearTree(&T) / 將樹清空 刪除類：DestroyTree(&T) / 銷毀樹的構(gòu)造De

5、leteChild(&T, &p, i) / 刪除結(jié)點(diǎn)p的第i棵子樹第十二頁，共36頁。二叉樹的重要特性第十三頁，共36頁。 性質(zhì) 1 ： 在二叉樹的第 i 層上至多有2i-1 個(gè)結(jié)點(diǎn)。(i1) 性質(zhì) 2 ： 深度為 k 的二叉樹上至多含 2k-1 個(gè)結(jié)點(diǎn)k1 性質(zhì) 3 ： 對任何一棵二叉樹，假設(shè)它含有n0 個(gè)葉子結(jié)點(diǎn)、n2 個(gè)度為 2 的結(jié)點(diǎn)，那么必存在關(guān)系式：n0 = n2+1。第十四頁，共36頁。 性質(zhì) 4 ： 具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2n +1 性質(zhì) 5 假設(shè)對含 n 個(gè)結(jié)點(diǎn)的完全二叉樹從上到下且從左至右進(jìn)展 1 至 n 的編號，那么對完全二叉樹中任意一個(gè)編號為 i

6、 的結(jié)點(diǎn)： (1) 假設(shè) i=1，那么該結(jié)點(diǎn)是二叉樹的根，無雙親, 否那么，編號為 i/2 的結(jié)點(diǎn)為其雙親結(jié)點(diǎn); (2) 假設(shè) 2in，那么該結(jié)點(diǎn)無左孩子， 否那么，編號為 2i 的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)； (3) 假設(shè) 2i+1n，那么該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)， 否那么，編號為2i+1 的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)第十五頁，共36頁。二叉樹的存儲構(gòu)造二、二叉樹的鏈?zhǔn)?存儲表示一、 二叉樹的順序 存儲表示第十六頁，共36頁。#define MAX_TREE_SIZE 100 / 設(shè)二叉樹的最大結(jié)點(diǎn)數(shù)typedef struct ElemType *data; / 初始化時(shí)分配存儲空間 int nodeNum;

7、/ 二叉樹中的結(jié)點(diǎn)數(shù)目SqBiTree ;一、 二叉樹的順序存儲表示/ 0號單元存儲根結(jié)點(diǎn)第十七頁，共36頁。例如: A B D 0 1 2 3 4 5 6 7 8 9 10 11 12 13ABCDEF1401326(k+1)2-1 =2k+1CE F第十八頁，共36頁。二、二叉樹的鏈?zhǔn)酱鎯Ρ硎?. 二叉鏈表2三叉鏈表3雙親鏈表第十九頁，共36頁。ADEBCF rootlchild data rchild結(jié)點(diǎn)構(gòu)造:1. 二叉鏈表第二十頁，共36頁。typedef struct / 結(jié)點(diǎn)構(gòu)造 TElemType data; struct BiTNode *lchild, *rchild; /

8、左右孩子指針 BiTNode, *BiTree;lchild data rchild結(jié)點(diǎn)構(gòu)造:C 語言的類型描繪如下:第二十一頁，共36頁。rootADEBCF 2三叉鏈表parent lchild data rchild結(jié)點(diǎn)構(gòu)造:第二十二頁，共36頁。 typedef struct / 結(jié)點(diǎn)構(gòu)造 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指針 struct TriTNode *parent; /雙親指針 TriTNode, *TriTree;parent lchild data rchild結(jié)點(diǎn)構(gòu)造:C 語言的類型描繪如下

9、:第二十三頁，共36頁。結(jié)點(diǎn)構(gòu)造:3雙親鏈表 data parentABDCEF0 B41 D42 C03 E14 A -15 F36LRTagLRRRL根根n = 6第二十四頁，共36頁。 typedef struct / 結(jié)點(diǎn)構(gòu)造 TElemType data; int *parent; / 指向雙親的指針 char LRTag; / 左、右孩子標(biāo)志域 BPTNode typedef struct / 樹構(gòu)造 BPTNode nodesMAX_NODE_SIZE; int num_node; / 樹中含結(jié)點(diǎn)數(shù)目 int root; / 根結(jié)點(diǎn)的位置 BPTree第二十五頁，共36頁。樹的三

10、種存儲構(gòu)造一、雙親表示法二、孩子鏈表表示法三、樹的二叉鏈表(孩子-兄弟 存儲表示法第二十六頁，共36頁。ABCDEFGr=0n=60 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5data parent一、雙親表示法:第二十七頁，共36頁。 typedef struct PTNode Elem data; int parent; / 雙親位置域 PTNode; data parent#define MAX_TREE_SIZE 100結(jié)點(diǎn)構(gòu)造:C語言的類型描繪:第二十八頁，共36頁。typedef struct PTNode nodes MAX_TREE_SIZE; in

11、t r, n; / 根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù) PTree;樹構(gòu)造:第二十九頁，共36頁。r=0n=6 data firstchildABCDEFG0 A -11 B 02 C 03 D 04 E 25 F 26 G 464 5 1 2 3二、孩子鏈表表示法:-1 0 0 0 2 2 4parent第三十頁，共36頁。typedef struct CTNode int child; struct CTNode *nextchild; *ChildPtr;孩子結(jié)點(diǎn)構(gòu)造: child nextchildC語言的類型描繪:第三十一頁，共36頁。 typedef struct Elem data; ChildPtr firstchild; / 孩子鏈的頭指針 CTBox;雙親結(jié)點(diǎn)構(gòu)造 data firstchild第三十二頁，共36頁。typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置 CTree;樹構(gòu)造:第三十三頁，共36頁。ABCDEFGroot AB C E D F G AB C E D F G 三、樹的二叉