第4章樹與二叉樹4.1樹的定義和基本術語4.2二叉樹4.3樹與森林4.4森林與二叉樹的關系4.5Huffman樹與編碼數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第1頁!4.1樹（Tree）的定義和基本術語樹形結構是一種非線性結構，應用十分廣泛例如，行政機構、家譜、磁盤目錄等內蒙古大學理工學院計算機學院生命科學學院外國語學院人文學院數學系物理系電子系計算機系計算中心網絡中心漢語系歷史系哲學系生物系環境系動物中心生物工程中心資源所英語系日語系

行政機構數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第2頁!4.1樹（Tree）的定義和基本術語磁盤目錄數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第3頁!4.1樹（Tree）的定義和基本術語例，Tree=(D,R)D={Book,C1,C2,C3,S1.1,S1.2,S2.1,S2.2,S2.3,S2.1.1,S2.1.2}R={<Book,C1>,<Book,C2>,<Book,C3>,<C1,S1.1>,<C1,S1.2>,<C2,S2.1>,<C2,S2.2>,<C2,S2.3>,<S2.1,S2.1.1>,<S2.1,S2.1.2>}BookC1C2C3S1.1S1.2S2.1S2.2S2.3S2.1.1S2.1.2ChapterSectionSection數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第4頁!4.1樹（Tree）的定義和基本術語術語主要來源于家譜和樹雙親、子女（parent，child）若<a,b>R，則稱a是b的雙親，b是a的子女（孩子）結點的度（degree）結點所擁有的子女數葉（leaf）結點度為0的結點分枝結點（branchnode）度大于0的結點樹的度（degree）樹中最大的結點度數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第5頁!4.1樹（Tree）的定義和基本術語祖先、子孫（descendant，ancestor）一個結點是它所有子樹中的結點的祖先，這些結點是它的子孫路徑（path）是一結點序列n1,n2,n3,…,nk，并且前1個結點是后1個結點的雙親它的長度是k-1有序樹（orderedtree）每個結點的子女由左到右是有次序的；否則是無序樹ABCACB無序有序數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第6頁!4.1樹（Tree）的定義和基本術語森林（Forest）是m（m≥0）棵互不相交的樹的集合ArootBCDEFGHIJMKLF數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第7頁!4.2二叉樹——ADT二叉樹例ABCDEFGHK根結點左子樹右子樹注意：二叉樹不是樹，它是另外單獨定義的一種樹形結構，并非一般樹的特例。它的子樹有順序規定，分為左子樹和右子樹，不能隨意顛倒。數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第8頁!4.2二叉樹——ADT二叉樹ADT二叉樹的定義ADTBinaryTreeis{Data

是有限個結點的集合D。當D非空時，其中有一根結點t，余下的結點被分為t的左子樹和右子樹。

OperationsConstructorProcess：建立一棵空二叉樹

DeleteProcess：刪除二叉樹IsEmpty Process：判斷二叉樹是否是空

Output：若二叉樹為空，則返回true，否則返回false數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第9頁!4.2二叉樹——ADT二叉樹

CreateBinaryTreeInput：二叉樹的某種形式的定義definitionProcess：根據此定義definition構造二叉樹

MakeTreeInput：data是根結點值，left是左子樹，right是右子樹

Process：創建二叉樹，data是根結點值，left是其左子樹，right是其右子樹BreakTreeProcess：拆分二叉樹，data是根結點數據，left是左子樹，right是右子樹

Output：data，left，rightPreOrderInput：Visit()是結點訪問函數

Process：按前序遍歷對二叉樹中每個結點調用Visit()1次且僅1次

Output：根據Visit()，按前序遍歷序列得到結果數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第10頁!4.2二叉樹——二叉樹的性質性質1在二叉樹的第i層最多有2i-1

個結點（i1）。用歸納法證明：歸納基：歸納假設：歸納證明：i=1層時，只有一個根結點，

2i-1=20=1i=k-1（1≤ki）時命題成立i=k時，二叉樹上每個結點至多有兩棵子樹，則第i層的結點數=2k-22=2k-2+1=2k-1=2i-1

數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第11頁!4.2二叉樹——二叉樹的性質性質3任一二叉樹，若其葉結點個數為n0，度為2的非葉結點個數為n2，則n0＝n2＋1證明：若設度為1的結點有n1個，總結點個數為n，則n=n0+n1+n2

再設總邊數為e，則根據二叉樹的定義，e=2n2+n1=n-1因此，有2n2+n1=n0+n1+n2-1

n2=n0-1n0=n2+1數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第12頁!4.2二叉樹——二叉樹的性質滿二叉樹（FullBinaryTree）

每一層的結點數都達到了最大的二叉樹完全二叉樹（CompleteBinaryTree）若設二叉樹的高度為h，除第h層外，其它各層（0~h-1）的結點數都達到最大個數，第h層從右向左連續缺若干結點，這就是完全二叉樹CDEFGHIJCDEFGHIJKLMNO1112131415數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第13頁!4.2二叉樹——二叉樹的實現順序存儲表示完全二叉樹的順序存儲表示根據性質5：ST[i]的雙親是ST[i/2],左子女是ST[2*i]，右子女是ST[2*i+1]。123456789101112123456789101112數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第14頁!4.2二叉樹——二叉樹的實現鏈表存儲表示數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第15頁!4.2二叉樹——二叉樹的實現二叉鏈表結點類的定義classBinaryTreeNode{DataTypedata;BinaryTreeNode*leftChild,*rightChild;//左、右指針public:BinaryTreeNode(DataType&e,BinaryTreeNode*l=NULL,BinaryTreeNode*r=NULL){data=e;leftChild=l;rightChild=r;}};//BinaryTreeNode數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第16頁!4.2二叉樹——二叉樹的實現voidBreakTree(DataType&data，BinaryTree&left，BinaryTree&right);//拆分二叉樹voidPreOrder(voidVisit(BinaryTreeNode*&),BinaryTreeNode*&=root);voidInOrder(voidVisit(BinaryTreeNode*&),BinaryTreeNode*&=root);voidPostOrder(voidVisit(BinaryTreeNode*&),BinaryTreeNode*&=root);voidLevelOrder(voidVisit(BinaryTreeNode*&));//逐層遍歷voidDelete(BinaryTreeNode*&=root); //刪除一棵二叉樹，釋放其結點intSize(BinaryTreeNode*&=root);//返回二叉樹中結點數intHeight(BinaryTreeNode*&=root); //返回二叉樹的高度};//BinaryTree數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第17頁!4.2二叉樹——二叉樹的實現用left、right和data構成一棵新樹voidMakeTree(DataType&data,BinaryTree&left,BinaryTree&right){//left,right與當前二叉樹必須是不同的對象

root=newBinaryTreeNode(data,left.root,right.root);//創建新二叉樹

left.root=right.root=NULL}數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第18頁!4.2二叉樹——二叉樹的遍歷前序遍歷二叉樹（PreorderTraversal）若二叉樹為空，則空操作；否則訪問根結點(V)；前序遍歷左子樹(L)；前序遍歷右子樹(R)。例遍歷結果

-+a*b

-

cd/ef數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第19頁!4.2二叉樹——二叉樹的遍歷后序遍歷（PostorderTraversal）若二叉樹為空，則空操作；否則后序遍歷左子樹(L)；后序遍歷右子樹(R)；訪問根結點(V)。例遍歷結果

abcd

-*+ef/-數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第20頁!4.2二叉樹——二叉樹的遍歷前序遍歷的遞歸算法outTypePreOrder(outTypevisit(BinaryTreeNode*&),BinaryTreeNode*&t=root){//前序遍歷

if(t){Visit(t);PreOrder(Visit,t->leftChild);PreOrder(Visit,t->rightChild);}}//preorder數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第21頁!4.2二叉樹——二叉樹的遍歷中序遍歷二叉樹的遞歸過程圖解數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第22頁!4.2二叉樹——二叉樹的遍歷建立二叉樹以前序遍歷序列建立二叉樹說明：二叉樹用根字符序列和左右子樹的字符序列表示，空樹用空格（或某一字符，如0）表示DBFEAC該擴充二叉樹的前序遍歷序列ABD00EF000C00

(字符序列與二叉樹一一對應）該算法是一遞歸算法，遞歸三要素：1.遞歸出口：當遇到0時，是空樹。2.若不是0，創建根結點；3.建立根的左子樹和右子樹；數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第23頁!4.2二叉樹——二叉樹的遍歷例00000ABCDATBCD^^^^^數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第24頁!4.2二叉樹——二叉樹的遍歷例：已知前序遍歷序列為ABC，后序遍歷序列為CBA，則下列二叉樹都滿足條件。ABCABC若已知一棵二叉樹的前序序列和后序序列，能否唯一確定這棵二叉樹呢？數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第25頁!4.2二叉樹——二叉樹的遍歷前序：ABCDEFG

HI中序：BCAEDGHFI前序：BC中序：BC

BCDEFGHIA前序：DEFGHI中序：EDGHFIABCDEFGHI數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第26頁!4.2二叉樹——二叉樹的遍歷說明任意一棵二叉樹的任一種遍歷序列都是唯一的由二叉樹的前序序列和中序序列可唯一確定一棵二叉樹由二叉樹的后序序列和中序序列可唯一確定一棵二叉樹數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第27頁!4.2二叉樹——二叉樹的遍歷設計算法求二叉樹的結點個數voidCount(BiNode*root)//n為全局量并已初始化為0{if(root){Count(root->lchild);n++;Count(root->rchild);}}數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第28頁!4.2二叉樹——二叉樹遍歷的非遞歸實現先觀察一下三種遍歷行走的路線前序遍歷（VLR）例，ABEHGCFDIABCEFHGDI*********數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第29頁!4.2二叉樹——二叉樹遍歷的非遞歸實現后序遍歷（LRV）例，EGHBDFICA&&&&&&&&&ABCEFHGDI數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第30頁!4.2二叉樹——二叉樹遍歷的非遞歸實現中序遍歷的遞歸工作棧遍歷序列：EBGHAFDCI棧的變化A入棧；B入棧；E入棧；空入棧；空出棧；訪問E；空入棧；空出棧；E出棧；訪問B；H入棧；G入棧；空入棧；空出棧；訪問G；空入棧；空出棧；G出棧；訪問H；空入棧；空出棧；H出棧；B出棧；訪問A；C入棧；F入棧；空入棧；空出棧；訪問F；D入棧；空入棧；空出棧；訪問D；空入棧；空出棧；F出棧；訪問C；I入棧；空入棧；空出棧；訪問I；空入棧；空出棧；I出棧；C出棧；A出棧。ABCEFHGDI數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第31頁!4.2二叉樹——二叉樹遍歷的非遞歸實現中序遍歷的非遞歸算法voidInOrder(voidVisit(BinaryTreeNode*＆)){//中序遍歷

BinaryTreeNode*t=root;Stackstack;//建立棧while(t||!stack.IsEmpty()){if(t){stack.Push(t);t=t->leftChild;}//t向左走一步else{t=stack.Pop(); Visit(t);t=t->rightChild;}//t向右走一步 }//while}//InOrder數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第32頁!4.2二叉樹——二叉樹遍歷的非遞歸實現前序遍歷二叉樹的非遞歸算法思想建立棧Stack；t指向根；當t不空或Stack不空時反復做：若t不空，訪問t，t入棧；t指向左子女；否則：出棧頂元素到t中；t指向右子女；結束與中序遍歷二叉樹類似數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第33頁!4.2二叉樹——二叉樹遍歷的非遞歸實現算法思想建立棧Stack；t指向根；當t不空或Stack不空時反復做：若t不空：(t,L)入棧；t指向左子女；否則：出棧頂元素到t和tag中；若tag==R：訪問t；t置空；否則（t,R）入棧；并讓t指向右子女；結束數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第34頁!4.2二叉樹——二叉樹遍歷的非遞歸實現BEACroot(A.L)入棧(A.L)(B.L)入棧(A.L)(B.L)(B.L)退棧(A.L)(B.R)入棧(A.L)(B.R)(E.L)入棧(A.L)(B.R)(E.L)(E.L)退棧(A.L)(B.R)(E.R)入棧(A.L)(B.R)(E.R)(E.R)退棧(A.L)(B.R)訪問E(B.R)退棧(A.L)訪問B(A.L)退棧(A.R)入棧(A.R)(C.L)入棧(A.R)(C.L)(C.L)退棧(A.R)(C.R)入棧(A.R)(C.R)(C.R)退棧(A.R) 訪問C(A.R)退棧 訪問A12345678910111213141516數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第35頁!4.2二叉樹——二叉樹遍歷的非遞歸實現算法4.9逐層遍歷voidLevelOrder(voidVisit(BinaryTreeNode*＆)){LinkedQueueq;BinaryTreeNode*t;t=root;if(t)q.Enter(t);while(!q.Empty()){t=q.Leave();Visit(t);//先入隊，出隊時訪問if(t->leftChild)q.Enter(t->leftChild);if(t->rightChild)q.Enter(t->rightChild);}//while}//LevelOrder數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第36頁!4.2二叉樹——線索二叉樹給二叉樹加線索的過程是線索化（穿線）按前序遍歷序列線索化的二叉樹是前序線索二叉樹按中序遍歷序列線索化的二叉樹是中序線索二叉樹按后序遍歷序列線索化的二叉樹是后序線索二叉樹中序線索二叉樹簡稱線索二叉樹數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第37頁!4.2二叉樹——線索二叉樹例，前序線索化二叉樹和后序線索化二叉樹后序線索二叉樹后序遍歷序列：CBEDA前序線索二叉樹前序遍歷序列：ABDCE數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第38頁!4.2二叉樹——線索二叉樹結點類的定義classThrBNode{ DataTypedata; boolltag,rtag; ThrBNode*leftchild,*rightchild;Public:ThrBNode(DataTyped){ data=d;leftchild=rightchild=NULL; ltag=rtag=false;}}//ThrBNode數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第39頁!4.2二叉樹——線索二叉樹中序線索二叉樹的類定義classInThrBTree//Thread_Binary_tree{ThrBNode*thrt;//頭指針

ThrBNode*GetFirstNode(ThrBNode*);ThrBNode*GetNextNode(ThrBNode*);ThrBNode*GetNextNodePre(ThrBNode*);public:InThrBTree(){thrt=newThrBNode();}voidCreateBTree(ThrBNode*&t=thrt);voidMakeTree(DataType&data,InThrBTree&left,InThrBTree&right);voidInOrderThreading(ThrBNode*&bt=thrt);//線索化voidInOrder(voidVisit(ThrBNode*));voidPreOrder(voidVisit(ThrBNode*));};//InThrBTree數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第40頁!4.2二叉樹——線索二叉樹算法4.13voidInOrderThreading(Thread*&bt=thrt){ Stackstack;p=bt->leftChild;pre=thrt;//指向根

while(p||!stack.IsEmpty){ if(p){stack.push(p);p=p->leftChild;}//p向左走一步

else{p=stack.pop(); //出棧頂元到p中

if(!p->leftChild){p->leftChild=pre;p->lTag=true;} if(pre&&!pre->rightChild){pre->rightChild=p;pre->rTag=true;} pre=p;p=p->rchild;//p向右走一步}

}}數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第41頁!4.2二叉樹——線索二叉樹算法思想1）找到序列的個結點p;2）當p不是頭結點時，反復執行：訪問p;

找出p的后繼r;p=r;關鍵問題1沿著根的左鏈走直到無左子女的結點r，即中序序列中的個結點p=thrt->leftChild;while(!p->lTag)p=p->leftChild;關鍵問題2，有如下兩種情況：p無右子女：則p->rightChild是p的后繼；p有右子女：則p的右子樹的中序序列的個結點是p的后繼，方法同關鍵問題1。數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第42頁!4.2二叉樹——線索二叉樹算法（續）ThrBNode*GetFirstNode(ThrBNode*p){while(!p->lTag)p=p->lefChild;

returnp;}ThrBNode*GetNextNode(ThrBNode*p){if(p->rTag)returnp->rightChild;

r=p->rightChild;

r=GetFirstNode(r);

returnr;}數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第43頁!4.2二叉樹——線索二叉樹算法4.12ThrBNode*GetNextNodePre(ThrBNode*p){if(!p->lTag)returnp->lefChild;//p有左子女

if(!p->rTag)returnp->rightChild;//p有右子女

r=p.rightChild; //p是葉

while(r!=thrt&&r->rTag)r=r->rightChild;if(r!=thrt)returnr->rightChild;elsereturnr;}voidPreOrder(){p=thrt->leftChild;while(p!=thrt){Visit(p);p=GetNextNodePre(p);}}數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第44頁!4.3樹與森林——樹與森林的遍歷例先根次序序列：ABCDE前序遍歷序列：ABCDE結論：

樹的先根次序遍歷結果與其對應二叉樹表示的前序遍歷結果相同。數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第45頁!4.3樹與森林——樹與森林的遍歷森林的遍歷先根次序遍歷的算法思想若森林F為空，則返回；否則 訪問F的棵樹的根結點先根次序遍歷棵樹的子樹森林先根次序遍歷其它樹組成的森林先根次序遍歷序列ABCDEFGHIKJ結論：森林的先根次序遍歷結果與其對應二叉樹表示的前序遍歷結果相同。數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第46頁!4.3樹與森林——樹的存儲結構雙親表示法數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第47頁!4.3樹與森林——樹的存儲結構孩子表示法（子女表示法）abcdefhgiacdefghib501234578datafirstchild

1

2^

3

4^^

8

6

7

^

5^^^^如何找雙親結點?^數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第48頁!4.3樹與森林——樹的存儲結構子女－兄弟表示法也稱二叉樹表示法或二叉鏈表表示法TreeNode

firstChildnextSiblingdata數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第49頁!4.4森林與二叉樹的關系森林與二叉樹的對應關系數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第50頁!4.4森林與二叉樹的關系自然轉換法凡是兄弟用線連起來，然后去掉雙親到子女的連線，但保留雙親到其子女的連線，最后轉45°保留每個結點的邊（紅色），兄弟間加橫邊，根間加橫邊（綠色）。去掉其它邊（淡藍色），邊在左，橫邊在右。ABCDEFGHIJABCDEFGHIJ數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第51頁!4.4森林與二叉樹的關系自然轉換法若某結點是其雙親的左孩子，則該結點的右孩子、右孩子的右孩子…，都與該結點的雙親連接起來，最后去掉所有雙親到右孩子的連線。ABCDEFGHIJABCDEFGHIJ數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第52頁!4.5Huffman樹與編碼結點的路徑長度從根結點到該結點的路徑上分支的數目樹的路徑長度樹中每個結點的路徑長度之和（結點）帶權路徑長度＝結點的路徑長度×結點的權＝li×wi樹的帶權路徑長度(WeightedPathLength,WPL)樹的各葉結點所帶的權值與該結點到根的路徑長度的乘積的和數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第53頁!4.5Huffman樹與編碼設K={k1,k2,…,kn}，它們的權W={w1,w2,…,wn}，構造以k1,k2,…,kn為葉結點的擴充二叉樹，使得

為最小，則稱之為最優二叉樹或HuffmanTree6412最優二叉樹數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第54頁!4.5Huffman樹與編碼HuffmanTree的構造算法由給定的n個權值{w1,w2,…,wn}，構造具有n棵擴充二叉樹的集合F={T1,T2,…,Tn}，其中每一棵擴充二叉樹Ti

只有一個帶有權值wi

的根結點，其左、右子樹均為空。重復以下步驟，直到F中僅剩下一棵樹為止在F中選取兩棵根結點的權值最小的擴充二叉樹,做為左、右子樹構造一棵新的二叉樹。置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值之和。在F中刪去這兩棵二叉樹。把新的二叉樹加入F。數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第55頁!4.5Huffman樹與編碼Huffman編碼定義設字符集為{c1,c2,…,cn}，看作葉結點出現概率為{w1,w2,…,wn}，看作葉結點的權（1）構造Huffman樹（2）左分支標0，右分支標1（3）根到葉結點ci

的路徑上的二進制編碼就是ci的編碼數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第56頁!4.5Huffman樹與編碼采用靜態鏈表建立Huffman樹用n個葉結點構造出的最優二叉樹共有幾個結點？因為n0=n2+1，所以n2=n0-1，又由于在最優二叉樹中沒有度為1的結點，所以在最優二叉樹中總的結點數為n0+n2=n+n-1=2n-1構造最優樹時共執行n-1次循環，每次增加一個新結點，共增加了n-1個結點，所以結點總數一定是n+n-1=2n-1數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第57頁!4.5Huffman樹與編碼public:Huffman(intm){n=m;tree=newNodeType[2*n-1];//前n個元素對應葉結點，最后一個元素存放根

for(k=0;k<n;k++){//對于外部結點，其ch域置為它所代表的字符

cin>>ch>>w;tree[k]={ch,w,0,0,0};}//for}voidCreatHTree();//構造Huffman樹voidGetCode();//得到每個葉結點的編碼}//Huffman樹數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第58頁!4.5Huffman樹與編碼voidCreatHTree(){for(i=n;i<2*n-1;i++){SelectMins(i,p1,p2);//在tree[0..k-1]中選最小的2棵樹

tree[p1].parent=tree[p2].parent=i;//p1,p2作k的子女

tree[i].leftChild=p1;tree[i].rightChild=p2;tree[i].w=tree[p1].w+tree[p2].w;}//for}//CreatHTree數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第59頁!52746weightparentlchildrchild

7

0

0

05

0

0

02

0

0

04

0

0

06

0

0

0

0

0

0

0

0

00123456p1p24423i數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第60頁!5274611weightparentlchildrchild0123456p1p26605i18

7

0

0

05

0

0

02

4

0

04

4

0

06

0

2

311

0

1

418

0

0

0數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第61頁!4.5Huffman樹與編碼求每個字符的哈夫曼編碼算法voidGetCode(){code=newString[n];for(k=0;k<n;k++){//從葉子到根逆向求編碼

p=k;while((q=tree[p].parent)!=0){if(tree[q].leftChild==p)code[k]+=”0”;elsecode[k]+=”1”p=q;}code[k].reverse();}//for}//GetCode數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第62頁!4.5Huffman樹與編碼例，最佳判定樹——考試成績分布表數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第63頁!4.5Huffman樹與編碼最佳判定樹不及格及格中良優<60?<70?<80?<90?50.350.15≥≥≥≥<<<<WPL=0.10*3+0.15*3+0.25*2+0.35*2+0.15*2=0.3+0.45+0.5+0.7+0.3=2.25數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第64頁!4.5Huffman樹與編碼因各字符出現的概率為{2/18,7/18,4/18,5/18}。化整為{2,7,4,5}，以它們為各葉結點上的權值建立哈夫曼樹。左分支賦0，右分支賦1，得哈夫曼編碼（變長編碼）

A:0T:10C:110S:111它的總編碼長度=7*1+5*2+(2+4)*3=35。比等長編碼的情形要短總編碼長度正好等于哈夫曼樹的帶權路徑長度WPL。哈夫曼編碼是一種無前綴編碼。解碼時不會混淆數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第65頁!書面作業p1254-3，4-4，4-10，4-11，4-14，4-17實驗題實驗5，實驗6數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第66頁!4.1樹（Tree）的定義和基本術語樹的定義

樹是由n（n0）個結點組成的有限集合如果n＝0，稱為空樹如果n>0，則：有一個特定的稱之為根（root）的結點，它只有直接后繼，但沒有直接前驅；除根以外的其它結點劃分為m（m0）個互不相交的有限集合T0,T1,…,Tm-1，每個集合又是一棵樹，并且稱之為根的子樹（subTree）。每棵子樹的根結點有且僅有一個直接前驅，但可以有0個或多個直接后繼。樹的定義具有遞歸性數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第67頁!4.1樹（Tree）的定義和基本術語樹的術語結點(node)結點的度(degree)分支(branch)結點葉(leaf)結點子女(child)結點雙親(parent)結點兄弟(sibling)結點祖先(ancestor)結點子孫(descendant)結點結點所處層次(level)樹的高度(depth)樹的度(degree)有序樹無序樹森林數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第68頁!4.1樹（Tree）的定義和基本術語結點所在的層次（level）樹根的層次為1其它任一結點所在的層次是其雙親的層次加1深度或高度（depth）結點所在的層次的最大層數12345兄弟（sibling）具有同一雙親的結點互稱兄弟堂兄弟（cousin）在同層的非兄弟結點互稱堂兄弟數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第69頁!4.1樹（Tree）的定義和基本術語ABCDEFGHIJKLM結點A的度：3結點B的度：2結點M的度：0葉子：K，L，F，G，M，I，J結點A的孩子：B，C，D結點B的孩子：E，F結點I的雙親：D結點L的雙親：E結點B，C，D為兄弟結點K，L為兄弟樹的度：3結點A的層次：1結點M的層次：4樹的高度：4結點A是結點F、G的祖先數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第70頁!4.2二叉樹——ADT二叉樹二叉樹（BinaryTree）是有限個結點的集合（可以為空）當二叉樹非空時，其中有且僅有一個稱為根的結點，余下的結點（如果有的話）被分為兩棵互不相交的二叉樹，分別稱為根的左子樹和右子樹數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第71頁!4.2二叉樹——ADT二叉樹二叉樹的5種基本形態

空

只有根

右子樹空

左子樹空

左、右子樹非空問題：具有3個結點的二叉樹可能有幾種不同形態？數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第72頁!4.2二叉樹——ADT二叉樹SizeProcess：計算二叉樹的結點數sizeOutput：sizeHeightProcess：計算二叉樹的高度heightOutput：heightRootProcess：xOutput：置二叉樹的根結點的值為xParentInput：node是二叉樹中的一個結點

Process：求node的雙親p，若node是根，則p為空

Output：p數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第73頁!4.2二叉樹——ADT二叉樹

InOrderInput：Visit()是結點訪問函數

Process：按中序遍歷對二叉樹中每個結點調用Visit()1次且僅1次

Output：根據Visit()，按中序遍歷序列得到結果PostOrderInput：Visit()是結點訪問函數

Process：按后序遍歷對二叉樹中每個結點調用Visit()1次且僅1次

Output:根據Visit()，按后序遍歷序列得到結果

LevelOrderInput：Visit()是結點訪問函數

Process：按層次對二叉樹中每個結點調用Visit()1次且僅1次

Output：根據Visit()，按層次遍歷序列得到結果}ADTBinaryTree數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第74頁!4.2二叉樹——二叉樹的性質性質2高度為k的二叉樹最多有2k－1個結點。（k1）證明：基于上一條性質，深度為k的二叉樹上的結點數至多為

20+21+

+2k-1=2k-1

數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第75頁!4.2二叉樹——二叉樹的性質性質4具有n個結點的二叉樹的高度最小為

log2(n+1)證明：由性質2，高度為h的二叉樹最多有2h-1個結點，即n2h-1

因此h≥log2(n+1)

因為h只能是整數，所以，h≥log2(n+1)注：x

：表示不小于x的最小整數x：表示不大于x的最大整數數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第76頁!4.2二叉樹——二叉樹的性質性質5在編號的完全二叉樹中，有以下關系：若i=1，則i無雙親若i>1，則i的雙親的編號為i/2

若2*i≤n，則i的左子女的編號為2*i若2*i+1≤n，則i的右子女的編號為2*i+1若i為偶數，且i≠n，則其右兄弟的編號為i+1若i為奇數，且i≠1，則其左兄弟的編號為i-1數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第77頁!4.2二叉樹——二叉樹的實現一般二叉樹的順序存儲表示注：由于一般二叉樹必須仿照完全二叉樹那樣存儲，可能會浪費很多存儲空間，單支樹就是一個極端情況。134678913152123456789101112131415數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第78頁!4.2二叉樹——二叉樹的實現例數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第79頁!4.2二叉樹——二叉樹的實現二叉鏈表類的定義classBinaryTree{BinaryTreeNode*root; //根結點指針public:BinaryTree(){root=NULL;}//創建一個空的二叉樹；boolIsEmpty();//如果二叉樹為空，則返回true，否則返回falseboolRoot(DataType&x);//置x為根結點值；若操作失敗，則返回false，否則返回truevoidCreateBinaryTree(BinaryTreeNode*&t=root);//通過擴充二叉樹的前序遍歷序列，創建二叉樹voidMakeTree(DataType&data，BinaryTree&left，BinaryTree&right); //創建二叉樹，data為根結點值，left作為左子樹，right作為右子樹數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第80頁!4.2二叉樹——二叉樹的實現基本操作的實現判斷二叉樹是否為空boolIsEmpty(){return(root?false:true);}置x為根結點的值，如果沒有根結點，則返回falseboolRoot(DataType&x){if(root){root->data=x;returntrue;}returnfalse;//沒有根結點}數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第81頁!4.2二叉樹——二叉樹的遍歷二叉樹的遍歷（TraversingBinaryTree）遵從某種次序，遍訪二叉樹中的所有結點，要求每個結點訪問一次且僅訪問一次。“訪問”的含義可以很廣，如：輸出結點的信息等。

設訪問根結點

記作

V

遍歷根的左子樹記作

L

遍歷根的右子樹記作

R

則可能的遍歷次序有

前序VLR鏡像VRL

中序LVR鏡像RVL

后序LRV鏡像RLVVLR123數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第82頁!4.2二叉樹——二叉樹的遍歷中序遍歷（InorderTraversal）若二叉樹為空，則空操作；否則中序遍歷左子樹(L)；訪問根結點(V)；中序遍歷右子樹(R)。例遍歷結果

a+b*c-d-e/f數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第83頁!4.2二叉樹——二叉樹的遍歷例ABCEFHGABCEFHG前序遍歷序列：ABEHGCF中序遍歷序列：ABCEFHGEBGHAFC后序遍歷序列：ABCEFHGEGHBFCA數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第84頁!4.2二叉樹——二叉樹的遍歷中序遍歷的遞歸算法outTypeInOrder(outTypevisit(BinaryTreeNode*&),BinaryTreeNode*&t=root){//中序遍歷

if(t){InOrder(Visit,t->leftChild);Visit(t);InOrder(Visit,t->rightChild);}}//preorder數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第85頁!4.2二叉樹——二叉樹的遍歷后序遍歷的遞歸算法outTypePostOrder(outTypevisit(BinaryTreeNode*&),BinaryTreeNode*&t=root){//后序遍歷

if(t){PostOrder(Visit,t->leftChild);PostOrder(Visit,t->rightChild);Visit(t);}}//preorder數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第86頁!4.2二叉樹——二叉樹的遍歷以前序遍歷序列建立二叉樹的算法voidCreateBinaryTree(BinaryTreeNode*&t=root){DataTypeu;cin>>u;if(!u)t=NULL;else{t=newBinaryTreeNode(u);CreateBinaryTree(t->leftChild);CreateBinaryTree(t->rightChild);}}數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第87頁!4.2二叉樹——二叉樹的遍歷若已知一棵二叉樹的前序（或中序，或后序，或層序）序列，能否唯一確定這棵二叉樹呢？ABC例：已知前序序列為ABC，則可能的二叉樹有5種。ABC數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第88頁!4.2二叉樹——二叉樹的遍歷若已知一棵二叉樹的前序序列和中序序列，能否唯一確定這棵二叉樹呢？怎樣確定？例如：已知一棵二叉樹的前序遍歷序列和中序遍歷序列分別為ABCDEFGHI和BCAEDGHFI，如何構造該二叉樹呢?數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第89頁!4.2二叉樹——二叉樹的遍歷前序：FG

HI中序：GHFI前序：DEFGHI中序：EDGHFIABCDEFGHIABCDEFIGH數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第90頁!4.2二叉樹——二叉樹的遍歷遍歷二叉樹是二叉樹各種操作的基礎，遍歷算法中對每個結點的訪問操作可以是多種形式及多個操作根據遍歷算法的框架，適當修改訪問操作的內容，可以派生出很多關于二叉樹的應用算法。voidInOrder(BiNode<T>*root){if(root==NULL)return;else{InOrder(root->lchild);cout<<root->data;InOrder(root->rchild);}}數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第91頁!4.2二叉樹——二叉樹遍歷的非遞歸實現遞歸算法簡潔，但執行效率不高，因為系統需要維護一個系統工作棧以保證遞歸函數的正確執行有時需要把遞歸算法轉換為非遞歸算法關鍵如何實現由系統完成的遞歸工作棧方法：仿照遞歸算法執行過程中工作棧的狀態變化得到數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第92頁!4.2二叉樹——二叉樹遍歷的非遞歸實現中序遍歷（LVR）例，EBGHAFDCI1#2#3#4#5#6#7#9#8#ABCEFHGDI數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第93頁!4.2二叉樹——二叉樹遍歷的非遞歸實現結論三種遍歷的路線是完全一樣的，每個結點都被經過三次但訪問時間是不同的前序：次經過時訪問*中序：第二次經過時訪問#后序：第三次經過時訪問&遍歷線路的核心規則是：先左后右用一個棧記錄走過的位置，以便返回數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第94頁!4.2二叉樹——二叉樹遍歷的非遞歸實現中序遍歷二叉樹的非遞歸算法思想建立棧Stack；t指向根結點；當t不空或Stack不空時反復做：若t不空，則t入棧；t指向左子女；否則出棧頂元素到t中；訪問t；t指向右子女；結束數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第95頁!4.2二叉樹——二叉樹遍歷的非遞歸實現ABCDEFGt訪問序列&A&B&Ct=NULLCBttt&Dt&Et=NULLEt&GGt=NULLDt&Ft=NULLFAt=NULL數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第96頁!4.2二叉樹——二叉樹遍歷的非遞歸實現后序遍歷二叉樹的非遞歸算法后序遍歷時，訪問一個結點的時間是第3次經過時第3次經過＝第2次返回＝從右邊返回如何區分從左返回還是右返回的呢？t入棧時帶一標記向左走時帶L向右走時帶R數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第97頁!4.2二叉樹——二叉樹遍歷的非遞歸實現后序遍歷二叉樹非遞歸算法voidPostOrder(voidVisit(BinaryTreeNode*＆)){//后序遍歷BinaryTreeNode*t=root;Stackstack;//建立棧while(t||!stack.IsEmpty()){if(t){stack.push((t,‘L’));//(t,L)入棧

t=t->leftChild;//t向左走一步}else{e=stack.pop();t=e.t;tag=e.tag;if(tag==‘R’){Visit(t);t=NULL;}else{stack.push((t,’R’)); t=t->rightChild;//t向右走一步} }//if}//while}//postOrder數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第98頁!4.2二叉樹——二叉樹遍歷的非遞歸實現層次遍歷二叉樹從二叉樹的層（根結點）開始，從上到下逐層遍歷，在同一層中，按照從左到右的順序對結點逐個訪問。例

-+/a*efb–cd數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第99頁!4.2二叉樹——線索二叉樹目的利用二叉樹的空指針指向遍歷序列的前驅、后繼結點，遍歷二叉樹時不需要棧n個結點的二叉樹，有2n個指針，只用了n-1個指針，有n+1個指針是空的線索用空的左指針指向遍歷序列的前驅節點；用空的右指針指向遍歷序列的后繼節點；這兩種指針稱為線索（Thread）加上了線索的二叉樹稱為線索化二叉樹，對應的二叉鏈表稱為線索化二叉鏈表數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第100頁!4.2二叉樹——線索二叉樹例，（中序）線索化二叉樹中序遍歷序列：DBFEACDBFEACNILNIL數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第101頁!4.2二叉樹——線索二叉樹中序線索化二叉樹的建立和遍歷為了區分線索與指針（左右孩子），給每個結點增加兩個域：leftThread和rightThread0,leftChild指向左子女lTag=1,leftChild為前驅線索

0,rightChild指向右子女rTag=

1,rightChild為后繼線索leftChildlTagdatarTagrightChild數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第102頁!4.2二叉樹——線索二叉樹例ABGCDEF0A0

0B0

0C1中序線索二叉樹

thrt01

1D1

1E0

1G1

1F1數據結構與算法第四章清華大學出版社趙玉蘭共130頁，您現在瀏覽的是第103頁!4.2二叉樹——線索二叉樹