第6章+樹和二叉樹old

1、第6章 樹和二叉樹 主要內(nèi)容 6.1 樹的定義和基本術(shù)語 6.2 二叉樹 6.3 遍歷二叉樹 6.4 線索二叉樹 6.5 樹和森林 6.6 赫夫曼樹及其應(yīng)用 6.1 樹的定義和基本術(shù)語(1) 樹（Tree）是n(n 0)個結(jié)點(diǎn)的有限集。在任意一棵非空樹 中: A、有且僅有一個稱為根的結(jié)點(diǎn)； B、當(dāng)n 2時，其余結(jié)點(diǎn)分為m(m 0) 個互不相交的子 集，每個子集本身又是一棵樹，稱為根的子樹。 以上是一個遞歸的定義 在樹的定義中又用到了樹的 概念，由此可見遞歸是樹的固 有特性。 A B MLK JIHGFE DC 6.1 樹的定義和基本術(shù)語(2) A B MLK JIHGFE DC 樹根：A 每個

2、子集都是滿足樹的定義的樹，稱 為A的子樹B子樹、C子樹、D子樹。 樹根A沒有 直接前驅(qū)；其余 結(jié)點(diǎn)有且僅有一 個直接前驅(qū)，有 0個或多個直接 后繼。 三個互不相交的子集： B, E, F, K, L C ,G D, H, I, J, M 樹的特征：層次性和分支性 6.1 樹的定義和基本術(shù)語(3) 結(jié)點(diǎn)的度：結(jié)點(diǎn)的非空子樹個數(shù) 樹的度：樹內(nèi)各結(jié)點(diǎn)度的最大值 分支結(jié)點(diǎn)(非終端結(jié)點(diǎn)) ：度非0的結(jié)點(diǎn) 葉子結(jié)點(diǎn)(終端結(jié)點(diǎn))：度為0的結(jié)點(diǎn) 孩子：結(jié)點(diǎn)的子樹的根 雙親：孩子的直接前驅(qū)結(jié)點(diǎn) 兄弟：同一個雙親的孩子結(jié)點(diǎn)互稱為兄弟 子孫：以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn) 祖先：從根到該結(jié)點(diǎn)所經(jīng)歷的分支上的所有結(jié)點(diǎn)

3、 堂兄:雙親在同一層的結(jié)點(diǎn) A B MLK JIHGFE DC 結(jié)點(diǎn)的層次：從根開始定義起，根為第一層，根的孩子為第二層。若 某結(jié)點(diǎn)在第L層，則其子樹的根在第L+1層。 樹的深度（高度）：結(jié)點(diǎn)層次的最大值 有序樹和無序樹：若樹中所有結(jié)點(diǎn)的的各子樹看成是從從至右是有次 序的（即不能置換），稱為有序樹，否則稱為無序樹。 森林：m（m0）個樹的集合 A B MLK JIHGFE DC Tree = (A ( B ( E ( K , L ), F ), C ( G ), D ( G, H ( M ), I, J ) ) ) 6.1 樹的定義和基本術(shù)語(4) 樹的基本操作：樹的基本操作： 構(gòu)造空樹Ini

4、tTree( 銷毀樹DestroyTree( 創(chuàng)建樹CreateTree( 清空樹ClearTree( 判斷空樹TreeEmpty(T); 求樹的深度TreeDepth(T); 求雙親parent(T, cur_e); 求長子LeftChild(T, cur_e); 求右鄰兄弟RightSibling(T, cur_e); 插入子樹InsertChild( 刪除子樹DeleteChild( 遍歷樹TraverseTree(T, visite(); 6.1 樹的定義和基本術(shù)語(5) 6.2 二叉樹 二叉樹的定義 二叉樹的性質(zhì) 二叉樹的存儲結(jié)構(gòu) 6.2.1 二叉樹的定義(1) 二叉樹是另一種樹型結(jié)

5、構(gòu)，它的特點(diǎn)是每個結(jié)點(diǎn)至多只有兩 棵子樹(即 二叉樹中不存在度大于2的結(jié)點(diǎn))，并且，二叉樹的子樹有左右之分，其 次序不能任意顛倒。 二叉樹可以為空，稱為空二叉樹; 非空二叉樹一定有兩個子樹； 左、右子樹有次序關(guān)系，不能互換； 二叉樹可以有5種基本形態(tài)： 二叉樹不是結(jié)點(diǎn)的度都不超過2的有序樹. 6.2 二叉樹 根根 左子樹 右子樹 根根根根 根根 6.2.1 二叉樹的定義(2) 具有三個結(jié)點(diǎn)的樹與二叉樹 6.2 二叉樹 A、三個結(jié)點(diǎn)的樹有兩種不同的形態(tài) B、三個結(jié)點(diǎn)的二叉樹有五種不同的形態(tài) 樹型結(jié)構(gòu)的共同特征：層次性、分支性 6.2.1 二叉樹的定義(3) 二叉樹的基本操作二叉樹的基本操作 初始

6、化空二叉樹InitBiTree( B、若X有左孩子，則X左孩子LCHILD(i)=2i； C、若X有右孩子，則X右孩子RCHILD(i)=2i1； D、若i為奇數(shù)且i1，則X的左兄弟為i1； E、若i為偶數(shù)且idata);/訪根 PreOrderTraverse (T-lchild); PreOrderTraverse (T-rchild); 6.3.2 遍歷二叉樹的遞歸與非遞歸算法(2) 先序遍歷二叉樹 6.3 遍歷二叉樹 A B LKJIH GFED C ACBEDLFKGJIH 6.3.2 遍歷二叉樹的遞歸與非遞歸算法(3) 中序遍歷二叉樹 若二叉樹為空，則空操作；否則 u中序遍歷左子樹

7、； u訪問根； u中序遍歷右子樹； 6.3 遍歷二叉樹 根根 void InOrderTraverse (BiTree T) if (!T) return; InOrderTraverse (T-lchild); visit(T-data);/訪根 InOrderTraverse (T-rchild); 6.3.2 遍歷二叉樹的遞歸與非遞歸算法(4) 中序遍歷二叉樹 6.3 遍歷二叉樹 A B LKJIH GFED C ACBEDLFKGJIH 6.3.2 遍歷二叉樹的遞歸與非遞歸算法(5) 后序遍歷二叉樹 若二叉樹為空，則空操作；否則 u后序遍歷左子樹； u后序遍歷右子樹； u訪問根； 6.

8、3 遍歷二叉樹 根根 void PostOrderTraverse (BiTree T) if (!T) return; PostOrderTraverse (T-lchild); PostOrderTraverse (T-rchild); visit(T-data);/訪根 6.3.2 遍歷二叉樹的遞歸與非遞歸算法(6) 先序遍歷二叉樹 6.3 遍歷二叉樹 A B LKJIH GFED C ACBEDLFKGJIH 6.3.2 遍歷二叉樹遞歸與非遞歸算法(7) 中序遍歷的非遞歸算法(借助堆棧實(shí)現(xiàn)) void InOrderTraverse ( BiTree bt, void(*visit)(

9、BiTree) /中序遍歷的非遞歸算法 InitStack(S); Push(S,T); While (!StackEmpty(S) While (GetTop(S,p) Pop(s,p); If (!StackEmpty(S) Pop(s,p); If(!visit(p-data) return ERROR; Push(S,p-rchild); 6.3 遍歷二叉樹 6.3.2 遍歷二叉樹遞歸與非遞歸算法(8) 先序遍歷的非遞歸算法(借助堆棧實(shí)現(xiàn)) void PreOrderTraverse (BiTree bt) if (!bt) return; InitStack(S); push(S,

10、bt); /樹根的指針進(jìn)棧 while (!EmptyStack(S) pop(S, p); while(p) /沿著左鏈一路向下 visit(p-data); /訪問 if(p-rchild) push(S,p-rchild); /右孩子進(jìn)棧 p=p-lchild; 6.3 遍歷二叉樹 6.3 遍歷二叉樹 遍歷二叉樹 遍歷二叉樹的遞歸與非遞歸算法 表達(dá)式求值 二叉樹的運(yùn)算舉例 層序遍歷二叉樹 6.3.3 表達(dá)式求值 表達(dá)式求值 6.3 遍歷二叉樹 算術(shù)表達(dá)式中的二叉樹表示 二元算符 右操作數(shù)左操作數(shù) 一元算符 右操作數(shù) Model ：a+b*(c-d)-e/f a b cd ef + * -

11、 - / 先序遍歷得到前綴表達(dá)式： - + a * b c d / e f 中序遍歷得到中綴表達(dá)式： a + b * ( c d ) e / f 后序遍歷得到后綴表達(dá)式： a b c d - * + e f / - 6.3 遍歷二叉樹 遍歷二叉樹 遍歷二叉樹的遞歸與非遞歸算法 表達(dá)式求值 二叉樹的運(yùn)算舉例 層序遍歷二叉樹 6.3.4 二叉樹的運(yùn)算舉例(1) 計(jì)算二叉樹中的結(jié)點(diǎn)數(shù) Number() 思路：二叉樹結(jié)點(diǎn)數(shù)1+左子樹結(jié)點(diǎn)數(shù)+右子樹結(jié)點(diǎn)數(shù) 6.3 遍歷二叉樹 int Number(BiTree bt) if(!bt) return 0; /空二叉樹 else nl=Number(bt-l

12、child); nr=Number(bt-rchild); return 1+nl+nr; void Number(BiTree bt, int n+; /累加結(jié)點(diǎn)數(shù) Number(bt-lchild, n); Number(bt-rchild, n); 計(jì)算二叉樹中葉子結(jié)點(diǎn)的數(shù)目 Leafs() 思路：葉子數(shù)左子樹葉子數(shù)+右子樹葉子數(shù) 6.3.4 二叉樹的運(yùn)算舉例(2) 6.3 遍歷二叉樹 int Leafs(BiTree bt) if(!bt) return 0; /空二叉樹 if(！bt-lchild LL=Leafs(bt-lchild); LR=Leafs(bt-rchild); r

13、eturn LL+LR; void Leafs(BiTree bt，int if(!bt-lchild Leafs(bt-lchild, n); Leafs(bt-rchild, n); 6.3.4 二叉樹的運(yùn)算舉例(3) 計(jì)算二叉樹的深度 Depth() 思路： 深度 = max(左子樹深度，右子樹深度) + 1 6.3 遍歷二叉樹 int Depth(BiTree bt) if(!bt) return 0; hl=Depth(bt-lchild); /計(jì)算bt的左子樹深度 hr=Depth(bt-rchild); /計(jì)算bt的右子樹深度 return (hlhr ? (Hl+1):(hr+

14、1) 6.3 遍歷二叉樹 遍歷二叉樹 遍歷二叉樹的遞歸與非遞歸算法 表達(dá)式求值 二叉樹的運(yùn)算舉例 層序遍歷二叉樹 6.3.5 層序遍歷二叉樹(1) 自上而下、自左向右地遍歷二叉樹，先被訪問結(jié)點(diǎn)的孩子先被訪問。 遍歷思想為： 空樹, 結(jié)束。 初始化一個空隊(duì)列Q, 樹根入隊(duì); 隊(duì)頭e元素出隊(duì), 訪問e; 如果e有左孩子, 則左孩子入隊(duì); 如果e有右孩子, 則右孩子入隊(duì); 如果隊(duì)列不空轉(zhuǎn)3; 否則結(jié)束 6.3 遍歷二叉樹 6.3.5 層序遍歷二叉樹(2) 算法 LevelTraverse() void LevelTraverse(BiTree bt) /按層次遍歷二叉樹算法 if( !bt ) re

15、turn ; /空樹 InitQueue(Q); /初始化空隊(duì)列Q EnQueue(Q, bt); /根入隊(duì) while( !EmptyQueue(Q) ) DeQueue(Q, p); /隊(duì)頭p出隊(duì) visit(p-data); /訪問p if(p-lchild) EnQueue(Q，p-lchild); /p的左孩子入隊(duì) if(p-rchild) EnQueue(Q,p-rchild); /p的右孩子入隊(duì) 6.3 遍歷二叉樹 6.4 線索二叉樹(1) 二叉樹的遍歷序列是線性序列。在二叉樹上找某個結(jié)點(diǎn)在某種遍歷序 列中的直接前驅(qū)或直接后繼，只能在對二叉樹遍歷時動態(tài)求得。 如何在遍歷過程中保留

16、下結(jié)點(diǎn)的前驅(qū)和后繼的信息呢？最直接的辦法 也許就是給每個結(jié)點(diǎn)增加兩個指針。這樣做會使得結(jié)構(gòu)的存儲密度大 大降低。 做如下規(guī)定： 若結(jié)點(diǎn)有左子樹，則其lchild域指向其左孩子，否則指向其前驅(qū)；若 結(jié)點(diǎn)有右子樹，則其rchild域指向其右孩子，否則指向其后繼。 其中： 6.4 線索二叉樹 lchildLTagdataRTagrchild Ltag = 0 lchild域指向結(jié)點(diǎn)的左孩子 1 lchild域指向結(jié)點(diǎn)的前驅(qū) Rtag = 0 lchild域指向結(jié)點(diǎn)的右孩子 1 lchild域指向結(jié)點(diǎn)的后繼 6.4 線索二叉樹(2) 二叉樹的二叉線索存儲表示： 6.4 線索二叉樹 typedef en

17、um PointerTagLink, Thread; typedef struct BiThrNode TElemType data; struct BiThrNode *lchild, *rchild; PointerTag Ltag, Rtag; /左右標(biāo)志 BiThrNode, * BiThrTree; 中序線索二叉樹： 1 32 7 4 65 1 32 7 4 65 NULL NULL 中序線索二叉樹 6.4 線索二叉樹(3) 二叉樹的二叉線索存儲： 6.4 線索二叉樹 1 32 7 4 65 NULL NULL 中序線索二叉樹 1 23 5 6 4 7 中序遍歷序列 的起始點(diǎn) 中序遍

18、歷序列 的終端點(diǎn) 帶頭結(jié)點(diǎn)的中序線索二叉樹 6.4 線索二叉樹(4) 線索化，就是在已知二叉鏈的前提下，填寫每個結(jié)點(diǎn)左線索LTag域和 右線索RTag域。 若要建立中(先、后）序線索，則在中(先、后）序遍歷過程中完成線索 化操作。 通過中序遍歷建立中序線索化鏈表的算法在教材P.134,135中。 遍歷線索二叉樹 在線索二叉樹中，由于可以直接找到每個結(jié)點(diǎn)的后繼或前驅(qū)，所以遍 歷可以用非遞歸的方法實(shí)現(xiàn)，而且不必借助棧.(算法 P.134) 6.4 線索二叉樹 6.5 樹和森林 樹的存儲結(jié)構(gòu) 森林與二叉樹的轉(zhuǎn)換 樹和森林的遍歷 6.5.1 樹的存儲結(jié)構(gòu)(1) 雙親表示法 6.5 樹和森林 R A G

19、K F H ED CB 1A0 2B0 3C0 0R-1 4D1 5E1 6F3 7G6 8H6 9K6 #define MAX_TREE_SIZE 100 typedef struct PTNode TElemType data; int parent; PTNode; typedef struct PTNode nodesMAX_TREE_SIZE; int r,n; /根位置和結(jié)點(diǎn)數(shù)目 Ptree; 6.5.1 樹的存儲結(jié)構(gòu)(2) 孩子表示法 6.5 樹和森林 R A GK F H ED CB typedef struct CTNode int child; struct CTNode

20、*next; *ChildPtr; typedef struct TElemType data; ChildPtr firstchild; CTBox; typedef struct CTBox nodesMAX_TREE_SIZE; int r,n; /根位置和結(jié)點(diǎn)數(shù)目 CTree; 1B 2C0 3D 0A 4R 5E 6F 7G 8H 9K 53 6 210 98-17 6.5.1 樹的存儲結(jié)構(gòu)(1) 孩子-兄弟表示法 6.5 樹和森林 R A GK F H ED CB typedef struct CSNode TElemType data; struct CSNode *firstc

21、hild, *nextsibling; CSNode, CSTree; firstchilddatanextsibling K H G F C E BD A R 樹的孩子兄弟表示可以將樹轉(zhuǎn)化為二叉樹 6.5 樹和森林 樹的存儲結(jié)構(gòu) 森林與二叉樹之間的轉(zhuǎn)換 樹和森林的遍歷 6.5.2 森林和二叉樹之間的轉(zhuǎn)換(1) 樹用孩子兄弟鏈表表示時，就已轉(zhuǎn)化成二叉樹了。一棵樹可以唯一地 轉(zhuǎn)換成一棵右子樹為空的二叉樹。 6.5 樹和森林 A B D EC A B DE C 森林轉(zhuǎn)化為二叉樹： 把森林中的每一棵樹轉(zhuǎn)換成二叉樹； 將所有二叉樹的樹根用線相連； 以第一棵二叉樹的樹根為圓心，順時針轉(zhuǎn)45度。 A B

22、D EC 6.5.2 森林和二叉樹之間的轉(zhuǎn)換(2) 6.5 樹和森林 A BDC E F G H J I A B D C E F G H J I A B D C E FG H J I 6.5 樹和森林 樹的存儲結(jié)構(gòu) 森林與二叉樹之間的轉(zhuǎn)換 樹和森林的遍歷 6.5.3 樹和森林的遍歷(1) 先序遍歷樹：若樹不空，則 1. 訪問根；訪問根； 2. 從左至右先序遍歷根的各個子樹。從左至右先序遍歷根的各個子樹。 6.5 樹和森林 R A GK F H ED CB 后序遍歷樹：若樹不空，則 1. 從左至右后序遍歷根的各個子樹。從左至右后序遍歷根的各個子樹。 2. 訪問根。訪問根。 R A G K F H

23、 E D C B 先根序列：RADEBCFGHK 后根序列：DEABGHKFCR 先序序列：RADEBCFGHK 中序序列：DEABGHKFCR 后序序列：EDKHGFCBAR 等價 6.5.3 樹和森林的遍歷(2) 先序遍歷樹，等價于先序遍歷由這棵樹轉(zhuǎn)換而成的二叉樹； 后序遍歷樹，等價于中序遍歷由這棵樹轉(zhuǎn)換而成的二叉樹； 6.5 樹和森林 先序遍歷森林：若森林不空，則 1. 訪問第一棵樹的根結(jié)點(diǎn)；訪問第一棵樹的根結(jié)點(diǎn)； 2. 先序遍歷第一棵樹根結(jié)點(diǎn)的子樹森林；先序遍歷第一棵樹根結(jié)點(diǎn)的子樹森林； 3. 先序遍歷森林中去掉第一棵樹后剩下的樹構(gòu)成的森林先序遍歷森林中去掉第一棵樹后剩下的樹構(gòu)成的森林

24、 中序遍歷森林：若森林不空，則 1. 中序遍歷第一棵樹根結(jié)點(diǎn)的子樹森林；中序遍歷第一棵樹根結(jié)點(diǎn)的子樹森林； 2. 訪問第一棵樹的根結(jié)點(diǎn)；訪問第一棵樹的根結(jié)點(diǎn)； 3. 中序遍歷森林中去掉第一棵樹后剩下的樹構(gòu)成的森林中序遍歷森林中去掉第一棵樹后剩下的樹構(gòu)成的森林 6.5.3 樹和森林的遍歷(3) 6.5 樹和森林 A BDC E F G H J I A B D C E FG H J I 等價 先序序列：ABCDEFGHIJ 中序序列：BCDAFEHJIG 先序序列：ABCDEFGHIJ 中序序列：BCDAFEHJIG 后序序列：DCBFJIHGEA 6.6 赫夫曼樹及其應(yīng)用 最優(yōu)二叉樹（赫夫曼樹）

25、 赫夫曼樹的構(gòu)造 赫夫曼編碼 6.6.1 最優(yōu)二叉樹（赫夫曼樹）(1) 路徑：從一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)所經(jīng)過的分支。 路徑長度L：路徑上分支的數(shù)目。 樹的路徑長度：從樹根到每一個結(jié)點(diǎn)的路徑產(chǎn)度之和。 樹的帶權(quán)路徑長度：樹中所有的葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，通常 記作： 6.6 赫夫曼樹及其應(yīng)用 1 n kk k WPLw L AB CD 7524 C D A B 7 5 2 4 C 7 5 2 4 A D B WPL=7*2+5*2+2*2+4*2=36WPL=7*3+5*3+2*1+4*2=46WPL=7*1+5*2+2*3+4*3=35 6.6.1 最優(yōu)二叉樹（赫夫曼樹）(2) 哈夫曼樹：由

26、權(quán)值為w1,w2,.,wn)的n片葉子構(gòu)成的所有二叉樹中， WPL值最小的二叉樹。 6.6 赫夫曼樹及其應(yīng)用 C 7 5 2 4 A D B WPL=7*1+5*2+2*3+4*3=35 C 7 5 2 4 A D B WPL=7*1+5*2+2*3+4*3=35 1. 哈夫曼樹不一定是最矮的樹 2. 哈夫曼樹形態(tài)可能不唯一 6.6 赫夫曼樹及其應(yīng)用 最優(yōu)二叉樹（赫夫曼樹） 赫夫曼樹的構(gòu)造 赫夫曼編碼 6.6.2 赫夫曼樹的構(gòu)造(1) 1952年，Huffman提出了一個構(gòu)造最優(yōu)二叉樹的一個精巧算法，被人們稱為 Huffman算法 。 算法的思想： 將權(quán)值為w1, w2, ., wn的n個葉子

27、構(gòu)成一個具有n棵樹的森林F； 從森林F中選取根權(quán)值最小的兩棵樹，分別作為左子樹和右子樹，再新添一個結(jié)點(diǎn)做為 根，合并成一棵新的二叉樹，新二叉樹根的權(quán)值等于左、右子樹根權(quán)值之和； 重復(fù)2，直到F中只剩下一棵樹為止，這棵樹就是所求的Huffman樹。 6.6 赫夫曼樹及其應(yīng)用 A 7 B 5 C 2 D 4 6 A 7 B 5 C 2 D 4 6 11 A 7 B 5 C 2 D 4 6 11 18 A 7 B 5 C 2 D 4 6.6.2 赫夫曼樹的構(gòu)造(2) 構(gòu)造n個葉子的哈夫曼樹需要經(jīng)過n-1次合并，每次合并都要增加一個新結(jié)點(diǎn)。 所以n個葉子的哈夫曼樹上有且僅有2n-1個結(jié)點(diǎn)。 哈夫曼樹上不存在度為1的結(jié)點(diǎn)。我們把這種不存在度為1的結(jié)點(diǎn)的二叉樹稱為 嚴(yán)格二叉樹嚴(yán)格二叉樹或正則二叉樹正則二叉樹。 6.6 赫夫曼樹及其應(yīng)用 存儲表示：存儲表示： typ