《數(shù)據(jù)結(jié)構(gòu)JAVA語言版》課件 孫愛香 第6、7章 樹和二叉樹、圖

從對線性結(jié)構(gòu)的研究過渡到對樹形結(jié)構(gòu)的研究，是數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)的一次躍變。

6.1樹的定義和基本術(shù)語6.1.1樹的定義

（非遞歸）

樹是由n(n

0)個結(jié)點組成的有限集合。如果n=0，稱為空樹；如果n>0，則:

有一個特定的稱之為根(root)的結(jié)點，它只有后繼，但沒有前驅(qū)；

其余結(jié)點有且僅有一個直接前驅(qū)，但可以有0個或多個后繼。是不是一棵樹？6.1.2樹的基本術(shù)語結(jié)點：數(shù)據(jù)元素及其分支

結(jié)點的子樹結(jié)點的度:結(jié)點射出的分支數(shù)。樹的度：樹內(nèi)各結(jié)點度的最大值。葉子結(jié)點（終端）:度為0的結(jié)點。非終端結(jié)點:度不為0的結(jié)點。結(jié)點的層次:樹中根結(jié)點的層次為1，下一層結(jié)點的層次是2，以此類推。樹的深度:樹中所有結(jié)點層次的最大值。父結(jié)點：結(jié)點的前驅(qū)稱為該結(jié)點的父親。孩子結(jié)點：結(jié)點的后繼稱為該結(jié)點的孩子。兄弟：同一個父親的孩子之間互稱兄弟。堂兄弟：兄弟的孩子之間互稱堂兄弟。有序樹、無序樹:如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱為有序樹，否則稱為無序樹。填空：對于一棵具有n個結(jié)點的樹，該樹中所有結(jié)點的度數(shù)之和為？答：結(jié)點的度數(shù)之和應(yīng)為所有分支數(shù)之和，除了根結(jié)點之外，所有結(jié)點都有一個分支射入，因此樹中所有結(jié)點度數(shù)之和是ｎ－１6.1.3樹的表示形式（1）倒懸樹。是最常用的表示形式，如圖所示。

ABDCEGFHIMJKL（b）一般的樹6.1.3樹的表示形式（2）嵌套集合。是一些集合的集體，對于任何兩個集合，或者不相交，或者一個集合包含另一個集合。圖6-2（a）是圖6-1（b）樹的嵌套集合形式。（3）廣義表形式。圖6-2（b）是樹的廣義表形式。（4）凹入法表示形式。圖6-2（c）是樹的凹入法表示形式。樹的表示方法的多樣化正說明了樹結(jié)構(gòu)在日常生活中及計算機程序設(shè)計中的重要性。

圖

樹的其他三種表示法6.1.4抽象數(shù)據(jù)類型樹的定義

ADTTREE{

數(shù)據(jù)對象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關(guān)系：R

基本操作：}

ADTTREE

n個數(shù)據(jù)元素的集合。數(shù)據(jù)元素可以是整型、字符型、結(jié)構(gòu)類型。想利用數(shù)學(xué)的語言正確地描述出前驅(qū)和后繼結(jié)點的一對多的關(guān)系不太容易;不再要求,感興趣的同學(xué)自己看教材。關(guān)于基本操作的幾點說明：1、基本操作是定義于邏輯結(jié)構(gòu)上的基本操作，向外界提供一個與其通訊的接口。還沒有用具體的某種程序語言寫出具體的算法，而算法的實現(xiàn)只有在存儲結(jié)構(gòu)確立之后。對應(yīng)于不同的存儲結(jié)構(gòu)，樹的基本操作的實現(xiàn)也不相同。2、基本操作的種類可隨實際需要的不同而不同，定義多少種基本操作由自己確定。3、針對不同的需要，基本操作的參數(shù)和返回值可以有所變化。樹的基本操作：（1）Root()：求樹的根結(jié)點。（2）Parent(t)：求結(jié)點t的雙親結(jié)點。（3）Child(t,i)：求結(jié)點t的第i個子結(jié)點。（4）RightSibling(t)：求結(jié)點t第一個右邊兄弟結(jié)點。（5）Insert(s,t,i)：把樹s插入到樹中作為結(jié)點t的第i棵子樹。（6）Delete(t,i)：刪除結(jié)點t的第i棵子樹。（7）Traverse(TraverseType)：按某種方式遍歷樹。（8）Clear()：清空樹。（9）IsEmpty：判斷樹是否為空樹。（10）GetDepth()：求樹的深度。6.2二叉樹(BinaryTree)6.2.1二叉樹的定義1、特點：（1）每個結(jié)點至多有兩棵子樹。（即二叉樹中不存在度大于2的結(jié)點）（2）二叉樹的子樹有左右之分，其次序不能任意顛倒。654321判斷題：二叉樹是度為2的有序樹.（）錯，不一定結(jié)點的度:結(jié)點的分支數(shù)樹的度:樹中結(jié)點度的最大值所以該樹的度為1.2、二叉樹的五種不同形態(tài)（a）空二叉樹（b）僅有根結(jié)點的二叉樹（c）右子樹為空的二叉樹（d）左子樹為空的二叉樹（e）左右子樹均非空的二叉樹3、抽象數(shù)據(jù)類型二叉樹的定義

ADT

BINARYTREE{

數(shù)據(jù)對象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關(guān)系：R

基本操作：}

ADTBINARYTREE

n個數(shù)據(jù)元素的集合。數(shù)據(jù)元素可以是整型、字符型、結(jié)構(gòu)類型。想利用數(shù)學(xué)的語言正確地描述出二叉樹中結(jié)點元素之間的關(guān)系不太容易。所以不再要求。關(guān)于基本操作的幾點說明：（1）基本操作是定義于邏輯結(jié)構(gòu)上的基本操作，向外界提供一個與其通訊的接口。還沒有用具體的某種程序語言寫出具體的算法，而算法的實現(xiàn)只有在存儲結(jié)構(gòu)確立之后。對應(yīng)于不同的存儲結(jié)構(gòu)，樹的基本操作的實現(xiàn)也不相同。

（2）基本操作的種類可隨實際需要的不同而不同，定義多少種基本操作由自己確定。（3）針對不同的需要，基本操作的參數(shù)和返回值可以有所變化。二叉樹的基本操作：（1）publicbool

IsEmpty()//判斷是否是空二叉樹（2）publicNode<T>GetRoot()//獲取根結(jié)點

（3）publicNode<T>Getleftchild(Node<T>p)//獲取結(jié)點的左孩子結(jié)點

（4）publicNode<T>Getrightchild(Node<T>p)//獲取結(jié)點的右孩子結(jié)點

（5）publicvoidInsertL(T

val,Node<T>p)

//將結(jié)點p的左子樹插入值為val的新結(jié)點，原來的左子樹成為新結(jié)點的左子樹（6）publicvoidInsertR(T

val,Node<T>p)

//將結(jié)點p的右子樹插入值為val的新結(jié)點，原來的右子樹成為新結(jié)點的右子樹

（7）publicNode<T>DeleteL(Node<T>p)

//若p非空，刪除p的左子樹

（8）publicNode<T>DeleteR(Node<T>p)

//若p非空，刪除p的右子樹

（9）publicbool

IsLeaf(Node<T>p)

//判斷是否是葉子結(jié)點（10）publicvoidPreOrder(Node<T>root)//二叉樹的前序遍歷（11）publicvoidInOrder(Node<T>root)//二叉樹的中序遍歷（12）publicvoidPostOrder(Node<T>root)//二叉樹的后序遍歷（13）publicvoidLevelOrder(Node<T>root)//二叉樹的層次遍歷性質(zhì)1

若二叉樹的層次從1開始,則在二叉樹的第i層最多有2i-1個結(jié)點。(i

1)證明：數(shù)學(xué)歸納法。當(dāng)i=1時，2i-1

=1;二叉樹的第1層上只有一個根結(jié)點。第一層的結(jié)點數(shù)1<=2i-1，所以命題成立。假設(shè)i=k時命題成立，即第k層上結(jié)點數(shù)目最多為2k-1

當(dāng)i=k+1時，第k+1層上結(jié)點數(shù)目最多為第k層上的兩倍，即2*2k-1

=2k+1-1；命題也成立。綜上所述：命題成立。

6.2.2二叉樹的性質(zhì)選擇題:在二叉樹的第三層上最多有幾個結(jié)點（）。A.3B.4C.5D.6性質(zhì)2

深度為k的二叉樹最多有2k-1個結(jié)點。(k

1)

利用性質(zhì)1的結(jié)論每一層上具有的最大結(jié)點數(shù)如下表所示：

第i層k……321每層結(jié)點數(shù)

2k-1……222120二叉樹所具有的最大結(jié)點數(shù):選擇題：二叉樹的深度為4，則二叉樹最多有（）個結(jié)點。A．13B．14C．15D．16

性質(zhì)3

對任何一棵二叉樹,如果其葉結(jié)點個數(shù)為n0,度為2的結(jié)點個數(shù)為n2,則有n0＝n2＋1。

證明:設(shè)度為1的結(jié)點有n1個，總結(jié)點個數(shù)為n，分支數(shù)為e

因為二叉樹中所有結(jié)點的度都小于等于2，所以有下式成立：

n=n0+n1+n2

（總結(jié)點數(shù)=度為0的結(jié)點數(shù)+度為1的結(jié)點數(shù)+度為2的結(jié)點數(shù)）

除了根結(jié)點外，其余結(jié)點都有一個分支進入，所以有下式成立：

n=e+1(總結(jié)點數(shù)=總分支數(shù)+1)鏈接又因為這些分支都是由度為1或度為2的結(jié)點射出的，所以有下式成立：

e=2n2+n1鏈接

綜合上面三式：

n0+n1+n2=2n2+n1+1即n0=n2+1

選擇題假定一棵二叉樹中，度為２的結(jié)點數(shù)為15，度為１的結(jié)點數(shù)為30，則葉子結(jié)點數(shù)為（）。A．15B．16C．17D．47定義1

滿二叉樹(FullBinaryTree)

一棵深度為k且有2k-1個結(jié)點的二叉樹稱為滿二叉樹。下面兩棵樹是否是滿二叉樹？為了引出完全二叉樹的定義，需要對滿二叉樹的結(jié)點按照從上至下，從左往右的順序進行編號。定義2

完全二叉樹(CompleteBinaryTree)

深度為k，有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時，稱之為完全二叉樹。

如何判斷一棵二叉樹是否是完全二叉樹？

1）對二叉樹從上到下、自左至右進行編號。

2）對比二叉樹結(jié)點與相同編號的滿二叉樹結(jié)點位置是否一一對應(yīng)；若一一對應(yīng)，則是完全二叉樹；如不一一對應(yīng)，則不是完全二叉樹。

判斷下列二叉樹abc是否是完全二叉樹(二叉樹結(jié)點已編號)滿二叉樹二叉樹a二叉樹b二叉樹c定義2

完全二叉樹(CompleteBinaryTree)若設(shè)二叉樹的深度為h，則共有h層。除第h層外，其它各層(1

h-1)的結(jié)點數(shù)都必須達(dá)到最大個數(shù)，第h層可以從右向左連續(xù)缺若干結(jié)點。

判斷二叉樹是否是完全二叉樹，可根據(jù)此定義判斷.

二叉樹a二叉樹b二叉樹c完全二叉樹的特點是：1）只允許最后一層有空缺結(jié)點且空缺在右邊，即葉子結(jié)點只能在層次最大的兩層上出現(xiàn)；2）對任一結(jié)點，如果其右子樹的深度為j，則其左子樹的深度必為j或j+1。性質(zhì)4

具有n個結(jié)點的完全二叉樹的深度為

log2n

+1證明：設(shè)完全二叉樹的深度為k，則前k-1層的結(jié)點數(shù)

第i層K-1……321每層結(jié)點數(shù)

2k-2……222120

k-1層的結(jié)點總數(shù)為2k-1-1，第k層最少有1個結(jié)點，最多有2k-1個結(jié)點，所以結(jié)點數(shù)n滿足：2k-1

n<=2k-1,由此式可推出下式一定成立：2k-1

n<2k

取對數(shù)k-1log2n<k

即log2n

<k

log2n+1

因為k為整數(shù)，所以k=

log2n

+1選擇題一棵完全二叉樹有18個結(jié)點，則完全二叉樹的深度為A．3B．4C．5D．6一棵具有n個結(jié)點的完全二叉樹的樹高度（深度）是（）

【南京理工大學(xué)1996一、8（2分）】A．

log2n+1B．Log2n+1C．log2n

D．Log2n-1一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（）

【西安交通大學(xué)1996三、2(3分)】A．250B．501C．254D．505

解：在完全二叉樹中，度為1的結(jié)點數(shù)n1或為0或為1。

由性質(zhì)3可知n0=n2+1即n2=n0-1

又因為n=n0+n1+n2

所以n=2n0+n1-1

將n=1001代入得：2n0+n1=1002

又因為n0必須為整數(shù)，所以n1的值必為0。

所以n0=501

性質(zhì)5

如果將一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序(自頂向下，同一層自左向右）連續(xù)編號1,2,…,n，對結(jié)點i(1

i

n)有以下關(guān)系：

若i==1,則i是二叉樹的根，無雙親若i>1,則i的雙親為

i/2

若2*i≤n,則i的左孩子為2*i，否則無左孩子若2*i+1≤n,則i的右孩子為2*i+1，否則無右孩子6.2.3二叉樹的存儲結(jié)構(gòu)1.順序存儲結(jié)構(gòu)（數(shù)組表示）

完全二叉樹的順序存儲：c語言中認(rèn)為：將完全二叉樹中的結(jié)點按照從上至下、自左往右的順序存儲到一維數(shù)組中。

普通二叉樹的順序存儲：也是將普通二叉樹中的結(jié)點按照從上至下、自左往右的順序存儲到一維數(shù)組中。（中間的空缺結(jié)點也留出相應(yīng)的位置）3105172312013245617051223316543210acb0132456

圖示二叉樹盡管只有三個結(jié)點，也要存儲到一個長度為7的數(shù)組中，浪費存儲空間。6543210cba練習(xí)：畫出下圖所示二叉樹的順序存儲結(jié)構(gòu)acb如果存儲結(jié)點數(shù)為30的單支樹，需要一個多大的一維數(shù)組？（同學(xué)們自算）acbG…答：利用性質(zhì)2，補齊空缺結(jié)點后，算出共有230-1個結(jié)點。存儲一個30個結(jié)點的單支樹，要用長度為230-1的數(shù)組（1G），微型機根本不支持。存儲空間的浪費異常明顯。

怎樣來解決這個問題？

不給空缺的結(jié)點留位置。按照從上到下，從左到右的順序?qū)⒍鏄涞慕Y(jié)點存儲到一維數(shù)組中。（30個結(jié)點的單支樹只需存儲到一個長度為30的數(shù)組中）避免了存儲空間的浪費，但這樣做行不行呢？答：不行。兩棵不同的二叉樹對應(yīng)的存儲結(jié)構(gòu)是完全相同的。計算機要嚴(yán)格避免二義性。不同的二叉樹必須對應(yīng)不同的存儲結(jié)構(gòu)。如果兩棵不同的二叉樹對應(yīng)的存儲結(jié)構(gòu)是完全相同的，計算機在看到這樣的一個數(shù)組的時候就不知道它表示的是那棵二叉樹了。2.二叉樹的鏈?zhǔn)酱鎯Γ?）二叉鏈表結(jié)點結(jié)構(gòu)：包含兩個指針域和一個數(shù)據(jù)域：指針域存儲指向左右孩子的指針，數(shù)據(jù)域存儲結(jié)點本身的信息。

結(jié)點的JAVA語言描述：class

Node<T>{

Tdata;

Node<T>

leftchild,

rightchild;};二叉樹a的鏈?zhǔn)酱鎯Y(jié)構(gòu)如下圖所示：因每個結(jié)點中包含兩個指針，所以這種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)又被稱為二叉鏈表。課堂練習(xí)：請畫出下面二叉樹的二叉鏈表結(jié)構(gòu)。acbcban個結(jié)點的二叉鏈表共有n+1個空指針域，為什麼？答：在含有n個結(jié)點的二叉鏈表中，共有2n個指針域，但實際有效的指針數(shù)等于二叉樹中的分支數(shù)（即n-1），所以共存在n+1個空的指針域。選擇題10個結(jié)點的二叉鏈表中共有（）個空的指針域。A.9B.10C.11D.12（2）三叉鏈表結(jié)點結(jié)構(gòu)：包含三個指針域和一個數(shù)據(jù)域：指針域存儲指向左右孩子的指針以及指向父親的指針，數(shù)據(jù)域存儲結(jié)點本身的信息。結(jié)點的JAVA語言表示：class

Node<T>{Tdata;

Node<T>leftchild,rightchild;Node<T>parent;};二叉樹a的三叉鏈表結(jié)構(gòu)如下圖所示：3、二叉鏈表存儲結(jié)構(gòu)下基本操作的實現(xiàn)1）結(jié)點類的實現(xiàn)二叉樹的二叉鏈表的結(jié)點類有3個成員字段：數(shù)據(jù)域字段data；左孩子引用域字段leftchild；右孩子引用域字段rightchild。

packagedspakage3;importdspackage1.CSeqQueue;classNode<T>{

publicTdata;//數(shù)據(jù)域

publicNode<T>leftchild;//左孩子

publicNode<T>rightchild;//右孩子

//三個參數(shù)構(gòu)造器

publicNode(Tval,Node<T>lp,Node<T>rp)

{

data=val;

leftchild=lp;

rightchild=rp;}

//兩個參數(shù)構(gòu)造器

public

Node(Node<T>lp,Node<T>rp){

leftchild=lp;

rightchild=rp;}

//一個參數(shù)構(gòu)造器

public

Node(T

val){

data=val;

leftchild=null;

rightchild=null;}

//無參構(gòu)造器

publicNode(){

leftchild=null;

rightchild=null;}}

2)二叉鏈表類

只要知道了根結(jié)點的地址，就可以確定整棵樹，所以用一個根結(jié)點引用root就可以確定整棵樹。所以二叉鏈表的類BiTree<T>只有一個成員字段root表示根結(jié)點引用。public

class

BiTree<T>{

publicNode<T>root;//根結(jié)點引用

//無參構(gòu)造器

public

BiTree(){

root=null;}

//一個參數(shù)構(gòu)造器

public

BiTree(T

val)

{Node<T>p=newNode<T>(val);

root=p;}

//三個參數(shù)構(gòu)造器

publicBiTree(Tval,Node<T>lp,Node<T>rp){Node<T>p=newNode<T>(val,lp,rp);

root=p;}

//判斷是否是空二叉樹

public

booleanIsEmpty(){

if(root==null){

return

true;}

else{

return

false;}}

//獲取根結(jié)點

publicNode<T>Getroot(){

return

root;

}

//獲取結(jié)點的左孩子結(jié)點

publicNode<T>Getleftchild(Node<T>p){

return

p.leftchild;}

//獲取結(jié)點的右孩子結(jié)點

publicNode<T>Getrightchild(Node<T>p){

return

p.rightchild;}

//將結(jié)點p的左子樹插入值為val的新結(jié)點，

//原來的左子樹成為新結(jié)點的左子樹

public

voidInsertL(Tval,Node<T>p)

//將結(jié)點p的左子樹插入值為val的新結(jié)點，

//原來的左子樹成為新結(jié)點的左子樹

public

voidInsertL(Tval,Node<T>p){Node<T>tmp=newNode<T>(val);

//建立值為val的新結(jié)點

tmp.leftchild=p.leftchild;

//原來的左子樹成為新結(jié)點的左子樹

p.leftchild=tmp;

//新結(jié)點成為結(jié)點p的左孩子

}

//將結(jié)點p的右子樹插入值為val的新結(jié)點，

//原來的右子樹成為新結(jié)點的右子樹

public

voidInsertR(Tval,Node<T>p)

//將結(jié)點p的右子樹插入值為val的新結(jié)點，

//原來的右子樹成為新結(jié)點的右子樹

public

voidInsertR(Tval,Node<T>p){Node<T>tmp=newNode<T>(val);

//建立值為val的新結(jié)點

tmp.rightchild=p.rightchild;

//原來的右子樹成為新結(jié)點的右子樹

p.rightchild=tmp;

//新結(jié)點成為結(jié)點p的右孩子

}

//若p非空，刪除p的左子樹

publicNode<T>DeleteL(Node<T>p){

if((p==null)||(p.leftchild==null)){//p為空或p無左子樹

return

null;//返回空引用

}Node<T>tmp=p.leftchild;

//令新的引用tmp指向左子樹

p.leftchild=null;//令左子樹為空，即刪除

return

tmp;//返回原來左子樹

}

//若p非空，刪除p的右子樹

publicNode<T>DeleteR(Node<T>p){

if((p==null)||(p.rightchild==null)){//p為空或p無右子樹

return

null;//返回空引用

}Node<T>tmp=p.rightchild;

//令新的引用tmp指向右子樹

p.rightchild=null;//令右子樹為空，即刪除

return

tmp;//返回原來右子樹

}

//判斷是否是葉子結(jié)點

public

boolean

IsLeaf(Node<T>p){

if

((p!=null)&&(p.leftchild==null)&&(p.rightchild==null)){//p不為空，且無左孩子和右孩子

return

true;}

else{

return

false;}}

6.3遍歷二叉樹和線索鏈表(TraversingBinaryTree)

所謂樹的遍歷，就是按某種次序訪問樹中的結(jié)點，要求每個結(jié)點訪問一次且僅訪問一次。

遍歷的結(jié)果：產(chǎn)生一個關(guān)于結(jié)點的線性序列。

設(shè)訪問根結(jié)點記作D

遍歷根的左子樹記作L

遍歷根的右子樹記作R

則可能的遍歷次序有

先序DLRDRL逆先序中序LDRRDL逆中序后序LRDRLD

逆后序6.3.1遍歷二叉樹先序遍歷(PreorderTraversal)先序遍歷二叉樹算法的框架是若二叉樹為空，則空操作；否則訪問根結(jié)點(D)；先序遍歷左子樹(L)；先序遍歷右子樹(R)。cab*-表達(dá)式語法樹遍歷結(jié)果（前綴表達(dá)式）

-*a

b

cpublic

void

PreOrder(Node<T>root){

//根結(jié)點為空

if(root==null){

return;}

//處理根結(jié)點

System.out.println(root.data);

//先序遍歷左子樹

PreOrder(root.leftchild);

//先序遍歷右子樹

PreOrder(root.rightchild);}中序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則中序遍歷左子樹(L)；訪問根結(jié)點(D)；中序遍歷右子樹(R)。遍歷結(jié)果（中綴表達(dá)式）

a*b-

c中序遍歷(InorderTraversal)表達(dá)式語法樹cab*-

中序遍歷二叉樹的遞歸算法

public

void

InOrder(Node<T>root){

//根結(jié)點為空

if(root==null){

return;}

//中序遍歷左子樹

InOrder(root.leftchild);

//處理根結(jié)點

System.out.println(root.data);

//中序遍歷右子樹

InOrder(root.rightchild);}后序遍歷(PostorderTraversal)后序遍歷二叉樹算法的框架是若二叉樹為空，則空操作；否則后序遍歷左子樹(L)；后序遍歷右子樹(R)；訪問根結(jié)點(D)。遍歷結(jié)果（后綴表達(dá)式）

a

b*c-cab*-表達(dá)式語法樹后序遍歷二叉樹的遞歸算法

public

void

PostOrder(Node<T>root){

//根結(jié)點為空

if(root==null){

return;}

//后序遍歷左子樹

PostOrder(root.leftchild);

//后序遍歷右子樹

PostOrder(root.rightchild);

//處理根結(jié)點

System.out.println(root.data);}CDEBA上機作業(yè):二叉鏈表存儲結(jié)構(gòu)下,建立圖示二叉樹并對其進行中序遍歷.

源碼：CDEBApublic

static

void

main(String[]args){

BiTree<Character>evergreen=new

BiTree<Character>('A');evergreen.InsertL('B',evergreen.root);

evergreen.InsertR('C',evergreen.root);

evergreen.InsertL('E',evergreen.root.rightchild);

evergreen.InsertR('D',evergreen.root.leftchild);

evergreen.InOrder(evergreen.root);}6.3.2二叉線索鏈表

講完了二叉鏈表及該種存儲結(jié)構(gòu)下基本操作的實現(xiàn)以后,再講二叉鏈表基礎(chǔ)上的另一種存儲結(jié)構(gòu)-二叉線索鏈表.

畫出圖示樹的二叉鏈表，寫出圖示樹的中序遍歷結(jié)果。CDEBACABED圖示樹按照中序遍歷的結(jié)果是：BDAEC當(dāng)以二叉鏈表作存儲結(jié)構(gòu)時，只能找到結(jié)點的左右孩子信息，卻無法直接得到結(jié)點的前驅(qū)和后繼信息（按照中序遍歷次序確定的）。同時n個結(jié)點的二叉鏈表有n+1個空指針域。能否利用這些空的指針域存儲結(jié)點的前驅(qū)和后繼信息（中序）？當(dāng)然是可以的。利用空的左指針指向它的前驅(qū)，利用空的右指針指向它的后繼。我們稱這種存儲結(jié)構(gòu)為二叉線索鏈表。6.3.2二叉線索鏈表1、結(jié)點結(jié)構(gòu)lpointerltagdatartagrpointerltag=0表示左指針指向的是左孩子ltag=1表示左指針指向的是前驅(qū)。rtag=0表示右指針指向的是右孩子；rtag=1表示右指針指向的是后繼。用java語言描述一下結(jié)點class

BiThrNode<T>{Tdata;

BiThrNode<T>lpointer,rpointer;

int

ltag,rtag;};如果空的左指針指向的是中序遍歷下的前驅(qū)，空的右指針指向的是中序遍歷下的后繼，稱這種二叉線索鏈表為中序線索鏈表。如果空的左指針指向的是先序遍歷下的前驅(qū)，空的右指針指向的是先序遍歷下的后繼，稱這種二叉線索鏈表為先序線索鏈表。如果空的左指針指向的是后序遍歷下的前驅(qū)，空的右指針指向的是后序遍歷下的后繼，稱這種二叉線索鏈表為后序線索鏈表。畫出圖示樹的中序線索鏈表CDEBACABED1）畫出樹的二叉鏈表結(jié)構(gòu)2）添上標(biāo)志位有孩子填“0”沒孩子填“1”3根據(jù)中序遍歷的結(jié)果BDAEC把空的指針補上

為了處理的方便，一般情況下都給線索鏈表加上一個頭結(jié)點。令剩下的兩個空指針都指向頭結(jié)點。頭結(jié)點的左指針指向根結(jié)點，頭結(jié)點的右指針指向按中序遍歷的最后一個結(jié)點。頭結(jié)點的左標(biāo)志是0，右標(biāo)志是1。作業(yè)：畫出圖示樹的先序線索鏈表CDEBA先序線索鏈表、中序線索鏈表、后序線索鏈表存儲結(jié)構(gòu)下基本操作的實現(xiàn)，礙于時間關(guān)系，不再講。（但是研究生入學(xué)考試通常會在這兒出大題）山東大學(xué)２００５碩士研究生考試試題（１０分）寫一算法，完成對中序線索二叉樹的中序掃描。也就是怎樣根據(jù)中序線索鏈表得到二叉樹中序遍歷的線性序列。即中序線索鏈表存儲結(jié)構(gòu)下中序遍歷基本操作的實現(xiàn)。

6.4.1樹的存儲1.雙親表示法主要描述的是結(jié)點的雙親關(guān)系。指出結(jié)點的雙親是誰。把圖示樹的結(jié)點按照從上至下從左往右的順序存儲到一維數(shù)組中，同時附設(shè)一個指示器指示其雙親結(jié)點。ABFKHGEDCR6K6H6G3F1E1D0C0B0A-1R0213456789如何表示此數(shù)組？每一個元素都是兩項的組合，可以考慮用類表示。class

PTNode<T>{//元素類型

Tdata;

int

parent;

//雙親位置};

6K6H6G3F1E1D0C0B0A-1R0213456789此數(shù)組一共有10個元素

PTNode<Character>[]tree=(PTNode<Character>[])newObject[10];2.孩子表示法：

主要描述的是結(jié)點的孩子關(guān)系。指出結(jié)點的孩子有哪些。由于每個結(jié)點的孩子個數(shù)不一定相等，所以利用鏈?zhǔn)酱鎯Y(jié)構(gòu)更加適宜。

（把每個結(jié)點的孩子都用一條鏈把它們串起來，父親牽著孩子的手丟不了）

K

H

G

F

E

D

C

B

A

R1235987460123456789ABFKHGEDCR鏈表中結(jié)點：class

CTNode{

int

child;

CTNode

next;};數(shù)組中結(jié)點：class

CTBox<T>{Tdata;

CTNode

firstchild;

//孩子鏈表頭引用};整個數(shù)組：CTBox<Character>[]tree1=(CTBox<Character>[])newObject[10];

K

H

G

F

E

D

C

B

A

R1235987460123456789用JAVA語言描述一下此種結(jié)構(gòu)：3.孩子雙親表示法

指出結(jié)點的父親是誰，同時指出結(jié)點的孩子有哪些。ABFKHGEDCR6K6H6G3F1E1D0C0B0A-1R1235987460123456789鏈表中結(jié)點：class

CTNode{

int

child;

CTNode

next;};數(shù)組中結(jié)點：class

CTBox<T>{Tdata;

intparent;

CTNode

firstchild;

//孩子鏈表頭引用};整個數(shù)組：CTBox<Character>[]tree1=(CTBox<Character>[])newObject[10];6K6H6G3F1E1D0C0B0A-1R1235987460123456789用JAVA語言描述一下此種結(jié)構(gòu)：4.孩子兄弟表示法（二叉鏈表表示）結(jié)點的左指針指向結(jié)點的第一個孩子結(jié)點，右指針指向下一個兄弟結(jié)點。ABFKHGEDCRKFACDEGHBR結(jié)點的C#表示：class

CSNode<T>{Tdata;

CSNode<T>firstchild;

CSNode<T>nextsibling;};KFACDEGHBRABFKHGEDCRABFKHGEDCR以二叉鏈表為媒介可以導(dǎo)出樹和二叉樹之間的一個對應(yīng)關(guān)系。給定一棵樹，可以找到唯一的一棵二叉樹與之對應(yīng)。圖示樹對應(yīng)的二叉樹是什麼？練習(xí)：畫出圖示樹對應(yīng)的二叉樹ADECBBEDCAADECB6.4.2森林與二叉樹的轉(zhuǎn)換１、森林轉(zhuǎn)換成二叉樹：

1）將森林中的每一棵樹都轉(zhuǎn)化成二叉樹

2）第二棵二叉樹作為第一棵二叉樹的右子樹，第三棵二叉樹作為第二棵二叉樹的右子樹，依次類推。例題：將下面三棵樹的森林轉(zhuǎn)化成二叉樹。2、二叉樹轉(zhuǎn)換成森林1）分解二叉樹取二叉樹的根及左子樹為第一棵二叉樹，取其右子樹的根及其左子樹為第二棵二叉樹……依次類推。2）把沒有右子樹的二叉樹轉(zhuǎn)化成樹。例題：將下面的二叉樹轉(zhuǎn)化成森林。6.4.3樹與森林的遍歷1、樹的遍歷（先根遍歷、后根遍歷）（1）先根遍歷：先訪問樹的根結(jié)點，然后依次先根遍歷根的每棵子樹（2）后根遍歷：先依次后根遍歷每棵子樹，然后訪問根結(jié)點圖示樹的先根遍歷結(jié)果：ABCDE圖示樹的后根遍歷結(jié)果：BDCEA對應(yīng)二叉樹的先序遍歷結(jié)果：ABCDE對應(yīng)二叉樹的中序遍歷結(jié)果：BDCEA樹的先根遍歷轉(zhuǎn)換后的二叉樹的先序遍歷樹的后根遍歷轉(zhuǎn)換后的二叉樹的中序遍歷森林的遍歷(1)先根次序遍歷的規(guī)則：

訪問F的第一棵樹的根結(jié)點；

先根次序遍歷第一棵樹的子樹森林；

先根次序遍歷其它樹組成的森林。(2)中根次序遍歷的規(guī)則：

中根次序遍歷第一棵樹的子樹森林；

訪問F的第一棵樹的根結(jié)點；

中根次序遍歷其它樹組成的森林。 森林的先序遍歷：對應(yīng)二叉樹的先序遍歷森林的中序遍歷：對應(yīng)二叉樹的中序遍歷具有不同路徑長度的二叉樹6.6赫夫曼樹

(HuffmanTree)及其應(yīng)用1、路徑長度(PathLength)

兩個結(jié)點之間的路徑長度是連接兩結(jié)點的路徑上的分支數(shù)。樹的路徑長度是各結(jié)點到根結(jié)點的路徑長度之和。6.6.1哈夫曼樹2、帶權(quán)路徑長度(WeightedPathLength,WPL)

結(jié)點的帶權(quán)路徑長度：從該結(jié)點到樹根的路徑長度與結(jié)點上權(quán)的乘積。

樹的帶權(quán)路徑長度是樹的各葉結(jié)點所帶的權(quán)值與該結(jié)點到根的路徑長度的乘積的和。3、Huffman樹

給定的n個權(quán)值{w1,w2,…,wn},在n個葉結(jié)點（葉結(jié)點權(quán)值分別為w1,w2,…,wn

）的帶權(quán)二叉樹中，帶權(quán)路徑長度達(dá)到最小的二叉樹稱為Huffman(哈夫曼)樹,又稱最優(yōu)二叉樹。給定的n個權(quán)值{w1,w2,…,wn}，如何構(gòu)造一棵哈夫曼樹？

Huffman算法(1)

由給定的n個權(quán)值{w1,w2,…,wn}，構(gòu)造具有n棵二叉樹的森林F={T1,T2,…,Tn}，其中每一棵二叉樹Ti只有一個帶有權(quán)值wi的根結(jié)點，其左、右子樹均為空。

在F中選取兩棵根結(jié)點的權(quán)值最小的二叉樹,作為左、右子樹合并成一棵新的二叉樹，且新二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和。

(2)

重復(fù)以下步驟,直到F中僅剩下一棵樹為止：

Huffman樹構(gòu)造示例在F中選取兩棵根結(jié)點的權(quán)值最小的二叉樹,作為左、右子樹合并成一棵新的二叉樹，且新二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和。作業(yè)：給定一組權(quán)值（5，9，11，2，7，16），試設(shè)計相應(yīng)的哈夫曼樹。6.6.2哈夫曼樹的應(yīng)用(哈夫曼編碼)對信息進行編碼，得到二進制碼文，在介質(zhì)（網(wǎng)線）中傳輸?shù)氖潜忍亓鳎炊M制碼文），接收方對收到的二進制碼文按編碼規(guī)則進行譯碼，還原成信息。‘ABACCDA’

00010010101100‘ABACCDA’

編碼譯碼A,B,C,D四個的編碼分別為00,01,10和11。通過網(wǎng)絡(luò)傳輸7道選擇題的答案給同學(xué)‘ABACCDA’,因為要傳輸?shù)男畔⒅兄怀霈F(xiàn)了ABCD四種字符，用？位二進制編碼就可以。對ABCD的編碼如下所示：則信息‘ABACCDA’的編碼為：00010010101100,要傳送的二進制碼文總長為14位。二進制碼文到達(dá)接收方后，接收方按照二位一個字符的編碼原則進行譯碼，還原成信息‘ABACCDA’。

別的因素相同的情況下，所要傳輸?shù)亩M制碼文長度越短，信息傳輸所需要的時間越短，信息的傳輸速度就越快。

為減少二進制碼文長度,重新設(shè)A,B,C,D四個字符的編碼為0,00,1和01，則‘ABACCDA’的二進制碼文為000011010,總長為9位。接收方對收到的二進制碼文進行譯碼的時候會出現(xiàn)什麼問題呢？

0000可譯成ABA，AAAA，BB，BAA

都可以。

盡管這種編碼方式縮短了二進制碼文，但由于不能正確地譯碼，所以是不可行的。怎樣的編碼才能正確地譯碼呢？前綴編碼前綴編碼：任何一個字符的編碼都不是另一個字符的編碼的前綴。000101

010010111

ABCD00011011

是前綴編碼不是前綴編碼是前綴編碼

利用赫夫曼樹可以構(gòu)造一種不等長的二進制編碼，并且構(gòu)造所得的赫夫曼編碼是一種最優(yōu)前綴編碼，使所傳二進制碼文的總長度最短。利用哈夫曼樹構(gòu)造哈夫曼編碼

1、以信息‘ABACCDA’各個字符出現(xiàn)的次數(shù)作為權(quán)值構(gòu)造哈夫曼樹。

A--3B--1C--2D--17124312BDCA2、從根結(jié)點開始，左分支填0，右分支填1。7124312BDCA010011

3、根據(jù)哈夫曼樹可得到哈夫曼編碼，如下所示：

A--0B--110C--10D--111

按哈夫曼編碼A--0B--110C--10D--111

對信息‘ABACCDA’進行編碼：0110010

10

1110二進制碼文總長度13位

再也找不到一種前綴編碼使得二進制碼文比這個長度更短。

A--0B--100C--101D--11是前綴編碼信息‘ABACCDA’的編碼為：01000101101110二進制碼文總長度是14位。

A--00B--01C--10D--11是前綴編碼信息‘ABACCDA’的編碼為：00010010101100二進制碼文總長度為14位。

作業(yè):已知某系統(tǒng)在通訊聯(lián)絡(luò)中只可能出現(xiàn)八種字符A,B,C,D,E,F,G,H,其概率分別為:0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11。試設(shè)計赫夫曼編碼.

解：可以以概率{0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11}作為權(quán)值構(gòu)造哈夫曼樹。若嫌小數(shù)麻煩，也可以以概率*100作為權(quán)值構(gòu)造哈夫曼樹。只要各個權(quán)值的比例保持不變就行。即以{5,29,7,8,14,23,3,11}作為權(quán)值構(gòu)造哈夫曼樹。1、構(gòu)造哈夫曼樹295783142311A5G38D8C715H1119E1429F2342B29581002、左分支填0，右分支填1，可得到八個字符的哈夫曼編碼。A5G38D8C715H1119E1429F2342B29581000000111100011100010011001111011011101111源碼實現(xiàn)對應(yīng)于哈夫曼樹不同的存儲結(jié)構(gòu)建立哈夫曼樹和求哈夫曼編碼的實現(xiàn)算法也不一樣。假定哈夫曼樹采用如下存儲結(jié)構(gòu)：Weight域存放結(jié)點的權(quán)值，同時parent指出結(jié)點的父親是誰，lChild指出結(jié)點的左孩子是誰、rChild指出右孩子是誰？結(jié)點有四個域：一個域weight，存放該結(jié)點的權(quán)值；一個域lChild，存放該結(jié)點的左孩子結(jié)點在數(shù)組中的序號；一個域rChild，存放該結(jié)點的右孩子結(jié)點在數(shù)組中的序號；一個域parent，存放結(jié)點的父親結(jié)點在數(shù)組中的序號；

weightparentlChild

rChild結(jié)點類Node的C#定義：packagedspackage4;import

java.util.Scanner;classNode{

public

float

weight;

//weight表示該結(jié)點的權(quán)值；

public

int

lChild;

public

int

rChild;

//lChild和rChild分別表示左、右孩子結(jié)點在數(shù)組中的序號；

public

int

parent;

//parent表示結(jié)點的父親結(jié)點在數(shù)組中的序號；

//無參構(gòu)造器

publicNode() {

weight=0;

lChild=-1;

rChild=-1;

parent=-1; }

//四個參數(shù)構(gòu)造器

public

Node(float

w,int

lc,int

rc,int

p) {

weight=w;

lChild=lc;

rChild=rc;

parent=p; }}哈夫曼樹類HuffmanTree的C#實現(xiàn)：public

class

HuffmanTree{

public

int

leafNum;

//leafNum表示哈夫曼樹葉子結(jié)點的數(shù)目；

publicNode[]data;

//data數(shù)組用于存放結(jié)點；

public

HuffmanTree(int

n)

{leafNum=n;

data=newNode[2*n-1];

//在哈夫曼樹中沒有度為1的結(jié)點，哈夫曼樹中總結(jié)點數(shù)=n0+n2又由二叉樹的性質(zhì)知n0=n2+1;即n2=n0-1，所以哈夫曼樹中總結(jié)點數(shù)=n0+n2=2n0-1；所以葉子結(jié)點數(shù)目為n時，總結(jié)點數(shù)目為2n-1，需要一個長度為2n-1的數(shù)組存儲哈夫曼樹中的結(jié)點。

}

//成員方法Create，它的功能是輸入n個葉子結(jié)點的權(quán)值，創(chuàng)建一棵哈夫曼樹

public

voidCreate() {

float

min1;

float

min2;

int

tmp1;

int

tmp2;

//令所有結(jié)點的父親域，左孩子域，右孩子域均為-1

for(int

i=0;i<2*leafNum-1;i++) {

data[i]=newNode();

data[i].parent=data[i].lChild=data[i].rChild=-1; }

//輸入n個葉子結(jié)點的權(quán)值

Scannerreader=newScanner(System.in);

//實例化Scanner類對象reader

//調(diào)用reader對象的相應(yīng)方法，讀取鍵盤數(shù)據(jù)

for(int

i=0;i<leafNum;++i) { System.out.print("第"+(i+1)+"個葉子結(jié)點的權(quán)值");

data[i].weight=reader.nextFloat(); }

//處理leafNum個葉子結(jié)點，建立哈夫曼樹

for(int

i=leafNum;i<2*leafNum-1;++i)

{

min1=min2=Float.MAX_VALUE;

tmp1=tmp2=0;

//在0~i-1個結(jié)點中找權(quán)值最小的兩個結(jié)點

，min1<=min2,循環(huán)執(zhí)行完畢以后，min1權(quán)值最小的結(jié)點的權(quán)值，min2是權(quán)值次小的結(jié)點的權(quán)值。

for(int

j=0;j<i;++j)

{

if((data[j].weight<min1)&&(data[j].parent==-1))

{

min2=min1;

tmp2=tmp1;

tmp1=j;

min1=data[j].weight; }

else

if((data[j].weight<min2)&&(data[j].parent==-1)) {

min2=data[j].weight;

tmp2=j; } }

//權(quán)值最小的兩個結(jié)點父結(jié)點為i

data[tmp1].parent=i;

data[tmp2].parent=i;

data[i].weight=data[tmp1].weight+data[tmp2].weight;

//父結(jié)點的權(quán)值為兩個結(jié)點的權(quán)值之和

//權(quán)值最小的兩結(jié)點分別是i結(jié)點的左孩子和右孩子

data[i].lChild=tmp1;

data[i].rChild=tmp2; } }

1475274Weightparentlchild

rchild7

-1-1

-15

-1-1

-12

-1-1

-14

-1-1

-1

-1-1

-1

-1-1

-1

-1-1

-10123456哈夫曼樹構(gòu)造示例:14852746Weightparentlchild

rchild7

-1-1

-15

-1-1

-12

-1-1

-14

-1-1

-16

-1-1

-1

-1-1

-1

-1-1

-10123456tmp1tmp24423i1495274611Weightparentlchild

rchild7

-1-1

-15

-1-1

-12

4

-1-14

4

-1-16

-12

311

-1-1

-1

-1-1

-10123456tmp1tmp25514i1505274611Weightparentlchild

rchild7

-1-1

-15

5

-1-12

4

-1-14

4

-1-16

5

2

311

-11

418

-1-1

-10123456tmp1tmp26605i18

public

void

huffmancode() {String[]huffman=new

String[leafNum];

//新建一個字符串?dāng)?shù)組huffman，長度為葉子結(jié)點的數(shù)目，存放各葉子的哈夫曼編碼

for(int

i=0;i<leafNum;i++) {

huffman[i]="";//第i個字符串初始值為空

for(int

c=i,f=data[i].parent;f!=-1;c=f,f=data[f].parent)

{

if(data[f].lChild==c)huffman[i]="0"+huffman[i];

else

huffman[i]="1"+huffman[i]; }//從葉子到根逆向求各個葉子結(jié)點的哈夫曼編碼

System.out.println("權(quán)值為"+data[i].weight+"的哈夫曼編碼是"+huffman[i]); } }

public

static

void

main(String[]args){

System.out.print("請輸入葉子結(jié)點的數(shù)目"); Scannerreader=new

Scanner(System.in);

//實例化Scanner類對象reader

//調(diào)用reader對象的相應(yīng)方法，讀取鍵盤數(shù)據(jù)

int

m=reader.nextInt();

HuffmanTree

ceshi=new

HuffmanTree(m);

//調(diào)用構(gòu)造函數(shù)

System.out.println("請輸入各葉子結(jié)點的權(quán)值");

ceshi.Create();//構(gòu)造哈夫曼樹

ceshi.huffmancode();//求哈夫曼編碼

}}

作業(yè):已知某系統(tǒng)在通訊聯(lián)絡(luò)中只可能出現(xiàn)十種字符A,B,C,D,E,F,G,H,I,G

其概率分別為:0.04,0.21,0.09,0.07,0.08,0.14,0.11,0.13,0.10,0.03。試設(shè)計赫夫曼編碼.

解：可以以概率{0.04,0.21,0.09,0.07,0.08,0.14,0.11,0.13,0.10,0.03}作為權(quán)值構(gòu)造哈夫曼樹。若嫌小數(shù)麻煩，也可以以概率*100作為權(quán)值構(gòu)造哈夫曼樹。只要各個權(quán)值的比例保持不變就行。即以{4,21,9,7,8,14,11,13,10,3}作為權(quán)值構(gòu)造哈夫曼樹。1、構(gòu)造哈夫曼樹42111021217347141327981714312、左分支填0，右分支填1，可得到十個字符的哈夫曼編碼。4211g10i2121b7d3j4a71413h279c8e1714f31010000000011