樹和森林的概念二叉樹二叉樹的表示二叉樹遍歷及其應(yīng)用課件

1、樹和森林的概念二叉樹二叉樹的表示二叉樹遍歷及其應(yīng)用樹和森林的概念二叉樹二叉樹的表示二叉樹遍歷及其應(yīng)用樹和森林的概念兩種樹：自由樹與有根樹。 自由樹： 一棵自由樹 Tf 可定義為一個(gè)二元組 Tf = (V, E) 其中V = v1, ., vn 是由 n (n0) 個(gè)元素組成的有限非空集合，稱為頂點(diǎn)集合。E = (vi, vj) | vi, vj V, 1i, jn 是n-1個(gè)序?qū)Φ募?，稱為邊集合，E 中的元素 (vi, vj）稱為邊或分支。樹和森林的概念兩種樹：自由樹與有根樹。 自由樹自由樹 r 是一個(gè)特定的稱為根(root)的結(jié)點(diǎn)，它只有直接后繼，但沒(méi)有直接前驅(qū)；根以外的其他結(jié)點(diǎn)劃分為 m

2、 (m 0) 個(gè)互不相交的有限集合T1, T2, , Tm，每個(gè)集合又是一棵樹，并且稱之為根的子樹。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或多個(gè)直接后繼。有根樹：一棵有根樹 T，簡(jiǎn)稱為樹，它是n (n0) 個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n = 0時(shí)，T 稱為空樹；否則，T 是非空樹，記作 r 是一個(gè)特定的稱為根(root)的結(jié)點(diǎn)，它只有直接后繼，樹的示意圖（P.187）樹的示意圖（P.187）樹的特點(diǎn)每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或多個(gè)直接后繼。0層1層3層2層height= 3ACGBDEFKLHMIJ樹的特點(diǎn)每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或0層1層

3、3層2層height= 3ACGBDEFKLHMIJ結(jié)點(diǎn)結(jié)點(diǎn)的度分支結(jié)點(diǎn)葉結(jié)點(diǎn)子女雙親兄弟祖先子孫結(jié)點(diǎn)層次樹的度樹高度森林術(shù)語(yǔ)0層1層3層2層heightACGBDEFKLHMIJ結(jié)點(diǎn)子template class Tree public: Tree ( ); Tree ( ); position Root ( ); BuildRoot ( const Type& value ); position FirstChild ( position p ); position NextSibling ( position p ); position Parent ( position p ); Ty

4、pe GetData ( position p ); int InsertChild ( const position p, const Type &value ); int DeleteChild ( position p, int i );樹的抽象數(shù)據(jù)類型template class Tr一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。 5.2 二叉樹 (Binary Tree)二叉樹的定義一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)二叉樹的五種不同形態(tài)LLRR二叉樹的五種不同形態(tài)LLRR性質(zhì)1 若二

5、叉樹的層次從1開始, 則在二叉樹的第 i 層最多有 2i -1個(gè)結(jié)點(diǎn)。(i 1) 性質(zhì)2 深度為 k 的二叉樹最多有 2k-1個(gè)結(jié)點(diǎn)。k 0二叉樹的性質(zhì)性質(zhì)1 若二叉樹的層次從1開始, 則在二叉樹的第 i 層性質(zhì)3 對(duì)任何一棵二叉樹, 如果其葉結(jié)點(diǎn)有 n0 個(gè), 度為2的非葉結(jié)點(diǎn)有 n2 個(gè), 則有 n0n21證明：若設(shè)度為1的結(jié)點(diǎn)有 n1 個(gè)，總結(jié)點(diǎn)個(gè)數(shù)為 n，總邊數(shù)為 e，則根據(jù)二叉樹的定義， n = n0 + n1 + n2 e = n - 1 =2n2 + n1 =因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1 性質(zhì)3

6、對(duì)任何一棵二叉樹, 如果其葉結(jié)點(diǎn)有 n0 個(gè), 度定義1 滿二叉樹 (Full Binary Tree) 如果二叉樹中所有分支結(jié)點(diǎn)的度數(shù)都為2，且葉子結(jié)點(diǎn)都在同一層次上，則稱這類二叉樹為滿二叉樹。定義2 完全二叉樹 (Complete Binary Tree)如果一棵具有n個(gè)結(jié)點(diǎn)的高度為k的二叉樹，它的每一個(gè)結(jié)點(diǎn)都與高度為k的滿二叉樹中編號(hào)為1-n結(jié)點(diǎn)一一對(duì)應(yīng)，則稱這棵二叉樹為完全二叉樹。（從上到下從左到右編號(hào)）定義1 滿二叉樹 (Full Binary Tree) 定滿二叉樹 完全二叉樹 層次h，葉結(jié)點(diǎn)僅在 兩層出現(xiàn) 對(duì)任一結(jié)點(diǎn)，若其右子樹的高度為k，則其左子樹的高度是 h和h-1 k or

7、 k+1滿二叉樹 性質(zhì)4 具有 n (n 0) 個(gè)結(jié)點(diǎn)的完全二叉樹的高度為 log2(n+1) 23-124-1 性質(zhì)4 具有 n (n 0) 個(gè)結(jié)點(diǎn)的完全二叉樹的高性質(zhì)5 如將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹自頂向下，同一層自左向右連續(xù)給結(jié)點(diǎn)編號(hào) 1, 2, , n，則有以下關(guān)系： (1)若i =1, 則 i 為根，無(wú)雙親 若i 1, 則 i 的雙親為i/2(2)若n =2*i, 則結(jié)點(diǎn)i 的左子女為 2*i; (3)若n=2*i+1, 則結(jié)點(diǎn)i 的右子女為2*i+112348567910性質(zhì)5 如將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹自頂向下，同一層自左（4）若結(jié)點(diǎn)編號(hào)i為奇數(shù)，且i!=1,則它的左兄弟為

8、結(jié)點(diǎn)i-1。（5）若結(jié)點(diǎn)編號(hào)i為偶數(shù)，且i!=n,則它的右兄弟為結(jié)點(diǎn)i+1。（6）結(jié)點(diǎn)i所在層次為log2i+112348567910（4）若結(jié)點(diǎn)編號(hào)i為奇數(shù)，且i!=1,則它的左兄弟為結(jié)點(diǎn)i-template class BinaryTree public: BinaryTree ( ); /構(gòu)造函數(shù) BinaryTree ( BinTreeNode * lch, BinTreeNode * rch, Type item ); /構(gòu)造以item為根，lch和rch為左、右 /子樹的二叉樹 int IsEmpty ( ); /判二叉樹空否？ BinTreeNode * Parent ( );

9、/雙親 二叉樹的抽象數(shù)據(jù)類型template class Bi BinTreeNode * LeftChild ( ); /取左子女結(jié)點(diǎn)地址 BinTreeNode * RightChild ( ); /取右子女結(jié)點(diǎn)地址 int Insert ( const Type& item ); /插入 int Find ( const Type &item ) const; /搜索 Type GetData ( ) const; /取得結(jié)點(diǎn)數(shù)據(jù) BinTreeNode *GetRoot ( ) const; /取根結(jié)點(diǎn)地址 BinTreeNode * LeftCh0 1 2 3 4 5 6 7 8 9

10、 完全二叉樹01378945625.3 二叉樹的存儲(chǔ)表示順序表示0 1 2 3 4 5 6 7 8 9 完全二叉樹013780 1 2 3 5 6 7 8 9 11 13一般二叉樹的順序表示1302653781110 1 2 3 5 6 7 8 9 11 130261430極端情形: 只有右單支的二叉樹02614300261430極端情形: 只有右單支的二叉樹0261430leftChild data rightChilddataleftChildrightChild二叉鏈表二叉樹的鏈表表示leftChild data rightChilddleftChild data parent righ

11、tChildparentdataleftChildrightChild三叉鏈表leftChild data parent ri二叉樹鏈表表示的示例ABCDFErootAABBCCDDFFEErootroot 二叉鏈表 三叉鏈表二叉樹鏈表表示的示例ABCDFEroot二叉鏈表的靜態(tài)結(jié)構(gòu)ABCDFErootdata parent leftChild rightChild012345A -1 1 -1B 0 2 3C 1 -1 -1D 1 4 5E 3 -1 -1F 3 -1 -1二叉鏈表的靜態(tài)結(jié)構(gòu)ABCDFErootdata parentemplate class BinaryTree;templ

12、ate Class BinTreeNode friend class BinaryTree;private: Type data; BinTreeNode * leftChild; BinTreeNode * rightChild; public: BinTreeNode ( ) : leftChild (NULL), rightChild (NULL) 二叉樹的類定義template class Bi BinTreeNode ( Type item, BinTreeNode *left = NULL, BinTreeNode *right = NULL ) : data (item), le

13、ftChild (left), rightChild (right) Type GetData ( ) const return data; BinTreeNode * GetLeft ( ) const return leftChild; BinTreeNode * GetRight ( ) const return rightChild; void SetData ( const Type& item ) data = item; BinTreeNode ( Type item, void SetLeft ( BinTreeNode * L ) leftChild = L; void Se

14、tRight ( BinTreeNode * R ) rightChild = R; ;template class BinaryTree private: BinTreeNode *root; Type RefValue; void CreateBinTree ( ifstream& in, BinTreeNode * & current ); void SetLeft ( BinTreeNode BinTreeNode * Parent ( BinTreeNode * subTree, BinTreeNode * current); int Insert (BinTreeNode * &

15、subTree, const Type &item); /插入 void Traverse (BinTreeNode *subTree, ostream &out) const /遍歷 int Find (BinTreeNode *subTree, const Type &item) const/搜索 void destroy (BinTreeNode * subTree); /刪除 BinTreeNode * Parent樹的遍歷: 按某種次序訪問(wèn)樹中的結(jié)點(diǎn)，要求每個(gè)結(jié)點(diǎn)訪問(wèn)一次且僅訪問(wèn)一次。 設(shè)訪問(wèn)根結(jié)點(diǎn)記作 V， 遍歷根的左子樹記作 L， 遍歷根的右子樹記作 R 5.4 二叉樹遍歷樹的遍

16、歷: 按某種次序訪問(wèn)樹中的結(jié)點(diǎn)，要求每個(gè)則可能的遍歷次序有: VLR VRL LVR RVL LRV RLV 前序 鏡像 中序 鏡像 后序 鏡像則可能的遍歷次序有: 前序 中序遍歷 (Inorder Traversal)-/+*abcdef遍歷結(jié)果: a + b * c - d - e / fLVR中序遍歷 (Inorder Traversal)-/+*a中序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則中序遍歷左子樹 (L)；訪問(wèn)根結(jié)點(diǎn) (V)；中序遍歷右子樹 (R)。中序遍歷二叉樹算法的框架是：二叉樹遞歸的中序遍歷算法template void BinaryTree : InOrde

17、r ( BinTreeNode *subTree ) if ( subTree != NULL ) InOrder ( subTree-leftChild ); cout data; InOrder ( subTree-rightChild ); 二叉樹遞歸的中序遍歷算法前序遍歷 (Preorder Traversal)-/+*abcdef遍歷結(jié)果: - + a * b - c d / e fVLR前序遍歷 (Preorder Traversal)-/+*前序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則訪問(wèn)根結(jié)點(diǎn) (V)；前序遍歷左子樹 (L)；前序遍歷右子樹 (R)。前序遍歷二叉樹算

18、法的框架是：二叉樹遞歸的前序遍歷算法template void BinaryTree :PreOrder ( BinTreeNode * subTree ) if ( subTree != NULL ) cout data; PreOrder ( subTree-leftChild ); PreOrder ( subTree-rightChild ); 二叉樹遞歸的前序遍歷算法后序遍歷 (Postorder Traversal)-/+*abcdef遍歷結(jié)果: a b c d - * + e f / - LRV后序遍歷 (Postorder Traversal)-/+后序遍歷二叉樹算法的框架是：

19、若二叉樹為空，則空操作；否則后序遍歷左子樹 (L)；后序遍歷右子樹 (R)；訪問(wèn)根結(jié)點(diǎn) (V)。后序遍歷二叉樹算法的框架是：二叉樹遞歸的后序遍歷算法template void BinaryTree :PostOrder ( BinTreeNode * subTree ) if ( subTree != NULL ) PostOrder ( subTree-leftChild ); PostOrder ( subTree-rightChild ); cout data; 二叉樹遞歸的后序遍歷算法template void BinaryTree : InOrder ( ) InOrder ( ro

20、ot );template void BinaryTree : PreOrder ( ) PreOrder ( root );template void BinaryTree : PostOrder ( ) PostOrder ( root );template 關(guān)于樹的性質(zhì)：1. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹，該樹中所有結(jié)點(diǎn)的度數(shù)之和為： 2. 假定一棵三叉樹的結(jié)點(diǎn)個(gè)數(shù)為50，則它的最小高度為 ，最大高度為 。3. 在一棵二叉樹中，假定度為2的結(jié)點(diǎn)有5個(gè)，度為1的結(jié)點(diǎn)有6個(gè)，則葉子結(jié)點(diǎn)數(shù)有 個(gè)n-14496 n2+1=n0關(guān)于樹的性質(zhì)：n-14496 n2+11. 利用二叉樹后序遍歷計(jì)算二叉樹結(jié)

21、點(diǎn)個(gè)數(shù)template int BinaryTree : Count ( BinTreeNode * t ) const if ( t = NULL ) return 0; else return 1 + Count ( t-leftChild ) + Count ( t-rightChild );應(yīng)用二叉樹遍歷的實(shí)例1. 利用二叉樹后序遍歷計(jì)算二叉樹結(jié)點(diǎn)個(gè)數(shù)template 遍歷順序abcdef-+/*層次序遍歷二叉樹的算法層次序遍歷二叉樹就是從根結(jié)點(diǎn)開始，按層次逐層遍歷遍歷順序abcdef-+/*層次序遍歷二叉樹的算法層次序遍這種遍歷需要使用一個(gè)先進(jìn)先出的隊(duì)列，在處理上一層時(shí)，將其下一層的

22、結(jié)點(diǎn)直接進(jìn)到隊(duì)列（的隊(duì)尾）。在上一層結(jié)點(diǎn)遍歷完后，下一層結(jié)點(diǎn)正好處于隊(duì)列的隊(duì)頭，可以繼續(xù)訪問(wèn)它們。算法是非遞歸的。這種遍歷需要使用一個(gè)先進(jìn)先出的隊(duì)列，在處理上一層時(shí)，將其下一abcdeQa訪問(wèn)a, 進(jìn)隊(duì)Qa出隊(duì)訪問(wèn)b, 進(jìn)隊(duì)訪問(wèn)c, 進(jìn)隊(duì)bcQb出隊(duì)訪問(wèn)d, 進(jìn)隊(duì)cdQc出隊(duì)訪問(wèn)e, 進(jìn)隊(duì)deQd出隊(duì)eQe出隊(duì)abcdeQa訪問(wèn)a, 進(jìn)隊(duì)Qa出隊(duì)bcQb出隊(duì)cdQc出隊(duì)層次序遍歷的（非遞歸）算法template void BinaryTree:levelOrder (void (*visit) (BinTreeNode *t) if (root = NULL) return; QueueBin

23、TreeNode * Q; BinTreeNode *p = root; visit (p); Q.EnQueue (p); while (!Q.IsEmpty () Q.DeQueue (p); if (p-leftChild != NULL) visit (p-leftChild); Q.EnQueue (p-leftChild); if (p-rightChild != NULL) visit (p-rightChild); Q.EnQueue (p-rightChild); ; 層次序遍歷的（非遞歸）算法template class T二叉樹的建立通過(guò)算法遞歸地實(shí)現(xiàn)已知一棵二叉樹的前序

24、序列和中序序列，可以唯一地確定一棵二叉樹；已知一棵二叉樹的中序序列和后序序列，可以唯一地確定一棵二叉樹；二叉樹的建立通過(guò)算法遞歸地實(shí)現(xiàn)5.5 線索二叉樹5.5 線索二叉樹線索 (Thread)：指示前驅(qū)和后繼的指針線索化二叉樹（Threaded Binary Tree）:加了線索的二叉樹線索 (Thread)：指示前驅(qū)和后繼的指針線索化二叉樹（T兩種方法：1）原有二叉樹的結(jié)構(gòu)中，增加兩個(gè)鏈域；2）利用空鏈域 如果結(jié)點(diǎn)有左孩子，則其leftchild指示其左孩子；否則指示其前驅(qū)如果結(jié)點(diǎn)有右孩子，則其rightchild指示其右孩子；否則指示其后繼設(shè)置兩個(gè)標(biāo)志：LeftThread RightTh

25、read兩種方法： 如果結(jié)點(diǎn)有左孩子，則其leftchild指示其左線索化二叉樹及其二叉鏈表表示LeftThread=0, LeftChild為左子女指針LeftThread=1, LeftChild為前驅(qū)線索RightThread=0, RightChild為右子女指針RightThread=1, RightChild為后繼指針LeftChildRightChilddataLeftThreadRightThread線索化二叉樹及其二叉鏈表表示LeftThread=0, 中序線索化二叉樹的例子中序線索化二叉樹的例子帶表頭結(jié)點(diǎn)的中序穿線鏈表原來(lái)的線索化二叉樹成為表頭結(jié)點(diǎn)的左子樹帶表頭結(jié)點(diǎn)的中序穿

26、線鏈表原來(lái)的線索化二叉樹成為表頭結(jié)點(diǎn)的左子template class ThreadNode friend class ThreadTree;private: int leftThread, rightThread; ThreadNode *leftChild, *rightChild; Type data;public: ThreadNode ( const Type item ) : data (item), leftChild (NULL), rightChild (NULL), leftThread (0), rightThread (0) ;中序線索化二叉樹的類定義template

27、class ThreadTree; template class Thtemplate class ThreadTree private: ThreadNode * root; /根 InThread ( ThreadNode * current, ThreadNode * &pre ); /建樹public: ThreadTree ( ) : root (NULL) ; /構(gòu)造函數(shù) ThreadNode * First ( ThreadNode * current ); ThreadNode * Last ( ThreadNode * current ); template class Th

28、 ThreadNode * Next ( ThreadNode * current ); ThreadNode * Prior ( ThreadNode * current ); ThreadNode * if (current-rightThread =1) 后繼為current-rightChildelse /current-rightThread != 1 后繼為當(dāng)前結(jié)點(diǎn)右子樹 的中序下的第一個(gè)結(jié)點(diǎn) （最左下） 尋找當(dāng)前結(jié)點(diǎn)在中序下的后繼ABDECFHIKGJif (current-rightThread =1) if (current-leftThread=1) 前驅(qū)為current-

29、leftChild else /current-leftThread=0 前驅(qū)為當(dāng)前結(jié)點(diǎn)左子樹 中序下的最后一個(gè)結(jié)點(diǎn) （最右下） 尋找當(dāng)前結(jié)點(diǎn)在中序下的前驅(qū)ABDECFHIKGJL if (current-leftThread=1樹的存儲(chǔ)表示樹的廣義表表示5.6 樹與森林ABCDEFG葉結(jié)點(diǎn)分支結(jié)點(diǎn)根結(jié)點(diǎn)廣義表原子結(jié)點(diǎn)子表結(jié)點(diǎn)表頭結(jié)點(diǎn)樹的存儲(chǔ)表示樹的廣義表表示5.6 樹與森林ABCDEFG葉結(jié)雙親表示法（每個(gè)節(jié)點(diǎn)都有唯一的雙親節(jié)點(diǎn)）ABCDEFGdataparentA B C D E F G-1 0 0 0 1 1 30 1 2 3 4 5 6雙親表示法（每個(gè)節(jié)點(diǎn)都有唯一的雙親節(jié)點(diǎn)）ABCDE

30、FGdatABCDEFG適用于： 等數(shù)量的鏈域ABCDEFG 每個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)相等，等于樹的度（degree）子女指針表示法 data child1child2child3childdABCDEFG適用于： 等數(shù)量的鏈域ABCDEFG 子女鏈表表示無(wú)序樹情形鏈表中各結(jié)點(diǎn)順序任意，有序樹必須自左向右鏈接各個(gè)子女結(jié)點(diǎn)。ABCDEFG123456ABCDEFG0123456子女鏈表表示無(wú)序樹情形鏈表中各結(jié)點(diǎn)順序任意，有序樹必須自左向左子女-右兄弟表示 datafirstChildnextSiblingABCDEFGABCDGFE左子女-右兄弟表示 datafirstChildnextS對(duì)于一棵

31、樹，按照以下規(guī)則構(gòu)造相應(yīng)的二叉樹：（）加線：各兄弟之間加一連線（）抹線：對(duì)任何結(jié)點(diǎn)，除了最左子樹外，抹掉該結(jié)點(diǎn)與其他子樹之間的“父子關(guān)系”（）調(diào)整：以樹的根結(jié)點(diǎn)作為二叉樹的根結(jié)點(diǎn)，樹根與最左子樹之間的關(guān)系“父左子”，結(jié)點(diǎn)按層次排列轉(zhuǎn)換后的二叉樹是唯一的，并且：根結(jié)點(diǎn)只有左子樹左子女是原樹中的最左的孩子，右孩子是它在原來(lái)樹中的下一個(gè)兄弟樹與二叉樹的轉(zhuǎn)換對(duì)于一棵樹，按照以下規(guī)則構(gòu)造相應(yīng)的二叉樹：轉(zhuǎn)換后的二叉樹是唯森林與二叉樹的轉(zhuǎn)換樹二叉樹（左子女，右兄弟）森林：樹的有限集合森林與二叉樹的轉(zhuǎn)換樹二叉樹（左子女，右兄弟）森林：T1 T2 T3AFHBCDGIJEK3 棵樹的森林T1 T2 T3AFBC

32、DEGHIKJ各棵樹的二叉樹表示ABCEDHIKJFG森林的二叉樹表示T1 T2 T3AFHBCDGIJ樹的遍歷深度優(yōu)先遍歷 先根(前序)次序遍歷 后根(后序)次序遍歷ABCDEFG樹的遍歷深度優(yōu)先遍歷ABCDEFG當(dāng)樹非空時(shí) 訪問(wèn)根結(jié)點(diǎn)； 依次先根遍歷根的各棵 子樹。ABCDEFG先根遍歷: ABEFCDGABCEDGF二叉樹前序遍歷 ？ABEFCDG樹的先根次序遍歷當(dāng)樹非空時(shí)ABCDEFG先根遍歷:ABCEDGF二叉樹前序遍樹的先根遍歷:與其對(duì)應(yīng)二叉樹表示的前序遍歷結(jié)果相同?？梢越柚鷮?duì)應(yīng)二叉樹的前序遍歷算法實(shí)現(xiàn)。樹的先根遍歷:當(dāng)樹非空時(shí)依次后根遍歷根的各棵子樹；訪問(wèn)根結(jié)點(diǎn)。對(duì)應(yīng)二叉樹中序遍

33、歷樹后根遍歷: EFBCGDAABCDEFGABCEDGFEFBCGDA樹的后根次序遍歷當(dāng)樹非空時(shí)對(duì)應(yīng)二叉樹中序遍歷樹后根遍歷: EFBCGDAAB與其對(duì)應(yīng)二叉樹表示的中序遍歷結(jié)果相同。 樹的后根遍歷可以借助對(duì)應(yīng)二叉樹的中序遍歷算法實(shí)現(xiàn)。樹的后根遍歷:與其對(duì)應(yīng)二叉樹表示的中序遍歷結(jié)果相同。樹的后根遍歷: 廣度優(yōu)先(層次次序)遍歷。按廣度優(yōu)先次序遍歷樹的結(jié)果。 ABCDEFGABCEDGFABCDEFG 廣度優(yōu)先(層次次序)遍歷。按廣度優(yōu)先次序遍歷樹的結(jié)果。AB廣度優(yōu)先遍歷算法template void Tree : LevelOrder ( ) /按廣度優(yōu)先次序分層遍歷樹, 樹的根結(jié)點(diǎn)是/當(dāng)前

34、指針current。算法中用到一個(gè)隊(duì)列。 QueueTreeNode* Qu(DefaultSize); TreeNode *p; if ( current != NULL ) /當(dāng)前指針不空 p = current; /保存當(dāng)前指針 Qu.EnQueue ( current ); while ( Qu.IsEmpty ( ) = 0 ) 廣度優(yōu)先遍歷算法 current = Qu.getFront( ); Qu.DeQueue ( ); visit ( ); /隊(duì)列中取一個(gè)并訪問(wèn)之 current = current -firstChild ;/待訪問(wèn)結(jié)點(diǎn)的子女結(jié)點(diǎn)進(jìn)隊(duì)列 while ( c

35、urrent != NULL ) Qu.EnQueue ( current ); current = current-nextSibling; current = p; /恢復(fù)算法開始的當(dāng)前指針 current = Qu.getFr(1) 先序次序遍歷的規(guī)則：若森林非空，則先訪問(wèn)森林中第一棵樹的根結(jié)點(diǎn)，再先序遍歷第一棵樹各子樹，接著先序遍歷第二棵樹、第三棵樹、直到最后一棵樹。 森林的先序遍歷等價(jià)于它轉(zhuǎn)換成的二叉樹的先序遍歷。 森林的遍歷(1) 先序次序遍歷的規(guī)則：森林的先序遍歷等價(jià)于它轉(zhuǎn)換成的二(2)后根次序遍歷的規(guī)則若森林 F = ，返回；否則后根遍歷森林 F 第一棵樹的根結(jié)點(diǎn)的子樹森林T1

36、1, , T1k；訪問(wèn)森林的根結(jié)點(diǎn) r1；后根遍歷森林中除第一棵樹外其他樹組成的森林T2, ., Tm。(2)后根次序遍歷的規(guī)則若森林 F = ，返回；否則ABCEDHIKJFG對(duì)應(yīng)二叉樹中序遍歷的結(jié)果。T1 T2 T3AFHBCDGIJEK森林的后根次序遍歷結(jié)果:BCEDA GF KIJHABCEDHIKJFG對(duì)應(yīng)二叉樹中序遍歷的結(jié)果。T1 森林的遍歷(3) 廣度優(yōu)先遍歷(層次序遍歷) ： 若森林 F 為空，返回；否則 依次遍歷各棵樹的根結(jié)點(diǎn)； 依次遍歷各棵樹根結(jié)點(diǎn)的所有子女； 依次遍歷這些子女結(jié)點(diǎn)的子女結(jié)點(diǎn)。ABCEDHIKJFGAFHBCDGIJEK森林的二叉樹表示T1 T2 T3AFH

37、BCDGIJEK森林的遍歷(3) 廣度優(yōu)先遍歷(層次ABCEDHIKJFGA優(yōu)先級(jí)隊(duì)列 每次出隊(duì)列的是優(yōu)先權(quán)最高的元素5.7 堆 ( Heap )優(yōu)先級(jí)隊(duì)列5.7 堆 ( Heap )完全二叉樹 順序表示Ki K2i+1 & Ki K2i+2 最小堆完全二叉樹 順序表示Ki K2i+1 & Ki K2i+2 最大堆堆的定義090987877878454565653131532323531717完全二叉樹完全二叉樹堆的定義0909878778784545關(guān)于堆完全二叉樹:所有非葉結(jié)點(diǎn)的值均不大于(或不小于)其左、右孩子結(jié)點(diǎn)的值堆：k0,k1,kn-1, ki k2i+1 & ki k2i+2關(guān)于

38、堆完全二叉樹:所有非葉結(jié)點(diǎn)的值均不大于(或不小于)其左、 判斷下列序列是否是堆？ 100,90,80,60,85,75,20,25,10,70,65,50 判斷下列序列是否是堆？ 1最小堆的類定義#define DefaultSize 10template class MinHeap : public MinPQ private: Type * heap; /存放最小堆元素的數(shù)組 int CurrentSize; /最小堆當(dāng)前元素個(gè)數(shù) int MaxHeapSize; /最多允許元素個(gè)數(shù) void FilterDown ( int i, int m ); /從 i 到m自頂向下進(jìn)行調(diào)整成為最小

39、堆 最小堆的類定義 void FilterUp ( int i ); /從 i 到0自底向上進(jìn)行調(diào)整成為最小堆public: MinHeap ( int sz ); /構(gòu)造函數(shù) : 建立空堆 MinHeap ( Type arr , int n ); /構(gòu)造函數(shù) MinHeap ( const MinHeap& R ); MinHeap ( ) delete heap; int Insert ( const Type& x ); /插入 int Remove ( Type& x ); /刪除 void FilterUp ( int i ); int IsEmpty ( ) const /判堆空

40、否 return CurrentSize = 0; int IsFull ( ) const /判堆滿否 return CurrentSize = MaxHeapSize; void MakeEmpty ( ) CurrentSize = 0; int IsEmpty ( ) const 堆的建立建立空堆根據(jù)給定數(shù)組中的數(shù)據(jù)和大小,建立堆對(duì)象template MinHeap :MinHeap ( int maxSize ) /根據(jù)給定大小maxSize,建立堆對(duì)象MaxHeapSize = DefaultSize maxSize ? maxSize : DefaultSize; /確定堆的大小

41、 heap = new Type MaxHeapSize; if ( heap = NULL ) cerr “存儲(chǔ)分配錯(cuò)!” endl; exit(1); CurrentSize = 0; 建立空堆堆的建立建立空堆template 根據(jù)給定數(shù)組中的數(shù)據(jù)和大小,建立堆對(duì)象 template MinHeap : MinHeap ( Type arr , int n ) MaxHeapSize = DefaultSize n ? n : DefaultSize; heap = new Type MaxHeapSize; if ( heap = NULL ) cerr “存儲(chǔ)分配錯(cuò)!” endl; e

42、xit(1); for ( int i = 0; i = 0 ) /從下到上逐步擴(kuò)大,形成堆 FilterDown ( currentPos, CurrentSize-1 ); /從currentPos開始,到CurrentSize止, /調(diào)整 currentPos-; i5317780923456587int currentPos = (CurrentSize-FilterDown逐步調(diào)整為最小堆例：將一組用數(shù)組存放的任意數(shù)據(jù)調(diào)整成堆5317780923456587icurrentPos = i = 3FilterDown逐步調(diào)整為最小堆例：將一組用數(shù)組存放的任最小堆的向下調(diào)整算法基本算法思

43、想： FilterDown ( int i, int n) 如果結(jié)點(diǎn)i左子女的關(guān)鍵碼小于右子女的關(guān)鍵碼，則沿i的左分支進(jìn)行調(diào)整，否則沿i的右分支進(jìn)行調(diào)整，令j為參加調(diào)整的子女； 若Ri.keyRj.key,則兩結(jié)點(diǎn)對(duì)調(diào)位置，把關(guān)鍵碼小的結(jié)點(diǎn)上浮，i=j,j=2i+1若Ri.key=Rj.key,則算法終止最小堆的向下調(diào)整算法基本算法思想： FilterDown (自下向上逐步調(diào)整為最小堆例：將一組用數(shù)組存放的任意數(shù)據(jù)調(diào)整成堆5317780923456587icurrentPos = i = 3currentPos = i = 2i5317780923456587自下向上逐步調(diào)整為最小堆例：將一

44、組用數(shù)組存放的任意數(shù)據(jù)調(diào)整成5317780923456587icurrentPos = i = 15317780923456587i5317780923456587icurrentPos = 5317780923456587icurrentPos = i = 05317780923456587i095317780923456587icurrentPos = 5317780923456587i5317780923456587i175317780923456587i5317780923456template void MinHeap : FilterDown ( int start, int En

45、dOfHeap ) int i = start, j = 2*i+1; / j 是 i 的左子女 Type temp = heapi; while ( j = EndOfHeap ) if ( j heapj+1 ) j+; /兩子女中選小者 if ( temp = heapj ) break; else heapi = heapj; /下面的上浮 i = j; j = 2*j+1; /向下滑動(dòng) heapi = temp; template void Min 最小堆的插入1778092345658711在堆中插入新元素1153ij53177809234565871123ji最小堆的向上調(diào)整 最

46、小堆的插1778094565871153ji2317531178092345658723ji1778094565871153ji231753117809/在堆中插入新元素 x if ( CurrentSize = MaxHeapSize ) /堆滿 cerr 堆已滿 endl; return 0; heapCurrentSize = x; /插在表尾 FilterUp (CurrentSize); /向上調(diào)整為堆 CurrentSize+; /堆元素增一 return 1;template int MinHeap : Insert ( const Type &x ) /在堆中插入新元素 xte

47、mplate class Tytemplate void MinHeap : FilterUp ( int start ) /從 start 開始,向上直到0,調(diào)整堆 int j = start, i = (j-1)/2; / i 是 j 的雙親 Type temp = heapj; while ( j 0 ) if ( heapi = temp ) break; else heapj = heapi; j = i; i = (i -1)/2; heapj = temp;最小堆的向上調(diào)整算法template 最小堆的向上調(diào)整最小堆的刪除算法（刪除堆頂元素） 將堆頂元素刪去 以最后一個(gè)結(jié)點(diǎn)填補(bǔ)取走的元素； 重新調(diào)整最小堆的刪除算法（刪除堆頂元素） 將堆頂元素刪去最小堆的刪除算法template int MinHeap :Remove ( Type &x ) if ( !CurrentSize ) cout “ 堆已空 endl; return 0; x = heap0; /最小元素出隊(duì)列 heap0 = heapCurrentSize-1; CurrentSize-; /用最小元素填補(bǔ) FilterDown ( 0, CurrentSize-1 ); /調(diào)整 return 1;