《數(shù)據(jù)結(jié)構(gòu)：思想與方法》第五章樹

1第五章樹樹的概念二叉樹表達(dá)式樹哈夫曼樹與哈夫曼編碼樹和森林2樹的概念樹的定義樹的術(shù)語樹的運(yùn)算3樹的定義樹是n(n≥1)個結(jié)點(diǎn)的有限集合T，并且滿足：(1)有一個被稱之為根(root)的結(jié)點(diǎn)(2)其余的結(jié)點(diǎn)可分為m(m≥0)個互不相交的集合Tl，T2，…，Tm，這些集合本身也是一棵樹，并稱它們?yōu)楦Y(jié)點(diǎn)的子樹(Subree)。每棵子樹同樣有自己的根結(jié)點(diǎn)。ADCBFEGJIHLKM4樹的概念樹的定義樹的術(shù)語樹的運(yùn)算5根結(jié)點(diǎn)、葉結(jié)點(diǎn)、內(nèi)部節(jié)點(diǎn)結(jié)點(diǎn)的度和樹的度兒子結(jié)點(diǎn)父親結(jié)點(diǎn)兄弟結(jié)點(diǎn)祖先結(jié)點(diǎn)子孫結(jié)點(diǎn)結(jié)點(diǎn)所處層次樹的高度有序樹無序樹森林

樹的術(shù)語ADCBFEGJIHLKM6樹的概念樹的定義樹的術(shù)語樹的運(yùn)算7樹的常用操作建樹create()：創(chuàng)建一棵空樹；清空clear()：刪除樹中的所有結(jié)點(diǎn)；判空IsEmpty()：判別是否為空樹；找根結(jié)點(diǎn)root()：找出樹的根結(jié)點(diǎn)。如果樹是空樹，則返回一個特殊的標(biāo)記；找父結(jié)點(diǎn)parent(x)：找出結(jié)點(diǎn)x的父結(jié)點(diǎn)；找子結(jié)點(diǎn)child(x,i)：找結(jié)點(diǎn)x的第i個子結(jié)點(diǎn)；剪枝delete(x,i)：刪除結(jié)點(diǎn)x的第i棵子樹；構(gòu)建一棵樹MakeTree（x,T1,T2,……,Tn）：構(gòu)建一棵以x為根結(jié)點(diǎn)，以T1,T2,……,Tn為第i棵子樹的樹；遍歷traverse()：訪問樹上的每一個結(jié)點(diǎn)。8第五章樹樹的概念二叉樹表達(dá)式樹哈夫曼樹與哈夫曼編碼樹和森林9二叉樹二叉樹的概念二叉樹的性質(zhì)二叉樹的基本運(yùn)算二叉樹的遍歷二叉樹的實(shí)現(xiàn)二叉樹類二叉樹遍歷的非遞歸實(shí)現(xiàn)10二叉樹的定義

二叉樹（BinaryTree）是結(jié)點(diǎn)的有限集合，它或者為空，或者由一個根結(jié)點(diǎn)及兩棵互不相交的左、右子樹構(gòu)成，而其左、右子樹又都是二叉樹。注意：二叉樹必須嚴(yán)格區(qū)分左右子樹。即使只有一棵子樹，也要說明它是左子樹還是右子樹。交換一棵二叉樹的左右子樹后得到的是另一棵二叉樹。11二叉樹的基本形態(tài)(a)空二叉樹(b)根和空的左右子樹(c)根和左右子樹(d)根和左子樹(e)根和右子樹左子樹右子樹左子樹右子樹12結(jié)點(diǎn)總數(shù)為3的所有二叉樹的不同形狀13一棵高度為k并具有2k－1個結(jié)點(diǎn)的二叉樹稱為滿二叉樹。一棵二叉樹中任意一層的結(jié)點(diǎn)個數(shù)都達(dá)到了最大值滿二叉樹14DCGEFBAHKIJOLNM滿二叉樹實(shí)例不是滿二叉樹DCGEFBAHIJ15完全二叉樹在滿二叉樹的最底層自右至左依次(注意：不能跳過任何一個結(jié)點(diǎn))去掉若干個結(jié)點(diǎn)得到的二叉樹也被稱之為完全二叉樹。滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹。完全二叉樹的特點(diǎn)是：（1）所有的葉結(jié)點(diǎn)都出現(xiàn)在最低的兩層上。（2）對任一結(jié)點(diǎn)，如果其右子樹的高度為k，則其左子樹的高度為k或k＋1。1601234完全二叉樹非完全二叉樹DCGEFBAHIJ17二叉樹二叉樹的概念二叉樹的性質(zhì)二叉樹的基本運(yùn)算二叉樹的遍歷二叉樹的實(shí)現(xiàn)二叉樹類二叉樹遍歷的非遞歸實(shí)現(xiàn)18二叉樹的性質(zhì)1

一棵非空二叉樹的第i層上最多有2i-1個結(jié)點(diǎn)（i≥1）。BCDEFLA1層：結(jié)點(diǎn)個數(shù)21-1=1個2層：結(jié)點(diǎn)個數(shù)22-1=2個3層：結(jié)點(diǎn)個數(shù)23-1=4個19證明：當(dāng)i=1時，只有一個根結(jié)點(diǎn)，2i-1=20=1,命題成立。

假定對于所有的j，1≤j≤k,命題成立。即第j層上至多有2j-1個結(jié)點(diǎn)。由歸納假設(shè)可知，第j=k層上至多有2k-1個結(jié)點(diǎn)。若要使得第k+1層上結(jié)點(diǎn)數(shù)為最多，那么，第k層上的每個結(jié)點(diǎn)都必須有二個兒子結(jié)點(diǎn)。因此，第k+1層上結(jié)點(diǎn)數(shù)最多為為第k層上最多結(jié)點(diǎn)數(shù)的二倍，即：2×2k-1＝2k+1-1＝2k。所以，命題成立。20二叉樹的性質(zhì)2

一棵高度為k的二叉樹，最多具有2k－1個結(jié)點(diǎn)。

證明：這棵二叉樹中的每一層的結(jié)點(diǎn)個數(shù)必須最多。根據(jù)性質(zhì)1，第i層的結(jié)點(diǎn)數(shù)最多為等于2i-1，因此結(jié)點(diǎn)個數(shù)N最多為：

21對于一棵非空二叉樹，如果葉子結(jié)點(diǎn)數(shù)為n0，度數(shù)為2的結(jié)點(diǎn)數(shù)為n2，則有:n0＝n2＋1成立。二叉樹的性質(zhì)322證明：設(shè)n為二叉樹的結(jié)點(diǎn)總數(shù)，n1為二叉樹中度數(shù)為

1的結(jié)點(diǎn)數(shù)。二叉樹中所有結(jié)點(diǎn)均小于或等于2，所以有：

n＝n0＋n1＋n2

再看二叉樹中的樹枝(父結(jié)點(diǎn)和兒子結(jié)點(diǎn)之間的線段)總數(shù)。在二叉樹中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有唯一的一個樹枝進(jìn)入本結(jié)點(diǎn)。性質(zhì)3證明23設(shè)B為二叉樹中的樹枝數(shù)，那么有下式成立：

B＝n－1這些樹枝都是由度為1和度為2的結(jié)點(diǎn)發(fā)出的，一個度為1的結(jié)點(diǎn)發(fā)出一個樹枝，一個度為2的結(jié)點(diǎn)發(fā)出兩個樹枝，所以有：

B＝n1＋2n2

因此，n0＝n2＋124二叉樹的性質(zhì)4具有n個結(jié)點(diǎn)的完全二叉樹的高度k=log2n+1證明根據(jù)完全二叉樹的定義和性質(zhì)2可知，高度為k的完全二叉樹的第一層到第k-1層具有最多的結(jié)點(diǎn)個數(shù)，總數(shù)為2k-1-1個，第k層至少具有一個結(jié)點(diǎn)，至多有2k-1個結(jié)點(diǎn)。因此，

2k-1–1<n≤2k-1即2k-1≤n<2k對不等式取對數(shù)，有

k-1≤log2n<k

由于k是整數(shù)，所以有：k=log2n

＋125二叉樹的性質(zhì)5

如果對一棵有n個結(jié)點(diǎn)的完全二叉樹中的結(jié)點(diǎn)按層自上而下（從第1層到第log2n+1層），每一層按自左至右依次編號。若設(shè)根結(jié)點(diǎn)的編號為1。則對任一編號為i的結(jié)點(diǎn)（1≤i≤n),有：（1）如果i＝1，則該結(jié)點(diǎn)是二叉樹的根結(jié)點(diǎn)；如果i>1，則其父親結(jié)點(diǎn)的編號為i/2

。（2）如果2i>n，則編號為i的結(jié)點(diǎn)為葉子結(jié)點(diǎn)，沒有兒子；否則，其左兒子的編號為2i。（3）如果2i+1>n，則編號為i的結(jié)點(diǎn)無右兒子；否則，其右兒子的編號為2i+1。26BDEFLAPSQRU121110987654321C27二叉樹二叉樹的概念二叉樹的性質(zhì)二叉樹的基本運(yùn)算二叉樹的遍歷二叉樹的實(shí)現(xiàn)二叉樹類二叉樹遍歷的非遞歸實(shí)現(xiàn)28二叉樹常用操作建樹create()：創(chuàng)建一棵空的二叉樹；清空clear()：刪除二叉樹中的所有結(jié)點(diǎn)；判空IsEmpty()：判別二叉樹是否為空樹；找根結(jié)點(diǎn)root()：找出二叉樹的根結(jié)點(diǎn)。找父結(jié)點(diǎn)parent(x)：找出結(jié)點(diǎn)x的父結(jié)點(diǎn)；找左孩子lchild(x)：找結(jié)點(diǎn)x的左孩子結(jié)點(diǎn)；找右孩子rchild(x)：找結(jié)點(diǎn)x的右孩子結(jié)點(diǎn)；刪除左子樹delLeft(x)：刪除結(jié)點(diǎn)x的左子樹；刪除右子樹delRight(x)：刪除結(jié)點(diǎn)x的右子樹；構(gòu)建一棵樹MakeTree（x,TL,TR）：構(gòu)建一棵以x為根結(jié)點(diǎn)，以TL，TR為左右子樹的二叉樹；遍歷traverse()：訪問二叉樹上的每一個結(jié)點(diǎn)。29二叉樹二叉樹的概念二叉樹的性質(zhì)二叉樹的基本運(yùn)算二叉樹的遍歷二叉樹的實(shí)現(xiàn)二叉樹類二叉樹遍歷的非遞歸實(shí)現(xiàn)30二叉樹的遍歷二叉樹的遍歷討論的是如何訪問到樹上的每一個結(jié)點(diǎn)在線性表中，我們可以沿著后繼鏈訪問到所有結(jié)點(diǎn)。而二叉樹是有分叉的，因此在分叉處必須確定下一個要訪問的節(jié)點(diǎn)：是根結(jié)點(diǎn)、左結(jié)點(diǎn)還是右結(jié)點(diǎn)根據(jù)不同的選擇，有三種遍歷的方法：前序、中序和后序31前序遍歷如果二叉樹為空，則操作為空否則訪問根結(jié)點(diǎn)前序遍歷左子樹前序遍歷右子樹32中序遍歷如果二叉樹為空，則操作為空否則中序遍歷左子樹訪問根結(jié)點(diǎn)中序遍歷右子樹33后序遍歷如果二叉樹為空，則操作為空否則后序遍歷左子樹后序遍歷右子樹訪問根結(jié)點(diǎn)34前序：A、L、B、E、C、D、W、X中序：B、L、E、A、C、W、X、D后序：B、E、L、X、W、D、C、ABCDELAXW35前序＋中序唯一確定一棵二叉樹

前序:A、B、D、E、F、C

中序:D、B、E、F、A、C

前序:B、D、E、F

中序:D、B、E、F

前序:E、F

中序:E、FD、B、E、FA

CACBABCD

E、FEFABCD36同理，由二叉樹的后序序列和中序序列同樣可以唯一地確定一棵二叉樹但是，已知二叉樹的前序遍歷序列和后序遍歷序列卻無法確定一棵二叉樹。比如：已知一棵二叉樹的前序遍歷序列為A、B，后序遍歷序列為B、A，我們雖然可以很容易地得知結(jié)點(diǎn)A為根結(jié)點(diǎn)，但是無法確定結(jié)點(diǎn)B是結(jié)點(diǎn)A的左兒子還是右兒子，因?yàn)锽無論是結(jié)點(diǎn)A的右兒子還是左兒子都是符合已知條件的。37二叉樹二叉樹的概念二叉樹的性質(zhì)二叉樹的基本運(yùn)算二叉樹的遍歷二叉樹的實(shí)現(xiàn)二叉樹類二叉樹遍歷的非遞歸實(shí)現(xiàn)38二叉樹的實(shí)現(xiàn)順序?qū)崿F(xiàn)鏈接實(shí)現(xiàn)39完全二叉樹的順序存儲

BCDEFLAPSQRU212111098765431根據(jù)編號性質(zhì)，可以省略左右孩子字段01A2L3B4B5E6F7D8P9Q10R11S12U40普通二叉樹的順序存儲

DBAHI將普通的樹修補(bǔ)成完全二叉樹01A2B3∧

4D5∧

6∧

7∧

8H9I41右單支樹的實(shí)例CGA01A2∧3C4∧5∧

6∧

7G

42順序?qū)崿F(xiàn)的特點(diǎn)存儲空間的浪費(fèi)。一般只用于一些特殊的場合，如靜態(tài)的并且結(jié)點(diǎn)個數(shù)已知的完全二叉樹或接近完全二叉樹的二叉樹。43二叉樹的實(shí)現(xiàn)順序?qū)崿F(xiàn)鏈接實(shí)現(xiàn)44鏈接存儲結(jié)構(gòu)ABCDEFGHIL標(biāo)準(zhǔn)形式：（二叉鏈表）廣義標(biāo)準(zhǔn)形式：（三叉鏈表）LEFTDATARIGHTLEFTDATARIGHTPARENT45標(biāo)準(zhǔn)形式的實(shí)例

AL/\C/\∧B/\/\E/\D/\W/\/\XrootALCXEBWD46廣義標(biāo)準(zhǔn)形式的實(shí)例ALCXEBWDA∧rootLCE∧∧B∧∧D∧W∧X∧∧47二叉樹基本運(yùn)算的實(shí)現(xiàn)由于二叉樹是一個遞歸的結(jié)構(gòu)，因此二叉樹中的許多運(yùn)算的實(shí)現(xiàn)都是基于遞歸函數(shù)。create()：將指向根結(jié)點(diǎn)的指針設(shè)為空指針就可以了，即root=NULL。isEmpty()：只需要判別root即可。如果root等于空指針，返回true，否則，返回false。root()：返回root指向的結(jié)點(diǎn)的數(shù)據(jù)部分。如果二叉樹是空樹，則返回一個特殊的標(biāo)記。48clear()從遞歸的觀點(diǎn)看，一棵二叉樹由三部分組成：根結(jié)點(diǎn)、左子樹、右子樹。刪除一棵二叉樹就是刪除這三個部分。根結(jié)點(diǎn)的刪除很簡單，只要回收根結(jié)點(diǎn)的空間，把指向根結(jié)點(diǎn)的指針設(shè)為空指針。如何刪除左子樹和右子樹呢？記住左子樹也是一棵二叉樹，右子樹也是一棵二叉樹，左右子樹的刪除和整棵樹的刪除過程是一樣的。49If（左子樹非空）遞歸刪除左子樹；If（右子樹非空）遞歸刪除右子樹；deleteroot指向的結(jié)點(diǎn)；root=NULL；50parent(x)：在二叉鏈表的實(shí)現(xiàn)中一般不實(shí)現(xiàn)這個操作lchild(x)：返回結(jié)點(diǎn)x的left值rchild(x)：返回結(jié)點(diǎn)x的right值delLeft(x)：對左子樹調(diào)用clear函數(shù)刪除左子樹，然后將結(jié)點(diǎn)x的left置為NULL。delRight(x)：對右子樹調(diào)用clear函數(shù)刪除右子樹，然后將結(jié)點(diǎn)x的right置為NULL。makeTree（x,TL,TR）：為x申請一個結(jié)點(diǎn)，讓它的left指向TL的根結(jié)點(diǎn)，right指向TR的根結(jié)點(diǎn)。51二叉樹的遍歷前序：訪問根結(jié)點(diǎn)；If（左子樹非空）前序遍歷左子樹；If（右子樹非空）前序遍歷右子樹；其他兩種遍歷只要調(diào)整一下次序即可。52二叉樹二叉樹的概念二叉樹的性質(zhì)二叉樹的基本運(yùn)算二叉樹的遍歷二叉樹的實(shí)現(xiàn)二叉樹類二叉樹遍歷的非遞歸實(shí)現(xiàn)53二叉樹類由于二叉樹的順序?qū)崿F(xiàn)僅用于一些特殊的場合。大多數(shù)情況下，二叉樹都是用二叉鏈表實(shí)現(xiàn)，所以僅介紹用二叉鏈表實(shí)現(xiàn)的二叉樹類。54二叉樹類的設(shè)計(jì)標(biāo)準(zhǔn)的鏈接存儲由兩個類組成：結(jié)點(diǎn)類和樹類。和線性表的實(shí)現(xiàn)類似，這個結(jié)點(diǎn)類是樹類專用的，因此可作為樹類的私有內(nèi)嵌類。55結(jié)點(diǎn)類Node的設(shè)計(jì)存儲和處理樹上每一個結(jié)點(diǎn)的類。數(shù)據(jù)成員包括：結(jié)點(diǎn)的數(shù)據(jù)及左右孩子的指針。結(jié)點(diǎn)的操作包括：構(gòu)造和析構(gòu)56二叉樹類的設(shè)計(jì)樹的存儲：存儲指向根結(jié)點(diǎn)的指針樹的操作：樹的標(biāo)準(zhǔn)操作增加了一個建樹的函數(shù)57遞歸函數(shù)的設(shè)計(jì)對于二叉樹類的用戶來說，他并不需要知道這些操作時用遞歸函數(shù)實(shí)現(xiàn)的。對用戶來說，調(diào)用這些函數(shù)并不需要參數(shù)但遞歸函數(shù)必須有一個控制遞歸終止的參數(shù)設(shè)計(jì)時，我們將用戶需要的函數(shù)原型作為公有的成員函數(shù)。每個公有成員函數(shù)對應(yīng)一個私有的、帶遞歸參數(shù)的成員函數(shù)。公有函數(shù)調(diào)用私有函數(shù)完成相應(yīng)的功能。58二叉樹類的定義template<classType>classBinaryTree{private:structNode{Node*left,*right;//結(jié)點(diǎn)的左、右兒子的地址

Typedata;//結(jié)點(diǎn)的數(shù)據(jù)信息

Node():left(NULL),right(NULL){}

Node(Typeitem,Node*L=NULL,Node*R=NULL):

data(item),left(L),right(R){} ~Node(){}}; Node*root;//二叉樹的根結(jié)點(diǎn)。

59public: BinaryTree():root(NULL){}//構(gòu)造空二叉樹

BinaryTree(constType&value){root=newNode(value);} ~BinaryTree(){clear();} TypegetRoot()const{returnroot->data;} TypegetLeft()const{returnroot->left->data;} TypegetRight()const{returnroot->right->data;} voidmakeTree(constType&x,BinaryTree<,BinaryTree&rt) {root=newNode(x,lt.root,rt.root); lt.root=NULL;rt.root=NULL; } voiddelLeft() {BinaryTreetmp=root->left; root->left=NULL；tmp.clear(); } voiddelRight() {BinaryTreetmp=root->right; root->right=NULL;tmp.clear(); }60boolisEmpty()const{returnroot==NULL;}voidclear(){if(root!=NULL)clear(root);root=NULL;}intsize()const{returnsize(root);}intheight()const{returnheight(root);}voidpreOrder()const；

voidpostOrder()const；

voidmidOrder()const；

voidcreateTree(Typeflag);61private:voidclear(Node*t)；

intheight(Node*t)const；

intsize(Node*t)const；

voidpreOrder(Node*t)const；

voidpostOrder(Node*t)const；

voidmidOrder(Node*t)const；

};62求規(guī)模操作的實(shí)現(xiàn)用遞歸的觀點(diǎn)來看，二叉樹是由根結(jié)點(diǎn)和左右子樹構(gòu)成。因此，樹的規(guī)模應(yīng)該為：左子樹的規(guī)模+右子樹的規(guī)模+1（根）63size()intsize()const{returnsize(root);}intsize(Node*t)const{if(t==NULL)return0; return1+size(t->left)+size(t->right); }64求高度操作的實(shí)現(xiàn)用遞歸的觀點(diǎn)來看，二叉樹是由根結(jié)點(diǎn)和左右子樹構(gòu)成。因此，樹的高度應(yīng)該為：1＋max（左子樹高度，右子樹高度）65height()intheight()const{returnheight(root);}intheight(Node*t)const{if(t==NULL)return0;else{intlt=height(t->left),rt=height(t->right); return1+((lt>rt)?lt:rt); }}66三種遍歷的實(shí)現(xiàn)樹的遍歷本身就是用遞歸形式描述的，因此用遞歸函數(shù)實(shí)現(xiàn)是很自然的67preOrder()voidpreOrder()const{if(root!=NULL){cout<<"\n前序遍歷：";preOrder(root);}}voidpreOrder(Node*t)const{if(t!=NULL){cout<<t->data<<''; preOrder(t->left); preOrder(t->right); }}68midOrder()voidmidOrder()const{if(root!=NULL){ cout<<"\n中序遍歷：";midOrder(root);}}voidmidOrder(Node*t)const{if(t!=NULL){midOrder(t->left); cout<<t->data<<'';midOrder(t->right);} }69postOrder()voidpostOrder()const{if(root!=NULL){cout<<"\n后序遍歷：";postOrder(root);}}voidpostOrder(Node*t)const{if(t!=NULL){postOrder(t->left); postOrder(t->right); cout<<t->data<<'';} }70樹的刪除的實(shí)現(xiàn)樹的刪除可以用遞歸的方法來實(shí)現(xiàn)。先遞歸刪除左右子樹，再刪除根結(jié)點(diǎn)本身71clear()voidclear(){if(root!=NULL)clear(root);root=NULL;}voidclear(Node*t){if(t->left!=NULL)clear(t->left);if(t->right!=NULL)clear(t->right);deletet;}72創(chuàng)建一棵樹創(chuàng)建過程：先輸入根結(jié)點(diǎn)的值，創(chuàng)建根節(jié)點(diǎn)對已添加到樹上的每個結(jié)點(diǎn)，依次輸入它的兩個兒子的值。如果沒有兒子，則輸入一個特定值實(shí)現(xiàn)工具：使用一個隊(duì)列，將新加入到樹中的結(jié)點(diǎn)放入隊(duì)列依次出隊(duì)。對每個出隊(duì)的元素輸入它的兒子73BCDEFLAPSQRU212111098765431隊(duì)列的變化ACLEBCDFEBPDFEQQPDFSRRQPDUSSRQPUUSRQ

USR

US

U

74createTreetemplate<classType>voidBinaryTree<Type>::createTree(Typeflag){linkQueue<Node*>que;Node*tmp;Typex,ldata,rdata;//創(chuàng)建樹，輸入flag表示空

cout<<"\n輸入根結(jié)點(diǎn)：";cin>>x;root=newNode(x);

que.enQueue(root); 75while(!que.isEmpty()){ tmp=que.deQueue(); cout<<"\n輸入"<<tmp->data<<"的兩個兒子("<<flag<<"表示空結(jié)點(diǎn))：";cin>>ldata>>rdata; if(ldata!=flag)que.enQueue(tmp->left=newNode(ldata)); if(rdata!=flag)que.enQueue(tmp->right=newNode(rdata)); } cout<<"createcompleted!\n";}

76二叉樹類的應(yīng)用創(chuàng)建一棵由整型值組成的二叉樹求高度求規(guī)模按前序、中序和后序遍歷歸并兩棵樹77intmain(){BinaryTree<char>tree,tree1('M'),tree2;tree.createTree('@');

cout<<"高度為："<<tree.height()<<endl;cout<<"規(guī)模為："<<tree.size()<<endl;tree.PreOrder();tree.MidOrder();tree.PostOrder();78tree2.makeTree('Y',tree,tree1);cout<<endl;cout<<"高度為："<<tree2.height()<<endl;cout<<"規(guī)模為："<<tree2.size()<<endl;tree2.PreOrder();tree2.MidOrder();tree2.PostOrder();return0;}79BCDELAXW執(zhí)行實(shí)例輸入根結(jié)點(diǎn)：A輸入A的兩個兒子(@表示空結(jié)點(diǎn))：LC輸入L的兩個兒子(@表示空結(jié)點(diǎn))：BE輸入C的兩個兒子(@表示空結(jié)點(diǎn))：@D輸入B的兩個兒子(@表示空結(jié)點(diǎn))：@@輸入E的兩個兒子(@表示空結(jié)點(diǎn))：@@輸入D的兩個兒子(@表示空結(jié)點(diǎn))：W@輸入W的兩個兒子(@表示空結(jié)點(diǎn))：@X輸入X的兩個兒子(@表示空結(jié)點(diǎn))：@@

80高度為：5規(guī)模為：8前序遍歷：ALBECDWX中序遍歷：BLEACWXD后序遍歷：BELXWDCA高度為：6規(guī)模為：10前序遍歷：YALBECDWXM中序遍歷：BLEACWXDYM后序遍歷：BELXWDCAMY

BCDELAXWMY81二叉樹二叉樹的概念二叉樹的性質(zhì)二叉樹的基本運(yùn)算二叉樹的遍歷二叉樹的實(shí)現(xiàn)二叉樹類二叉樹遍歷的非遞歸實(shí)現(xiàn)82二叉樹遍歷的非遞歸實(shí)現(xiàn)遞歸是程序設(shè)計(jì)中強(qiáng)有力的工具。遞歸程序結(jié)構(gòu)清晰、明了、美觀，遞歸程序的弱點(diǎn)：它的時間、空間的效率比較低。所以在實(shí)際使用中，我們常常希望使用它的非遞歸版本二叉樹的遍歷也是如此。盡管二叉樹遍歷的遞歸函數(shù)非常簡潔，但有時我們還是希望使用速度更快的非遞歸函數(shù)。83二叉樹遍歷的非遞歸實(shí)現(xiàn)前序遍歷中序遍歷后序遍歷84前序遍歷的非遞歸實(shí)現(xiàn)前序遍歷第一個被訪問的結(jié)點(diǎn)是根結(jié)點(diǎn)，然后訪問左子樹，最后訪問右子樹?？梢栽O(shè)置一個棧，保存將要訪問的樹的樹根。開始時，把二叉樹的根結(jié)點(diǎn)存入棧中。然后重復(fù)以下過程，直到棧為空：從棧中取出一個結(jié)點(diǎn)，輸出根結(jié)點(diǎn)的值；然后把右子樹，左子樹放入棧中85template<classType>voidBinaryTree<Type>::preOrder()const{linkStack<Node*>s;Node*current;

cout<<"前序遍歷:";s.push(root);while(!s.isEmpty()){ current=s.pop(); cout<<current->data;if(current->right!=NULL)s.push(current->right); if(current->left!=NULL)s.push(current->left);}}86二叉樹遍歷的非遞歸實(shí)現(xiàn)前序遍歷中序遍歷后序遍歷87中序遍歷的非遞歸實(shí)現(xiàn)采用一個棧存放要遍歷的樹的樹根中序遍歷中，先要遍歷左子樹，接下去才能訪問根結(jié)點(diǎn)，因此，當(dāng)根結(jié)點(diǎn)出棧時，我們不能訪問它，而要訪問它的左子樹，此時要把樹根結(jié)點(diǎn)暫存一下。存哪里？由于左子樹訪問完后還要訪問根結(jié)點(diǎn)，因此仍可以把它存在棧中，接著左子樹也進(jìn)棧。此時執(zhí)行出棧操作，出棧的是左子樹。左子樹問結(jié)束后，再次出棧的是根結(jié)點(diǎn)，此時根結(jié)點(diǎn)可被訪問。根結(jié)點(diǎn)訪問后，訪問右子樹，則將右子樹進(jìn)棧。88棧元素的設(shè)計(jì)在中序遍歷中根結(jié)點(diǎn)要進(jìn)棧兩次。當(dāng)要遍歷一棵樹時，將根結(jié)點(diǎn)進(jìn)棧。根結(jié)點(diǎn)第一次出棧時，它不能被訪問，必須重新進(jìn)棧，并將左子樹也進(jìn)棧，表示接下去要訪問的是左子樹。根結(jié)點(diǎn)第二次出棧時，才能被訪問，并將右子樹進(jìn)棧，表示右子樹可以訪問了。在中序遍歷時不僅要記住需要訪問哪一棵樹，而且還必須記住根結(jié)點(diǎn)是在第幾次進(jìn)棧。89StNode類的定義structStNode{Node*node;intTimesPop;StNode(Node*N=NULL):node(N),TimesPop(0){}

};90中序遍歷的非遞歸實(shí)現(xiàn)template<classType>voidBinaryTree<Type>::midOrder()const{linkStack<StNode>s;StNodecurrent(root);

cout<<"中序遍歷:";s.push(current);91while(!s.isEmpty()){ current=s.pop();if(++current.TimesPop==2){ cout<<current.node->data; if(current.node->right!=NULL)s.push(StNode(current.node->right));} else{s.push(current); if(current.node->left!=NULL)s.push(StNode(current.node->left)); }} }92二叉樹遍歷的非遞歸實(shí)現(xiàn)前序遍歷中序遍歷后序遍歷93后序遍歷的非遞歸實(shí)現(xiàn)將中序遍歷的非遞歸實(shí)現(xiàn)的思想進(jìn)一步延伸，可以得到后序遍歷的非遞歸實(shí)現(xiàn)。當(dāng)以后序遍歷一棵二叉樹時，先將樹根進(jìn)棧，表示要遍歷這棵樹。根結(jié)點(diǎn)第一次出棧時，根結(jié)點(diǎn)不能訪問，應(yīng)該訪問左子樹。于是，根結(jié)點(diǎn)重新入棧，并將左子樹也入棧。根結(jié)點(diǎn)第二次出棧時，根結(jié)點(diǎn)還是不能訪問，要先訪問右子樹。于是，根結(jié)點(diǎn)再次入棧，右子樹也入棧。當(dāng)根結(jié)點(diǎn)第三次出棧時，表示右子樹遍歷結(jié)束，此時，根結(jié)點(diǎn)才能被訪問。94后序遍歷的非遞歸實(shí)現(xiàn)template<classType>voidBinaryTree<Type>::postOrder()const{ linkStack<StNode>s; StNodecurrent(root);cout<<"后序遍歷:"; s.push(current);95while(!s.isEmpty()){current=s.pop();if(++current.TimesPop==3){cout<<current.node->data;continue;}s.push(current);if(current.TimesPop==1){if(current.node->left!=NULL) s.push(StNode(current.node->left)); }else{ if(current.node->right!=NULL) s.push(StNode(current.node->right)); } }}96第五章樹樹的概念二叉樹表達(dá)式樹哈夫曼樹與哈夫曼編碼樹和森林97表達(dá)式樹算術(shù)表達(dá)式可以表示為一棵二叉樹，如:(4-2)*(10+(4+6)/2)+2對這棵樹后序遍歷可得到結(jié)果設(shè)計(jì)一個類，利用表達(dá)式樹計(jì)算由四則運(yùn)算組成的表達(dá)式+*+/210+64-42298樹的構(gòu)建過程3*4+5*7*9+8構(gòu)建左節(jié)點(diǎn)33*4+5*7*9+8構(gòu)建根節(jié)點(diǎn)*3*4+5*7*9+8構(gòu)建右節(jié)點(diǎn)43*4+5*7*9+8構(gòu)建根節(jié)點(diǎn)+，原樹作為左子樹+3*45*7*9+8構(gòu)建右節(jié)點(diǎn)5+3*4599*7*9+8下移到右節(jié)點(diǎn)，構(gòu)建根節(jié)點(diǎn)*，原來的右節(jié)點(diǎn)作為它的左節(jié)點(diǎn)+3*45+3*45*7*9+8構(gòu)建右節(jié)點(diǎn)7+3*45*7*9+8創(chuàng)建根*，原樹作為左子樹+3*45*7*100+8上移到根。創(chuàng)建根+，原樹作為左子樹88作為左節(jié)點(diǎn)9+89作為右子樹8++3*45*7*9+3*45*7*9++3*45*7*9101構(gòu)建過程總結(jié)順序掃描中綴表達(dá)式當(dāng)掃描到的是運(yùn)算數(shù)：先檢查當(dāng)前的表達(dá)式樹是否存在。如果不存在，則表示掃描到的是第一個運(yùn)算數(shù)，將它作為樹根。如果樹存在，則將此運(yùn)算數(shù)作為前一運(yùn)算符的右孩子。如果掃描到的是+或-：將它作為根結(jié)點(diǎn)，原來的樹作為它的左子樹。如果掃描到的是*或/：則與根結(jié)點(diǎn)比較。如果根結(jié)點(diǎn)也是*或/，則根結(jié)點(diǎn)應(yīng)該先執(zhí)行，于是將當(dāng)前運(yùn)算符作為根結(jié)點(diǎn)，原來的樹作為左子樹。如果根結(jié)點(diǎn)是+或-，則當(dāng)前運(yùn)算符應(yīng)該先運(yùn)算，于是將它作為右子樹的根，原來的右子樹作為它的左子樹。在遇到運(yùn)算數(shù)時，如何知道它前面的運(yùn)算符是誰？這只需要判別根結(jié)點(diǎn)有沒有右孩子。如果沒有右孩子，則運(yùn)算數(shù)是根結(jié)點(diǎn)的右運(yùn)算數(shù)，否則就是根結(jié)點(diǎn)右孩子的右運(yùn)算數(shù)。102構(gòu)建過程（括號的處理）(4+5)*(8+9)+10遇到括號，將括號內(nèi)的子表達(dá)式構(gòu)建一棵子樹作為整個表達(dá)式的一個運(yùn)算數(shù)4+5*(8+9)+10*作為根節(jié)點(diǎn)，括號內(nèi)的子樹作為左子樹4+5*(8+9)+10括號內(nèi)的子表達(dá)式構(gòu)建一棵子樹作為整棵樹的右子樹4+5*8+9+10+作為根節(jié)點(diǎn)，原樹作為左子樹，10作為右子樹4+5*8+9+10103表達(dá)式樹類的設(shè)計(jì)數(shù)據(jù)成員：指向樹根節(jié)點(diǎn)的指針公有成員函數(shù)：構(gòu)造函數(shù)：調(diào)用create從表達(dá)式構(gòu)建一棵樹result：計(jì)算表達(dá)式的結(jié)果，用后序遍歷過程私有成員函數(shù)：Create帶有遞歸參數(shù)的result函數(shù)getToken：create函數(shù)所用的子函數(shù)，用于從表達(dá)式中獲取一個語法單位104結(jié)點(diǎn)的設(shè)計(jì)在表達(dá)式樹中，每個葉子結(jié)點(diǎn)保存的是一個運(yùn)算數(shù)，每個非葉結(jié)點(diǎn)保存的是一個運(yùn)算符。結(jié)點(diǎn)的數(shù)據(jù)部分應(yīng)該包括兩個部分：結(jié)點(diǎn)的類型和值。105calc類的定義

classcalc{enumType{DATA,ADD,SUB,MULTI,DIV,OPAREN,CPAREN,EOL};structnode{Typetype; intdata; node*lchild,*rchild;

node(Typet,intd=0,node*lc=NULL,node*rc=NULL)

{type=t;data=d;lchild=lc;rchild=rc;} }; node*root; 106public: calc(char*s){root=create(s);} intresult(){if(root==NULL)return0; returnresult(root);}private：

node*create(char*&s);TypegetToken(char*&s,int&value); intresult(node*t); };

107私有create函數(shù)的實(shí)現(xiàn)calc::node*calc::create(char*&s){calc::node*p,*root=NULL;TypereturnType;intvalue;while(*s){returnType=calc::getToken(s,value);switch(returnType) {caseDATA:caseOPAREN: if(returnType==DATA)p=newcalc::node(DATA,value); elsep=create(s); if(root==NULL)root=p; elseif(root->rchild==NULL)root->rchild=p; elseroot->rchild->rchild=p; break;108 caseCPAREN:caseEOL:returnroot; caseADD:caseSUB: root=newcalc::node(returnType,0,root);break; caseMULTI:caseDIV: if(root->type==DATA||root->type==MULTI||root->type==DIV)root=newcalc::node(returnType,0,root); elseroot->rchild=newcalc::node(returnType,0,root->rchild); }}returnroot;}109getTokencalc::Typecalc::getToken(char*&s,int&data){chartype;while(*s=='')++s;if(*s>='0'&&*s<='9'){data=0;while(*s>='0'&&*s<='9'){data=data*10+*s-'0';++s;} returnDATA;}110if(*s=='\0')returnEOL;type=*s;++s;switch(type){case'+':returnADD; case'-':returnSUB; case'*':returnMULTI; case'/':returnDIV; case'(':returnOPAREN; case')':returnCPAREN; default:returnEOL; }}

111私有的result函數(shù)的實(shí)現(xiàn)intcalc::result(calc::node*t){intnum1,num2;if(t->type==DATA)returnt->data;num1=result(t->lchild);num2=result(t->rchild);switch(t->type){caseADD:t->data=num1+num2;break; caseSUB:t->data=num1-num2;break; caseMULTI:t->data=num1*num2;break; caseDIV:t->data=num1/num2;

}returnt->data;}112Calc類的應(yīng)用intmain(){calcexp("2*3+(1*2*3+6*6)*(2+3)/5+2/2");cout<<exp.result()<<endl;return0;}

113Calc類的特點(diǎn)使用時和基于棧實(shí)現(xiàn)的calc類完全一樣缺點(diǎn)沒有考慮表達(dá)式不正確的情況沒有考慮乘方運(yùn)算114第五章樹樹的概念二叉樹表達(dá)式樹哈夫曼樹與哈夫曼編碼樹和森林115字符的機(jī)內(nèi)表示在計(jì)算機(jī)中每個字符是用一個編碼表示大多數(shù)編碼系統(tǒng)都采用等長編碼，如ASCII編碼例如在某段文本中用到了下列字符，括號中是它們出現(xiàn)的頻率：a(10),e(15),i(12),s(3),t(4),空格(13),換行(1)。如采用定長編碼，7個不同的字符至少要用3位編碼。116字符編碼出現(xiàn)頻率占用空間（bit）a0001030e0011545i0101236s01139t100412空格1011339換行11013總存儲量：3*（10+15+12+3+4+13+1）=3*58=174bit117這個編碼可以對應(yīng)成如下的完全二叉樹，左枝為0，右枝為1aSeit43121510113空格換行118aSeit43121510113空格換行很顯然，將換行上移一層可以減少存儲量不等長編碼可以減少存儲量！??！119前綴編碼字符只放在葉結(jié)點(diǎn)中

字符編碼可以有不同的長度由于字符只放在葉結(jié)點(diǎn)中，所以每個字符的編碼都不可能是其他字符編碼的前綴前綴編碼可被惟一解碼120哈夫曼樹哈夫曼樹是一棵最小代價的二叉樹，在這棵樹上，所有的字符都包含在葉結(jié)點(diǎn)上。要使得整棵樹的代價最小，顯然權(quán)值大的葉子應(yīng)當(dāng)盡量靠近樹根，權(quán)值小的葉子可以適當(dāng)離樹根遠(yuǎn)一些。121snltaeispA001E01I10S00000T0001Sp11nl00001總共用了146bit哈夫曼編碼122哈夫曼算法1、給定一個具有n個權(quán)值{w1,w2,………wn}的結(jié)點(diǎn)的集合

F={T1,T2,………Tn}2、

初始時，設(shè)集合

A=F。3、

執(zhí)行

i=1至

n-1的循環(huán)，在每次循環(huán)時執(zhí)行以下操作從當(dāng)前集合中選取權(quán)值最小、次最小的兩個結(jié)點(diǎn)，以這兩個結(jié)點(diǎn)作為內(nèi)部結(jié)點(diǎn)

bi

的左右兒子，bi的權(quán)值為其左右兒子權(quán)值之和。在集合中去除這兩個權(quán)值最小、次最小的結(jié)點(diǎn)，并將內(nèi)部結(jié)點(diǎn)bI加入其中。這樣，在集合A中，結(jié)點(diǎn)個數(shù)便減少了一個。這樣，在經(jīng)過了n-1次循環(huán)之后，集合A中只剩下了一個結(jié)點(diǎn)，這個結(jié)點(diǎn)就是根結(jié)點(diǎn)。

123a(10),e(15),i(12),s(3),t(4),空格(13),換行(1)。t4S3i12e15a1013空格1換行t4S3i12e15a1013空格1換行4t4S3i12e15a1013空格1換行48124i12e15a1013空格18i12e1513空格25t4S31換行48a1018t4S31換行48125i1213空格25e1533a1018t4S31換行48i1213空格2558e1533a1018t4S31換行48126哈夫曼編碼的生成每個字符的編碼是根節(jié)點(diǎn)到該字符的路徑左枝為0，右枝為1127哈夫曼樹類的實(shí)現(xiàn)為了便于找出一組符號的哈夫曼編碼，我們可以定義一個哈夫曼樹類。哈夫曼樹類的對象可以接受一組符號以及對應(yīng)的權(quán)值，并告知每個符號對應(yīng)的哈夫曼編碼。因此，哈夫曼樹類應(yīng)該有兩個公有的成員函數(shù)：構(gòu)造函數(shù)：接受一組待編碼的符號以及它們的權(quán)值，構(gòu)造一棵哈夫曼樹。GetCode函數(shù)根據(jù)保存的哈夫曼樹為每個葉結(jié)點(diǎn)生成哈夫曼編碼。128哈夫曼樹的存儲在哈夫曼樹中，每個要編碼的元素是一個葉結(jié)點(diǎn)，其它結(jié)點(diǎn)都是度數(shù)為2的節(jié)點(diǎn)一旦給定了要編碼的元素個數(shù)，由n0＝n2＋1可知哈夫曼樹的大小為2n-1哈夫曼樹可以用一個大小為2n的數(shù)組來存儲。0節(jié)點(diǎn)不用，根存放在節(jié)點(diǎn)1。葉結(jié)點(diǎn)依次放在n+1到2n的位置每個數(shù)組元素保存的信息：結(jié)點(diǎn)的數(shù)據(jù)、權(quán)值和父結(jié)點(diǎn)和左右孩子的位置129值aeistspnl權(quán)583325188410151234131父112454236536左2495610右381271113012345678910111213i1213空格2558e1533a1018t4S31換行48130131211109876543210131171283右1065942左635632454211父113431215104818253358權(quán)nlsptsiea值生成過程131編碼的產(chǎn)生值aeistspnl權(quán)583325188410151234131父112454236536左2495610右381271113012345678910111213生成a的代碼：結(jié)點(diǎn)4的右孩子（1），結(jié)點(diǎn)4是結(jié)點(diǎn)2的左孩子（01），結(jié)點(diǎn)2是結(jié)點(diǎn)1的左孩子（001）對每個結(jié)點(diǎn)，從葉子往根推進(jìn)，是左枝加0，是右枝加1132哈夫曼樹類存儲設(shè)計(jì)結(jié)點(diǎn)的表示：結(jié)點(diǎn)的數(shù)據(jù)、權(quán)值和父結(jié)點(diǎn)和左右孩子的位置哈夫曼樹的存儲：一個結(jié)點(diǎn)數(shù)組以及一個整型數(shù)據(jù)成員，保存數(shù)組的大小。操作構(gòu)建一棵哈夫曼樹：構(gòu)造函數(shù)實(shí)現(xiàn)。給出節(jié)點(diǎn)數(shù)據(jù)數(shù)組，權(quán)值數(shù)組和數(shù)據(jù)個數(shù)獲取樹上節(jié)點(diǎn)的哈夫曼編碼返回一個數(shù)組，數(shù)組的元素由數(shù)據(jù)和編碼兩部分組成的133template<classType>classhfTree{private:structNode {Typedata;//結(jié)點(diǎn)值

intweight;//結(jié)點(diǎn)的權(quán)值

intparent,left,right; };Node*elem;intlength;134 public: structhfCode{ Typedata; stringcode; }; hfTree(constType*x,constint*w,intsize); voidgetCode(hfCoderesult[]); ~hfTree(){delete[]elem;}};

135構(gòu)造函數(shù)template<classType>hfTree<Type>::hfTree(constType*v,constint*w,intsize) {constintMAX_INT=32767;intmin1,min2;//最小樹、次最小樹的權(quán)值

intx,y;//最小樹、次最小樹的下標(biāo)

//置初值

length=2*size;elem=newNode[length];for(inti=size;i<length;++i){elem[i].weight=w[i-size];

elem[i].data=v[i-size];

elem[i].parent=elem[i].left=elem[i].right=0;}136//構(gòu)造新的二叉樹

for(i=size-1;i>0;--i){min1=min2=MAX_INT;x=y=0;for(intj=i+1;j<length;++j)

if(elem[j].parent==0) if(elem[j].weight<min1)

{min2=min1;min1=elem[j].weight;x=y;y=j;}

elseif(elem[j].weight<min2){min2=elem[j].weight;x=j;}

elem[i].weight=min1+min2;

elem[i].left=x;elem[i].right=y;elem[i].parent=0;elem[x].parent=i;elem[y].parent=i;

}}

137getCode的偽代碼getCode(hfCode<Type>result[]){for(inti=size;i<length;++i){result[i-size].data=elem[i].data;result[i-size].code="";p=elem[i].parent;s=i; while(p不等于0){ if(p的左孩子是==s)result[i-size].code前添加‘0’; elseresult[i-size].code前添‘1’;

移到上一層；

}}}138getCode代碼template<classType>voidhfTree<Type>::getCode(hfCoderesult[]){intsize=length/2;intp,s;//s是追溯過程中正在處理的結(jié)點(diǎn)，p是s的父結(jié)點(diǎn)下標(biāo)

for(inti=size;i<length;++i){result[i-size].data=elem[i].data;result[i-size].code="";p=elem[i].parent;s=i; while(p){ if(elem[p].left==s)result[i-size].code='0'+result[i-size].code; elseresult[i-size].code='1'+result[i-size].code; s=p;p=elem[p].parent; }}}

139哈夫曼類的使用為下列符號集生成哈夫曼編碼：a(10),e(15),i(12),s(3),t(4),d(13),n(1)140intmain(){charch[]={"aeistdn"};intw[]={10,15,12,3,4,13,1};hfTree<char>tree(ch,w,7);hfTree<char>::hfCoderesult[7];tree.getCode(result);