二叉樹的基本知識

1、SDUT_ACM 培訓(xùn)培訓(xùn)數(shù)據(jù)對象數(shù)據(jù)對象 D：D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。 若若D為空集，則稱為空樹；為空集，則稱為空樹； 否則否則: (1) 在在D中存在唯一的稱為根的數(shù)據(jù)元素中存在唯一的稱為根的數(shù)據(jù)元素root, (2) 當當n1時，其余結(jié)點可分為時，其余結(jié)點可分為m (m0)個互個互 不相交的有限集不相交的有限集T1, T2, , Tm, 其中每一其中每一 棵子集本身又是一棵符合本定義的樹，棵子集本身又是一棵符合本定義的樹， 稱為根稱為根root的子樹。的子樹。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 R：結(jié)點結(jié)點: :結(jié)點的度結(jié)點的度: :樹的度樹的度: :葉子結(jié)點葉

2、子結(jié)點: :分支結(jié)點分支結(jié)點: :數(shù)據(jù)元素+ +若干指向子樹的分支分支的個數(shù)樹中所有結(jié)點的度的最大值度為零的結(jié)點度大于零的結(jié)點DHIJM(從根到結(jié)點的)路徑路徑：孩子孩子結(jié)點、雙親雙親結(jié)點、兄弟兄弟結(jié)點、堂兄弟祖先祖先結(jié)點、子孫子孫結(jié)點結(jié)點的層次結(jié)點的層次: :樹的深度：樹的深度： 由從根根到該結(jié)點所經(jīng)分支和結(jié)點構(gòu)成ABCDEFGHIJMKL假設(shè)根結(jié)點的層次為1,第l 層的結(jié)點的子樹根結(jié)點的層次為l+1樹中葉子結(jié)點所在的最大層次任何一棵非空樹是一個二元組 Tree = （root，F(xiàn)）其中：其中：root 被稱為根結(jié)點， F 被稱為子樹森林森林：森林：是 m（m0）棵互不相交的樹的集合Aroo

3、tBEFKLCGDHIJMF 二叉樹或為空樹空樹；或是由一個根結(jié)根結(jié)點點加上兩棵兩棵分別稱為左子樹左子樹和右子樹的、互不交的互不交的二叉樹二叉樹組成。ABCDEFGHK根結(jié)點左子樹右子樹EFG兩類兩類特殊特殊的二叉樹：的二叉樹：滿二叉樹滿二叉樹：指的是深度為k且含有2k-1個結(jié)點的二叉樹。完全二叉樹完全二叉樹：樹中所含的 n 個結(jié)點和滿二叉樹中編號為編號為 1 至至 n 的結(jié)點的結(jié)點一一對應(yīng)。123456789 10 11 12 13 14 15abcdefghij二叉樹的五種基本形態(tài)：二叉樹的五種基本形態(tài)：NLRLR空樹空樹只含根結(jié)點只含根結(jié)點NNN右子樹右子樹為空樹為空樹左子樹左子樹為空樹

4、為空樹左右子左右子樹均不樹均不為空樹為空樹 二叉樹的主要基本操作二叉樹的主要基本操作：查查 找找 類類插插 入入 類類刪刪 除除 類類 Root(T) / 求樹的根結(jié)點求樹的根結(jié)點 查找類：查找類：Value(T, cur_e) / 求當前結(jié)點的元素值求當前結(jié)點的元素值 Parent(T, cur_e) / 求當前結(jié)點的雙親結(jié)點求當前結(jié)點的雙親結(jié)點LeftChild(T, cur_e) / 求當前結(jié)點的最左孩子求當前結(jié)點的最左孩子 RightSibling(T, cur_e) / 求當前結(jié)點的右兄弟求當前結(jié)點的右兄弟TreeEmpty(T) / 判定樹是否為空樹判定樹是否為空樹 TreeDep

5、th(T) / 求樹的深度求樹的深度TraverseTree( T, Visit() ) / 遍歷遍歷InitTree(&T) / 初始化置空樹初始化置空樹 插入類：插入類：CreateTree(&T, definition) / 按定義構(gòu)造樹按定義構(gòu)造樹Assign(T, cur_e, value) / 給當前結(jié)點賦值給當前結(jié)點賦值InsertChild(&T, &p, i, c) / 將以將以c為根的樹插入為結(jié)點為根的樹插入為結(jié)點p的第的第i棵子樹棵子樹 ClearTree(&T) / 將樹清空將樹清空 刪除類：刪除類：DestroyTree(&am

6、p;T) / 銷毀樹的結(jié)構(gòu)銷毀樹的結(jié)構(gòu)DeleteChild(&T, &p, i) / 刪除結(jié)點刪除結(jié)點p的第的第i棵子樹棵子樹二叉樹二叉樹的重要特性的重要特性 性質(zhì)性質(zhì) 1 ： 在二叉樹的第 i 層上至多有2i-1 個結(jié)點。(i1) 性質(zhì)性質(zhì) 2 ： 深度為 k 的二叉樹上至多含 2k-1 個結(jié)點（k1） 性質(zhì)性質(zhì) 3 ： 對任何一棵二叉樹，若它含有n0 個葉子結(jié)點、n2 個度為 2 的結(jié)點，則必存在關(guān)系式：n0 = n2+1。 性質(zhì)性質(zhì) 4 ： 具有 n 個結(jié)點的完全二叉樹的深度深度為 log2n +1 性質(zhì)性質(zhì) 5若對含 n 個結(jié)點的完全二叉樹從上到下且從左至右進行 1

7、至 n 的編號，則對完全二叉樹中任意一個編號為 i 的結(jié)點： (1) 若 i=1，則該結(jié)點是二叉樹的根，無雙親, 否則，編號為 i/2 的結(jié)點為其雙親雙親結(jié)點; (2) 若 2in，則該結(jié)點無左孩子， 否則，編號為 2i 的結(jié)點為其左孩子左孩子結(jié)點； (3) 若 2i+1n，則該結(jié)點無右孩子結(jié)點， 否則，編號為2i+1 的結(jié)點為其右孩子右孩子結(jié)點二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)二、二叉樹的鏈式二、二叉樹的鏈式 存儲表示存儲表示一、一、 二叉樹的順序二叉樹的順序 存儲表示存儲表示#define MAX_TREE_SIZE 100 / 設(shè)二叉樹的最大結(jié)點數(shù)typedef struct ElemTy

8、pe *data; / 初始化時分配存儲空間 int nodeNum; / 二叉樹中的結(jié)點數(shù)目SqBiTree ;一、一、 二叉樹的順序存儲表示二叉樹的順序存儲表示/ 0 0號單元存儲根結(jié)點號單元存儲根結(jié)點例如例如: A B D 0 1 2 3 4 5 6 7 8 9 10 11 12 13ABCDEF1401326(k+1)2-1 =2k+1CE F二、二叉樹的鏈式存儲表示二、二叉樹的鏈式存儲表示1. . 二叉鏈表二叉鏈表2三叉鏈表三叉鏈表3雙親鏈表雙親鏈表ADEBCF rootlchild data rchild結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu):1. 1. 二叉鏈表二叉鏈表typedef struct /

9、 結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu) TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指針 BiTNode, *BiTree;lchild data rchild結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu):C 語言的類型描述如下語言的類型描述如下: :rootADEBCF 2三叉鏈表三叉鏈表parent lchild data rchild結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu): typedef struct / 結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu) TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指針 struct TriTNode *parent;

10、/雙親指針 TriTNode, *TriTree;parent lchild data rchild結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu):C 語言的類型描述如下語言的類型描述如下: :結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu):3 3雙親鏈表雙親鏈表 data parentABDCEF0B41D42C03E14A-15F36LRTagLRRRL根根n = 6 typedef struct / 結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu) TElemType data; int *parent; / 指向雙親的指針 char LRTag; / 左、右孩子標志域 BPTNode typedef struct / 樹結(jié)構(gòu)樹結(jié)構(gòu) BPTNode nodesMAX_NODE_

11、SIZE; int num_node; / 樹中含結(jié)點數(shù)目 int root; / 根結(jié)點的位置 BPTree樹的三種存儲結(jié)構(gòu)樹的三種存儲結(jié)構(gòu)一、一、雙親表示法雙親表示法二、二、孩子鏈表表示法孩子鏈表表示法三、三、樹的二叉鏈表樹的二叉鏈表( (孩子孩子- -兄弟）兄弟） 存儲表示法存儲表示法ABCDEFGr=0n=60 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5data parent一、雙親表示法一、雙親表示法: typedef struct PTNode Elem data; int parent; / 雙親位置域 PTNode; data parent#defi

12、ne MAX_TREE_SIZE 100結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu):C語言的類型描述語言的類型描述: :typedef struct PTNode nodes MAX_TREE_SIZE; int r, n; / 根結(jié)點的位置和結(jié)點個數(shù) PTree;樹結(jié)構(gòu)樹結(jié)構(gòu):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 4parenttypedef struct CTNode int child; struct CTNode *nextchild; *ChildPtr;孩子結(jié)點結(jié)構(gòu)孩子結(jié)點結(jié)構(gòu): child nextchildC語言的類型描述語言的類型描述: : typedef struct Elem data; ChildPtr firstchild; / 孩子鏈的頭指針 CTBox;雙親結(jié)點結(jié)構(gòu)雙親結(jié)點結(jié)構(gòu) data firstchildtypedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 結(jié)點數(shù)和根結(jié)點的位置 CTree;樹結(jié)構(gòu)樹結(jié)構(gòu):ABCDEFGroot AB C E D F G AB