【正文】 Data Structure— Ch5 Tree 2022/1/4 mayan 第五章 樹 ?樹 ?二叉樹 ?線索二叉樹 ?樹與森林 ?堆 ?Huffman樹 Data Structure— Ch5 Tree 2022/1/4 mayan 樹 樹的定義和術語 ? 兩種樹：自由樹與有根有序樹 。 ? 自由樹： 一棵自由樹 Tf 可定義為一個二元組 Tf = (V, E)，其中 V = {v1, ..., vn} 是由 n (n＞ 0) 個元素組成的有限非空集合，稱為頂點（ vertex）集合。E = {(vi, vj) | vi, vj V, 1≤i, j≤n} 是 n1個序?qū)Φ募?，稱為邊集合， E 中的元素 (vi, vj）稱為邊（ edge）或分支。 Data Structure— Ch5 Tree 2022/1/4 mayan 樹 樹的定義和術語 ? 有根樹 ：一棵有根樹 T， 簡稱為樹 ， 它是 n (n≥0) 個結(jié)點的有限集合 。 當 n = 0時 ， T 稱為 空樹 ；否則 ， T 是 非空樹 ， 記作 其中 ， r 是一個特定的稱為 根 (root)的結(jié)點 ， 它沒有直接前驅(qū)；根以外的其他結(jié)點劃分為 m (m ≥0) 個互不相交的有限集合 T1, T2, … , Tm， 每個集合又是一棵樹 ， 并且稱之為根的 子樹 。 ??????00n,T,... ,T,Tr,n,Tm21 }{ΦData Structure— Ch5 Tree 2022/1/4 mayan 樹 樹的定義和術語 ? 相關術語 ? 子女 ：若結(jié)點的子樹非空 ， 結(jié)點子樹的根即為該結(jié)點的子女 。 ? 雙親： 若結(jié)點有子女 ， 該結(jié)點是子女雙親 。 ? 兄弟 ：同一結(jié)點的子女互稱為兄弟 。 ? 度： 結(jié)點的子女個數(shù)即為該結(jié)點的度；樹中各個結(jié)點的度的最大值稱為 樹的度 。 ? 分支結(jié)點： 度不為 0的結(jié)點即為分支結(jié)點 ， 亦稱為非終端結(jié)點 。 AB C DE F G H I JK L M1 層2 層3 層4 層d e p t h h e i g h tData Structure— Ch5 Tree 2022/1/4 mayan 樹 樹的定義和術語 ?葉結(jié)點 ：度為 0的結(jié)點即為葉結(jié)點，亦稱為終端結(jié)點。 ?祖先 ：某結(jié)點到根結(jié)點的路徑上的各個結(jié)點都是該結(jié)點的祖先。 ?子孫 ：某結(jié)點的所有下屬結(jié)點，都是該結(jié)點的子孫。 ?結(jié)點的層次 ：規(guī)定根結(jié)點在第一層，其子女結(jié)點的層次等于它的層次加一。以此類推。 ?深度 ：結(jié)點的深度即為結(jié)點的層次；離根最遠結(jié)點的層次即為 樹的深度 。 AB C DE F G H I JK L M1 層2 層3 層4 層d e p t h h e i g h tData Structure— Ch5 Tree 2022/1/4 mayan 樹 樹的定義和術語 ?高度 ：規(guī)定葉結(jié)點的高度為 1，其雙親結(jié)點的高度等于它的高度加一。 ?樹的高度 ：等于根結(jié)點的高度，即根結(jié)點所有子女高度的最大值加一。 ?有序樹 ：樹中結(jié)點的各棵子樹 T0, T1, … 是有次序的，即為有序樹。 ?無序樹 ：樹中結(jié)點的各棵子樹之間的次序是不重要的，可以互相交換位置。 ?森林 ：森林是 m（ m≥0）棵樹的集合。 AB C DE F G H I JK L M1 層2 層3 層4 層d e p t h h e i g h tData Structure— Ch5 Tree 2022/1/4 mayan 樹 樹的抽象數(shù)據(jù)類型 template class T class Tree { //在類界面中的 position 是樹中結(jié)點的地址。在順序 //存儲方式下是下標型 , 在鏈表存儲方式下是指針型 public: Tree ()。 ~Tree ()。 position Root()。 BuildRoot (const Tamp。 value)。 //建立樹的根結(jié)點 Data Structure— Ch5 Tree 2022/1/4 mayan 樹 樹的抽象數(shù)據(jù)類型 position FirstChild(position p)。 //返回 p 第一個子女地址 , 無子女返回 0 position NextSibling(position p)。 //返回 p 下一兄弟地址 , 若無下一兄弟返回 0 position Parent(position p)。 //返回 p 雙親結(jié)點地址 , 若 p 為根返回 0 T getData(position p)。 //返回結(jié)點 p 中存放的值 bool InsertChild(const position p, const Tamp。 value)。 //在結(jié)點 p 下插入值為 value 的新子女 , 若插 //入失敗 , 函數(shù)返回 false, 否則返回 true Data Structure— Ch5 Tree 2022/1/4 mayan 樹 樹的抽象數(shù)據(jù)類型 bool DeleteChild (position p, int i)。 //刪除結(jié)點 p 的第 i 個子女及其全部子孫結(jié) //點 , 若刪除失敗 , 則返回 false, 否則返回 true void DeleteSubTree (position t)。 //刪除以 t 為根結(jié)點的子樹 bool IsEmpty ()。 //判樹空否 , 若空則返回 true, 否則返回 false void Traversal (void (*visit)(position p))。 //遍歷以 p 為根的子樹 }。 Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉樹的定義 ? 一棵二叉樹是結(jié)點的一個有限集合，該集合或者為空，或者是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。 ??????0},{0nTTrnTRL?TLTRTLTR二 叉 樹 的 五 種 不 同 形 態(tài)Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉樹的性質(zhì) ? 性質(zhì) 1 若二叉樹結(jié)點的層次從 1 開始 , 則在二叉樹的第 i (i≥1)層最多有 2i1 個結(jié)點 。 [證明用數(shù)學歸納法 ] ? 性質(zhì) 2 深度為 k (k≥ 0) 的二叉樹最少有 k 個結(jié)點 ，最多有 2k1個結(jié)點 。 ? 證明：因為每一層最少要有 1個結(jié)點 ， 因此 ， 最少結(jié)點數(shù)為 k。 最多結(jié)點個數(shù)借助性質(zhì) 1用求等比級數(shù)前 k項和的公式 20 +21 +22 + … +2k1 = 2k1 Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉樹的性質(zhì) ? 性質(zhì) 3 對任何一棵二叉樹 ， 如果其葉結(jié)點有 n0 個 , 度為 2 的非葉結(jié)點有 n2 個 , 則有 n0＝ n2＋ 1 證明：若設度為 1 的結(jié)點有 n1 個 ， 總結(jié)點數(shù)為 n，總邊數(shù)為 e， 則根據(jù)二叉樹的定義 ， n = n0+n1+n2 , e = 2n2+n1 = n1 因此 ， 有 2n2+n1 = n0+n1+n21則 n2 = n01 ? n0 = n2+1 Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉樹的性質(zhì) ? 定義 1 滿二叉樹 (Full Binary Tree) ：深度為 k的滿二叉樹是有 2k1個結(jié)點的二叉樹 。 ? 定義 2 完全二叉樹 (Complete Binary Tree)：若設二叉樹的深度為 k， 則共有 k 層 。 除第 k 層外 ，其它各層 (1～ k1) 的結(jié)點數(shù)都達到最大個數(shù) ， 第 k層從右向左連續(xù)缺若干結(jié)點 ， 這就是完全二叉樹 。 12 34 65 78 91 0 1 1 1 2 1 3 1 4 1 5滿 二 叉 樹12 34 65 78 91 0完 全 二 叉 樹Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉樹的性質(zhì) ? 性質(zhì) 4 具有 n (n≥0) 個結(jié)點的完全二叉樹的深度為 ?log2(n+1)?。 證明： 設完全二叉樹的深度為 k， 則有 2k11 n ≤ 2k1 即 2k1 n+1≤2k ， 取對數(shù) k1 log2(n+1) ≤k 有 k= ?log2(n+1)? 12 34 65 78 91 023 124 1Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉樹的性質(zhì) ? 性質(zhì) 5 如將一棵有 n個結(jié)點的完全二叉樹自頂向下 ，同一層自左向右連續(xù)給結(jié)點編號 1, 2, … , n， 則有以下關系： 1) 若 i == 1, 則 i 無雙親； 2) 若 i 1, 則 i 的雙親為 ?i／ 2」 ； 3) 若 2*i = n, 則 i 的左子女為 2*i； 4) 若 2*i+1 = n, 則 i 的右子女為 2*i+1； 5) 若 i 為奇數(shù) , 且 i != 1, 則其左兄弟為 i1； 6) 若 i 為偶數(shù) , 且 i != n, 則其右兄弟為 i+1； 7) 結(jié)點 i 所在的層次為 ?log2i」 +1 12 34 65 78 91 0Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉樹的抽象數(shù)據(jù)類型 template class T class BinaryTree { public: BinaryTree ()。 //構(gòu)造函數(shù) BinaryTree (BinTreeNodeT *lch, BinTreeNodeT *rch, T item)。 //構(gòu)造函數(shù) , 以 item為根 , lch和 rch為左、 //右子樹構(gòu)造一棵二叉樹 int Height ()。 //求樹深度或高度 int Size ()。 //求樹中結(jié)點個數(shù) Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉樹的抽象數(shù)據(jù)類型 bool IsEmpty ()。 //判二叉樹空否？ BinTreeNodeT *Parent (BinTreeNodeT *current)。//求結(jié)點 current的雙親 BinTreeNodeT *LeftChild (BinTreeNodeT *current)。 //求結(jié)點 current 的左子女 BinTreeNodeT *RightChild (BinTreeNodeT *current)。 //求結(jié)點 current 的右子女 bool Insert (T item)。 //在樹中插入新元素 bool Remove (T item)。 //在樹中刪除元素 bool Find (const Tamp。 item)const。 //判斷 item是否在樹中 Data Structure— Ch5 Tree 2022/1/4 mayan 二叉樹 二叉樹的抽象數(shù)據(jù)類型 bool getData (const Tamp。 item) const。 //取得結(jié)點數(shù)據(jù) BinTreeNodeT *getRoot ()const。 //取根 void preOrder (void (*visit) (BinTreeNodeT *p))。 //前序遍歷 , visit是訪問函數(shù) void inOrder (void (*visit) (BinTreeNodeT *p))。 //中序遍歷 , visit是訪問函數(shù) void postOrder (void (*visit) (BinTreeNodeT *p))。 //后序遍歷 , (*visit)是訪問函數(shù)