數(shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言版)-樹(shù)與二叉樹(shù)

數(shù)據(jù)結(jié)構(gòu)與算法

(C#語(yǔ)言版)

DataStructure&AlgorithminC#第6章樹(shù)與二叉樹(shù)電子信息學(xué)院IPLTableofContents第1章緒論第2章線性表第3章棧與隊(duì)列第4章串第5章數(shù)組和廣義表第6章樹(shù)和二叉樹(shù)第7章圖第8章查找第9章排序本章位置TableofContents6.0簡(jiǎn)介6.1樹(shù)的定義與基本術(shù)語(yǔ)6.2二叉樹(shù)的定義與實(shí)現(xiàn)6.3二叉樹(shù)的遍歷6.4線索二叉樹(shù)6.5用二叉樹(shù)表示樹(shù)與森林6.0Introduction樹(shù)結(jié)構(gòu)是一種數(shù)據(jù)元素之間具有層次關(guān)系的非線性結(jié)構(gòu)。除根結(jié)點(diǎn)外，每個(gè)數(shù)據(jù)元素只有一個(gè)前驅(qū)數(shù)據(jù)元素，可有零個(gè)或若干個(gè)后繼數(shù)據(jù)元素。樹(shù)結(jié)構(gòu)有樹(shù)和二叉樹(shù)兩種。二叉樹(shù)是最多只有兩個(gè)子樹(shù)且兩個(gè)子樹(shù)有左右之分的有序樹(shù)。本章介紹具有層次關(guān)系的樹(shù)結(jié)構(gòu)，重點(diǎn)討論二叉樹(shù)的定義、性質(zhì)、存儲(chǔ)結(jié)構(gòu)和遍歷算法，并討論線索二叉樹(shù)的定義、存儲(chǔ)結(jié)構(gòu)和遍歷算法。6.1樹(shù)的定義與基本術(shù)語(yǔ)6.1.1

樹(shù)的定義和表示6.1.2

樹(shù)的基本術(shù)語(yǔ)樹(shù)結(jié)構(gòu)從自然界中的樹(shù)抽象而來(lái)，有樹(shù)根、從根發(fā)源類似枝杈的分支以及作為分支終點(diǎn)的葉子等。6.1.1樹(shù)的定義和表示樹(shù)(tree)是由n個(gè)結(jié)點(diǎn)組成的有限集合。n=0的樹(shù)稱為空樹(shù)；對(duì)n>0的樹(shù)T有以下特點(diǎn)：樹(shù)T有一個(gè)特殊的結(jié)點(diǎn)，它沒(méi)有前驅(qū)結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)稱為根結(jié)點(diǎn)（root）。當(dāng)n>1時(shí)，除根結(jié)點(diǎn)之外的其他結(jié)點(diǎn)分為m個(gè)互不相交的集合T1,T2,…,Tm，其中每個(gè)集合Ti本身又是一棵樹(shù)，稱作子樹(shù)(subtree)。無(wú)序樹(shù)與有序樹(shù)在無(wú)序樹(shù)（unorderdtree）中，結(jié)點(diǎn)的子樹(shù)T1，T2，…之間沒(méi)有次序。通常所說(shuō)的樹(shù)指的是無(wú)序樹(shù)。如果樹(shù)中結(jié)點(diǎn)的子樹(shù)T1，T2，…從左至右是有次序的，則稱該樹(shù)為有序樹(shù)（orderdtree）。樹(shù)與森林若干棵互不相交的樹(shù)的集合稱為森林（forest）。給森林加上一個(gè)根結(jié)點(diǎn)就變成一棵樹(shù)；將樹(shù)的根結(jié)點(diǎn)刪除就變成由子樹(shù)組成的森林。樹(shù)的廣義表形式表示可以用廣義表的形式表示樹(shù)結(jié)構(gòu)。例如圖示樹(shù)的廣義表表示形式為：

A（B（C，D），E（F，G，H），I（J））樹(shù)中的葉結(jié)點(diǎn)對(duì)應(yīng)廣義表中的原子，非葉結(jié)點(diǎn)對(duì)應(yīng)子表。樹(shù)結(jié)構(gòu)的廣義表是一種純表，其中沒(méi)有共享和遞歸成分。6.1.2樹(shù)的基本術(shù)語(yǔ)node:結(jié)點(diǎn)表示樹(shù)集合中的一個(gè)數(shù)據(jù)元素，它由元素的數(shù)據(jù)和指向它的子結(jié)點(diǎn)的指針構(gòu)成。childnode與parentnode:若結(jié)點(diǎn)N有子樹(shù)，則子樹(shù)的根結(jié)點(diǎn)稱為結(jié)點(diǎn)N的子結(jié)點(diǎn)。N稱為其孩子的父結(jié)點(diǎn)。siblingnode:同一雙親的子結(jié)點(diǎn)之間互稱兄弟結(jié)點(diǎn)。ancestornode與descendantnode:結(jié)點(diǎn)的祖先是指從根到該結(jié)點(diǎn)所經(jīng)過(guò)的所有結(jié)點(diǎn)。后代是指結(jié)點(diǎn)的所有子結(jié)點(diǎn)，以及各子結(jié)點(diǎn)的子結(jié)點(diǎn)。樹(shù)的基本術(shù)語(yǔ)(II)degreeofnode&tree

:結(jié)點(diǎn)的度定義為結(jié)點(diǎn)所擁有子樹(shù)的棵數(shù)。樹(shù)的度是指樹(shù)中各結(jié)點(diǎn)度的最大值。leafnode與branchnode:葉子結(jié)點(diǎn)是指度為0的結(jié)點(diǎn)，又稱為終端結(jié)點(diǎn)。除葉子結(jié)點(diǎn)以外的其他結(jié)點(diǎn)，稱為分支結(jié)點(diǎn)或非葉子結(jié)點(diǎn)，又稱為非終端結(jié)點(diǎn)。edge:設(shè)樹(shù)中M結(jié)點(diǎn)是N結(jié)點(diǎn)的父結(jié)點(diǎn)，有序?qū)?lt;M，N>稱為連接這兩個(gè)結(jié)點(diǎn)的邊。path與path

length:如果（N1，N2，…，Nk）是由樹(shù)中結(jié)點(diǎn)組成的一個(gè)序列，且<

Ni，Ni+1

>都是樹(shù)的邊，則該序列稱為從N1到Nk的一條路徑。路徑上邊的條數(shù)稱為該路徑長(zhǎng)度。level:結(jié)點(diǎn)N的層次與從根到該結(jié)點(diǎn)的路徑長(zhǎng)度有關(guān)。令根結(jié)點(diǎn)的層次為0，其余結(jié)點(diǎn)的層次等于它雙親結(jié)點(diǎn)的層次加1。顯然，兄弟結(jié)點(diǎn)的層次相同。depth:樹(shù)中結(jié)點(diǎn)的最大層次數(shù)稱為樹(shù)的深度或高度。6.2二叉樹(shù)的定義與實(shí)現(xiàn)6.2.1二叉樹(shù)的定義6.2.2二叉樹(shù)的性質(zhì)6.2.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)6.2.4二叉樹(shù)類的定義6.2.1二叉樹(shù)的定義二叉樹(shù)(binarytree)的遞歸定義：二叉樹(shù)是n個(gè)結(jié)點(diǎn)組成的有限集合。n=0時(shí)稱為空二叉樹(shù)；n>0時(shí)，二叉樹(shù)由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為左子樹(shù)和右子樹(shù)的子二叉樹(shù)構(gòu)成。二叉樹(shù)是一種有序樹(shù)，每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)有左、右之分，即使只有一個(gè)子樹(shù)，也要區(qū)分是左子樹(shù)還是右子樹(shù)。二叉樹(shù)的結(jié)點(diǎn)最多只有兩棵子樹(shù)，所以二叉樹(shù)的度最多為2。二叉樹(shù)的五種基本形態(tài)（a）為空二叉樹(shù)。（b）為只有一個(gè)結(jié)點(diǎn)作（根結(jié)點(diǎn)）的二叉樹(shù)。（c）為由根結(jié)點(diǎn)，非空的左子樹(shù)和空的右子樹(shù)組成的二叉樹(shù)。（d）為由根結(jié)點(diǎn)，空的左子樹(shù)和非空的右子樹(shù)組成的二叉樹(shù)。（e）為由根結(jié)點(diǎn)，非空的左子樹(shù)和非空的右子樹(shù)組成的二叉樹(shù)。【例6.1】畫(huà)出3個(gè)結(jié)點(diǎn)的樹(shù)與二叉樹(shù)的基本形態(tài)(a)3個(gè)結(jié)點(diǎn)的樹(shù)的2種基本形態(tài)(b)3個(gè)結(jié)點(diǎn)的二叉樹(shù)的5種基本形態(tài)6.2.2二叉樹(shù)的性質(zhì)性質(zhì)一：二叉樹(shù)第i層的結(jié)點(diǎn)數(shù)目最多為2i

(i

≥

0)。

用歸納法證明。歸納基礎(chǔ)：根是i=0層上的惟一結(jié)點(diǎn)，故2i=1，命題成立。歸納假設(shè)：對(duì)所有j(0≤j<i)，j層上的最大結(jié)點(diǎn)數(shù)為2j。歸納步驟：根據(jù)歸納假設(shè)，第i-1層上的最大結(jié)點(diǎn)數(shù)為2i-1；由于二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度最大為2，故第i層上的最大結(jié)點(diǎn)數(shù)為2×2i-1=2i。命題成立。性質(zhì)二：在深度為k的二叉樹(shù)中，至多有2k+1-1個(gè)結(jié)點(diǎn)。二叉樹(shù)的性質(zhì)(II)性質(zhì)三：二叉樹(shù)中，若葉子結(jié)點(diǎn)數(shù)為n0，2度結(jié)點(diǎn)數(shù)為n2，則有n0=n2+1。

證明：設(shè)二叉樹(shù)結(jié)點(diǎn)數(shù)為n，度為1的結(jié)點(diǎn)數(shù)為n1，則有：n=n0+n1+n2

度為1的結(jié)點(diǎn)有1個(gè)子女，度為2的結(jié)點(diǎn)有2個(gè)子女，葉子結(jié)點(diǎn)沒(méi)有子女，根結(jié)點(diǎn)不是任何結(jié)點(diǎn)的子女，從子女結(jié)點(diǎn)數(shù)角度看，有

n=0×n0+1×n1+2×n2+1

綜合上述兩式，可得n0=n2+1，即二叉樹(shù)中葉子結(jié)點(diǎn)數(shù)比度為2的結(jié)點(diǎn)數(shù)多1。二叉樹(shù)的性質(zhì)(III)性質(zhì)四：如果一棵完全二叉樹(shù)有n個(gè)結(jié)點(diǎn)，則其深度深度為k的滿二叉樹(shù)

(fullbinarytree)具有2k+1-1個(gè)結(jié)點(diǎn)。結(jié)點(diǎn)數(shù)目都達(dá)到最大值。對(duì)滿二叉樹(shù)的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)，約定編號(hào)從根結(jié)點(diǎn)開(kāi)始，自上而下，每層自左至右。具有n個(gè)結(jié)點(diǎn)深度為k的二叉樹(shù)，如果它的每個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中編號(hào)為0~n-1的結(jié)點(diǎn)一一對(duì)應(yīng)，則稱為完全二叉樹(shù)(completebinarytree)。滿二叉樹(shù)與完全二叉樹(shù)滿二叉樹(shù)一定是完全二叉樹(shù)，而完全二叉樹(shù)不一定是滿二叉樹(shù)。完全二叉樹(shù)只有最下面一層可以不滿，其上各層都可看成滿二叉樹(shù)。完全二叉樹(shù)至多只有最下面兩層結(jié)點(diǎn)的度可以小于2。完全二叉樹(shù)最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置上。二叉樹(shù)的性質(zhì)(續(xù))性質(zhì)五：若將一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按順序表示，編號(hào)為i的結(jié)點(diǎn)，有如下特點(diǎn)：若i=0，則結(jié)點(diǎn)i為根結(jié)點(diǎn)；若i≠0，則結(jié)點(diǎn)i的雙親是編號(hào)為(i-1)/2的結(jié)點(diǎn)。若2i+1≤n-1，則i的左孩子是編號(hào)為2i+1的結(jié)點(diǎn)；若2i+1>n-1，則i無(wú)左孩子。若2i+2≤n-1，則i的右孩子是編號(hào)為2i+2的結(jié)點(diǎn)；若2i+2＞n-1，則i無(wú)右孩子。6.2.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)1.二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)2.二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹(shù)結(jié)構(gòu)是一種具有層次關(guān)系的數(shù)據(jù)結(jié)構(gòu)，用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)二叉樹(shù)更加靈活方便，所以一般情況下，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)二叉樹(shù)。二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)適用于完全二叉樹(shù)，對(duì)完全二叉樹(shù)進(jìn)行順序編號(hào)，將編號(hào)為i的結(jié)點(diǎn)存放在數(shù)組下標(biāo)為i的位置上。二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)每個(gè)結(jié)點(diǎn)有3個(gè)域：數(shù)據(jù)域data，表示結(jié)點(diǎn)的數(shù)據(jù)元素；左鏈域left，指向該結(jié)點(diǎn)的左子結(jié)點(diǎn)；右鏈域right，指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)。二叉樹(shù)則用其根結(jié)點(diǎn)root表示。樹(shù)中某結(jié)點(diǎn)的左子結(jié)點(diǎn)也代表該結(jié)點(diǎn)的左子樹(shù)，同理，該結(jié)點(diǎn)的右子結(jié)點(diǎn)代表它的右子樹(shù)。若二叉樹(shù)為空，則root==null。6.2.4二叉樹(shù)類的定義public

class

BinaryTreeNode<T>{

privateTdata;//數(shù)據(jù)元素private

BinaryTreeNode<T>left,right;//指向左、右孩子結(jié)點(diǎn)的鏈public

BinaryTreeNode(){left=right=null;}public

BinaryTreeNode(Td){//構(gòu)造有值結(jié)點(diǎn)data=d;left=right=null;}……}二叉樹(shù)的結(jié)點(diǎn)類二叉樹(shù)結(jié)點(diǎn)類的公有屬性

publicTData{get{returndata;}set{data=value;}}public

BinaryTreeNode<T>Left{get{returnleft;}set{left=value;}}public

BinaryTreeNode<T>Right{get{returnright;}set{right=value;}}二叉樹(shù)類public

class

BinaryTree<T>{

protected

BinaryTreeNode<T>root;

//指向二叉樹(shù)的根結(jié)點(diǎn)public

BinaryTree(){//構(gòu)造空二叉樹(shù)root=null;}……}BinaryTree類表示鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的二叉樹(shù)，成員變量root指向二叉樹(shù)的根結(jié)點(diǎn)。6.3.二叉樹(shù)的遍歷6.3.1.二叉樹(shù)遍歷的過(guò)程6.3.2.二叉樹(shù)遍歷的遞歸算法6.3.3.二叉樹(shù)遍歷的非遞歸算法6.3.4.按層次遍歷二叉樹(shù)6.3.5.建立二叉樹(shù)6.3.1二叉樹(shù)遍歷的概念traversal:遍歷二叉樹(shù)就是按照一定次序訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次。若規(guī)定對(duì)子樹(shù)的訪問(wèn)按“先左后右”的次序進(jìn)行，則遍歷二叉樹(shù)有3種次序：先根次序：訪問(wèn)根結(jié)點(diǎn)，遍歷左子樹(shù)，遍歷右子樹(shù)。中根次序：遍歷左子樹(shù)，訪問(wèn)根結(jié)點(diǎn)，遍歷右子樹(shù)。后根次序：遍歷左子樹(shù)，遍歷右子樹(shù)，訪問(wèn)根結(jié)點(diǎn)。先根次序或后根次序反映雙親與孩子結(jié)點(diǎn)的層次關(guān)系，中根次序反映兄弟結(jié)點(diǎn)間的左右次序。遍歷二叉樹(shù)的3種次序先根次序遍歷二叉樹(shù)的過(guò)程若二叉樹(shù)為空，則空操作，返回；否則從根結(jié)點(diǎn)開(kāi)始，訪問(wèn)當(dāng)前結(jié)點(diǎn)；若當(dāng)前結(jié)點(diǎn)的左子樹(shù)不空，則沿著left鏈進(jìn)入該結(jié)點(diǎn)的左子樹(shù)進(jìn)行遍歷。若當(dāng)前結(jié)點(diǎn)的右子樹(shù)不空，則沿著right鏈進(jìn)入該結(jié)點(diǎn)的右子樹(shù)進(jìn)行遍歷。6.3.2二叉樹(shù)遍歷的遞歸算法按先根次序遍歷二叉樹(shù)的遞歸算法若二叉樹(shù)為空，則空操作，返回；否則從根結(jié)點(diǎn)開(kāi)始，訪問(wèn)當(dāng)前結(jié)點(diǎn)。按先根次序遍歷當(dāng)前結(jié)點(diǎn)的左子樹(shù)。按先根次序遍歷當(dāng)前結(jié)點(diǎn)的右子樹(shù)。先根次序遍歷二叉樹(shù)的遞歸算法public

void

ShowPreOrder(){

Console.Write(this.Data+“”);

BinaryTreeNode<T>q=this.Left;if(q!=null)q.ShowPreOrder();q=this.Right;if(q!=null)q.ShowPreOrder();}public

void

TraversalPreOrder(IList<T>sql){

sql.Add(this.Data);

BinaryTreeNode<T>q=this.Left;if(q!=null)q.TraversalPreOrder(sql);q=this.Right;if(q!=null)q.TraversalPreOrder(sql);}BinaryTreeNode從根結(jié)點(diǎn)先根次序遍歷二叉樹(shù)public

void

ShowPreOrder(){

Console.Write(“先根次序：”);if(root!=null)

root.ShowPreOrder();

Console.WriteLine();}public

List<T>TraversalPreOrder(){

List<T>sql=new

List<T>();

if(root!=null)

root.TraversalPreOrder(sql);

return

sql;}BinaryTree中根次序遍歷二叉樹(shù)的遞歸算法public

void

ShowInOrder(){

BinaryTreeNode<T>q=this.Left;if(q!=null)q.ShowInOrder();

Console.Write(this.Data+“”);q=this.Right;if(q!=null)q.ShowInOrder();}public

void

TraversalInOrder(IList<T>sql){

BinaryTreeNode<T>q=this.Left;if(q!=null)q.TraversalInOrder(sql);

sql.Add(this.Data);q=this.Right;if(q!=null)q.TraversalInOrder(sql);}BinaryTreeNode從根結(jié)點(diǎn)中根次序遍歷二叉樹(shù)public

voidShowInOrder(){

Console.Write("中根次序：");

if(root!=null)root.ShowInOrder();

Console.WriteLine();}public

List<T>TraversalInOrder(){List<T>sql=new

List<T>();

if(root!=null)root.TraversalInOrder(sql);

returnsql;}BinaryTree后根次序遍歷二叉樹(shù)的遞歸算法public

void

ShowPostOrder(){

BinaryTreeNode<T>q=this.Left;if(q!=null)q.ShowPostOrder();q=this.Right;if(q!=null)q.ShowPostOrder();

Console.Write(this.Data+"");}public

voidTraversalPostOrder(IList<T>sql){BinaryTreeNode<T>q=this.Left;if(q!=null)q.TraversalPostOrder(sql);q=this.Right;if(q!=null)q.TraversalPostOrder(sql);sql.Add(this.Data); }BinaryTreeNode從根結(jié)點(diǎn)后根次序遍歷二叉樹(shù)public

voidShowPostOrder(){

Console.Write("后根次序：");

if(root!=null)root.ShowPostOrder();

Console.WriteLine();}public

List<T>TraversalPostOrder(){List<T>sql=new

List<T>();

if(root!=null)root.TraversalPostOrder(sql);

returnsql;}BinaryTree【例6.2】按先根、中根和后根次序遍歷二叉樹(shù)BinaryTree<int>btree=new

BinaryTree<int>();BinaryTreeNode<int>[]nodes=new

BinaryTreeNode<int>[9];for(inti=1;i<=8;i++)nodes[i]=new

BinaryTreeNode<int>(i);btree.Root=nodes[1];nodes[1].Left=nodes[2];nodes[1].Right=nodes[3];nodes[2].Left=nodes[4];nodes[3].Left=nodes[5];nodes[3].Right=nodes[6];nodes[4].Right=nodes[7];nodes[6].Left=nodes[8];btree.ShowPreOrder();btree.ShowInOrder();btree.ShowPostOrder();

BinaryTree<string>btree2=new

BinaryTree<string>();btree2.Root=new

BinaryTreeNode<string>(“大學(xué)”);btree2.Root.Left=new

BinaryTreeNode<string>(“學(xué)院1”);6.3.3二叉樹(shù)遍歷的非遞歸算法中根次序遍歷:在每個(gè)結(jié)點(diǎn)處，先選擇遍歷左子樹(shù)，當(dāng)左子樹(shù)遍歷完后，必須返回該結(jié)點(diǎn)，訪問(wèn)該結(jié)點(diǎn)后，再遍歷右子樹(shù)。設(shè)置一個(gè)棧。從二叉樹(shù)的根結(jié)點(diǎn)p開(kāi)始，如果p不空或棧不空時(shí)，循環(huán)執(zhí)行以下操作，直到掃描完二叉樹(shù)且棧為空。如果p不空，表示掃描到一個(gè)結(jié)點(diǎn)，將p結(jié)點(diǎn)入棧（Push），進(jìn)入其左子樹(shù)。如果p為空并且棧不空，表示已走出一條路徑，必須返回尋找另一條路徑。設(shè)置p指向出棧的結(jié)點(diǎn)（Pop），訪問(wèn)p結(jié)點(diǎn)，再進(jìn)入p的右子樹(shù)。public

voidShowInOrderNR(){

Stack<BinaryTreeNode<T>>s=newStack<BinaryTreeNode<T>>(20);

BinaryTreeNode<T>p=root;

Console.Write("非遞歸中根次序：");

while(p!=null||s.Count!=0){//p非空或棧非空時(shí)

if(p!=null){s.Push(p);//p結(jié)點(diǎn)入棧p=p.Left;//進(jìn)入左子樹(shù)}else{ //p為空且棧非空時(shí)p=s.Pop();//p指向出棧的結(jié)點(diǎn)

Console.Write(p.Data+“”);//訪問(wèn)結(jié)點(diǎn)p=p.Right; //進(jìn)入右子樹(shù)}}

Console.WriteLine();}二叉樹(shù)的非遞歸中根遍歷過(guò)程6.3.4按層次遍歷二叉樹(shù)按層次遍歷二叉樹(shù):從根結(jié)點(diǎn)開(kāi)始，逐層深入，同層從左至右依次訪問(wèn)結(jié)點(diǎn)。圖示的二叉樹(shù)，其層次遍歷序列為1，2，3，4，5，6，7，8。首先訪問(wèn)根結(jié)點(diǎn)1，再訪問(wèn)根結(jié)點(diǎn)的孩子2和3，然后應(yīng)該訪問(wèn)2的孩子4，再訪問(wèn)3的孩子5結(jié)點(diǎn)……

按層次遍歷二叉樹(shù)的非遞歸算法設(shè)置一個(gè)隊(duì)列。從根結(jié)點(diǎn)p開(kāi)始，當(dāng)不空時(shí)，循環(huán)順序執(zhí)行以下操作：訪問(wèn)p結(jié)點(diǎn)。如果p的left鏈不空，將p結(jié)點(diǎn)的左孩子入隊(duì)(Enqueue)。如果p的right鏈不空，將p結(jié)點(diǎn)的右孩子入隊(duì)。如果隊(duì)列為非空，設(shè)置p指向出隊(duì)(Dequeue)的結(jié)點(diǎn)，否則設(shè)置p指向null。

當(dāng)p==null，循環(huán)停止。public

voidShowByLevel(){varq=new

Queue<BinaryTreeNode<T>>(20);

//設(shè)立一個(gè)空隊(duì)列BinaryTreeNode<T>p=root;Console.Write(“層次遍歷：”);

while(p!=null){

Console.Write(p.Data+“”);

if(p.Left!=null)q.Enqueue(p.Left);//p的左孩子結(jié)點(diǎn)入隊(duì)

if(p.Right!=null)q.Enqueue(p.Right);//p的右孩子結(jié)點(diǎn)入隊(duì)

if(q.Count!=0)p=q.Dequeue();//p指向出隊(duì)的結(jié)點(diǎn)

elsep=null;}

Console.WriteLine();}按層次遍歷二叉樹(shù)時(shí)隊(duì)列內(nèi)容的變化6.3.5建立二叉樹(shù)給定一定的條件，可唯一建立二叉樹(shù)。例如對(duì)于完全二叉樹(shù)，給定它的順序結(jié)構(gòu)，即可唯一建立鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的二叉樹(shù)。一般情況下，建立一棵二叉樹(shù)必須明確以下兩點(diǎn)：結(jié)點(diǎn)與其父結(jié)點(diǎn)及子結(jié)點(diǎn)間的層次關(guān)系。兄弟結(jié)點(diǎn)間的左右順序關(guān)系。二叉樹(shù)可用特殊的廣義表唯一描述，例如在二叉樹(shù)的廣義表表示式中也清楚地標(biāo)明空子樹(shù)，這種形式的

廣義表表示式，可以唯一地建立一顆二叉樹(shù)。對(duì)于給定的一棵二叉樹(shù)，遍歷產(chǎn)生的先根、中根、后根序列是唯一的；反之，僅知一種遍歷序列，并不能唯一確定一棵二叉樹(shù)。先根次序或后根次序反映雙親與孩子結(jié)點(diǎn)的層次關(guān)系，中根次序反映兄弟結(jié)點(diǎn)間的左右次序。所以，已知先根和中根兩種遍歷序列，或中根和后根兩種遍歷序列才能夠唯一確定一棵二叉樹(shù)。建立二叉樹(shù)舉例建立鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的完全二叉樹(shù)以廣義表表示式建立二叉樹(shù)按先根和中根次序遍歷序列建立二叉樹(shù)1.建立鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的完全二叉樹(shù)對(duì)于一棵順序存儲(chǔ)結(jié)構(gòu)的完全二叉樹(shù)，由二叉樹(shù)的性質(zhì)五可知，第0個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)，第i個(gè)結(jié)點(diǎn)的左孩子為第2i+1個(gè)結(jié)點(diǎn)，右孩子為第2i+2個(gè)結(jié)點(diǎn)。在二叉樹(shù)類BinaryTree<T>中，增加靜態(tài)方法ByOneList，它的參數(shù)t是一個(gè)線性表或數(shù)組，用以表示順序存儲(chǔ)的完全二叉樹(shù)結(jié)點(diǎn)值的序列。public

static

BinaryTree<T>ByOneList(IList<T>t){

intn=t.Count;

BinaryTree<T>bt=new

BinaryTree<T>();

if(n==0){bt.Root=null;return

bt;}

int

i,j;Tv;

BinaryTreeNode<T>[]q=new

BinaryTreeNode<T>[n];for(i=0;i<n;i++){v=t[i];//取編號(hào)為i的結(jié)點(diǎn)值q[i]=new

BinaryTreeNode<T>(v);}

for(i=0;i<n;i++){j=2*i+1;

if(j<n)q[i].Left=q[j];

elseq[i].Left=null;j++;

if(j<n)q[i].Right=q[j];

elseq[i].Right=null;}

bt.Root=q[0];return

bt;}static

voidMain(string[]args){

int[]it={0,1,2,3,4,5,6,7};

BinaryTree<int>btree=

BinaryTree<int>.ByOneList(it);

btree.ShowPreOrder();

btree.ShowInOrder();char[]ct={‘A’,‘B’,‘C’,‘D’,‘E’,‘F’,‘G’,‘H’};

BinaryTree<char>btree2=

BinaryTree<char>.ByOneList(ct);}【例6.3】根據(jù)給定數(shù)組建立完全二叉樹(shù)2.以廣義表表示式建立二叉樹(shù)廣義表形式一般不能惟一表示一棵二叉樹(shù)，原因在于無(wú)法明確左右子樹(shù)。例如，廣義表A(B)沒(méi)有表達(dá)出結(jié)點(diǎn)B是結(jié)點(diǎn)A的左子結(jié)點(diǎn)還是右子結(jié)點(diǎn)。為了惟一表示一棵二叉樹(shù)，必須重新定義廣義表的形式。在廣義表中，除數(shù)據(jù)元素外還定義四個(gè)邊界符號(hào)：左界符LeftDelimitFlag，如‘(’，以標(biāo)明下一層次的左邊界；右界符RightDelimitFlag，如‘)’，以標(biāo)明下一層次的右邊界。中界符MiddleDelimitFlag，如‘,’，以標(biāo)明某一層次的左右子樹(shù)的分界。空子樹(shù)符NullSubtreeFlag，如‘^’，以標(biāo)明非葉子結(jié)點(diǎn)的空子樹(shù)。1(2(4(^,7),^),3(5,6(8,^)))以廣義表表示式建立二叉樹(shù)的算法依次讀取二叉樹(shù)的廣義表表示序列中的每個(gè)元素，如果遇到有效數(shù)據(jù)值，建立一個(gè)結(jié)點(diǎn)；移到下一元素，如果它為L(zhǎng)eftDelimitFlag，則LeftDelimitFlag和RightDelimitFlag之間是該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)，再遞歸調(diào)用，分別建立左、右子樹(shù)，返回結(jié)點(diǎn)對(duì)象。如果沒(méi)有遇到LeftDelimitFlag，表示該結(jié)點(diǎn)是葉子結(jié)點(diǎn)。如果遇到NullSubtreeFlag，表示空子樹(shù)，返回null值。在二叉樹(shù)類BinaryTree<T>中，增加靜態(tài)方法ByOneList，它的第一個(gè)參數(shù)表示順序存儲(chǔ)的廣義表表示式，第二個(gè)參數(shù)定義廣義表所用的分界符。public

static

BinaryTree<T>ByOneList(

IList<T>sList,ListFlagsStruc<T>ListFlags){

BinaryTree<T>.ListFlags=ListFlags;

BinaryTree<T>.idx=0;//初始化遞歸變量

BinaryTree<T>bt=new

BinaryTree<T>();

if(sList.Count>0)bt.Root=RootByOneList(sList);

else

bt.Root=null;

returnbt;}private

static

BinaryTreeNode<T>RootByOneList(IList<T>sList){

BinaryTreeNode<T>p=null;TnodeData=sList[idx];//序列當(dāng)前元素的值

if(isData(nodeData)){p=new

BinaryTreeNode<T>(nodeData);//有效數(shù)據(jù)，建立結(jié)點(diǎn)idx++;nodeData=sList[idx];

if(nodeData.Equals(ListFlags.LeftDelimitFlag)){idx++;//左邊界，如'（'，跳過(guò)p.Left=RootByOneList(sList);//建立左子樹(shù)，遞歸idx++;//跳過(guò)中界符，如','p.Right=RootByOneList(sList);//建立右子樹(shù)，遞歸idx++;//跳過(guò)右邊界，如')'}}

if(nodeData.Equals(ListFlags.NullSubtreeFlag))idx++;//空子樹(shù)符，跳過(guò)，返回null

returnp;}static

voidMain(string[]args){

strings="1(2(4(^,7),^),3(5,6(8,^)))";

Console.WriteLine("GeneralizedList:"+s);

ListFlagsStruc<char>ListFlags;

ListFlags.NullSubtreeFlag='^';

ListFlags.LeftDelimitFlag='(';

ListFlags.RightDelimitFlag=')';

ListFlags.MiddleDelimitFlag=',';

BinaryTree<char>btree=BinaryTree<char>.

ByOneList(s.ToCharArray(0,s.Length),ListFlags);

btree.ShowPreOrder();

btree.ShowInOrder();}3.按先根和中根次序遍歷序列建立二叉樹(shù)設(shè)二叉樹(shù)的先根及中根次序遍歷序列分別為線性表或數(shù)組preList和inList。確定根元素。由先根次序知，二叉樹(shù)的根為preList[0]。查找它在inList中的位置k=inList.IndexOf(rootData);確定根的左子樹(shù)的相關(guān)序列。由中根次序知，inList[k]之前的結(jié)點(diǎn)在根的左子樹(shù)上，inList[k]之后的結(jié)點(diǎn)在根的右子樹(shù)上。因此根的左子樹(shù)由k個(gè)結(jié)點(diǎn)組成：先根序列——preList[1]，…，preList[k]。中根序列——inList[0]，…，inList[k-1]。根據(jù)左子樹(shù)的先根序列和中根序列遞歸建立左子樹(shù)。確定根的右子樹(shù)的相關(guān)序列。右子樹(shù)由n-k-1個(gè)結(jié)點(diǎn)組成：先根序列——preList[k+1]，…，preList[n-1]。中根序列——inList[k+1]，…，inList[n-1]。根據(jù)右子樹(shù)的先根序列和中根序列遞歸建立右子樹(shù)。按先根和中根次序遍歷序列建立二叉樹(shù)usingSystem;usingtrees;namespace

treetest{class

ByTwoListTest{static

voidMain(string[]args){

int[]prelist={1,2,4,7,3,5,6,8};

int[]inlist={4,7,2,1,5,3,8,6};

BinaryTree<int>

btree=BinaryTree<int>.

ByTwoList(prelist,inlist);

btree.ShowPreOrder();

btree.ShowInOrder();}}}【例6.4】按先根和中根次序遍歷序列建立二叉樹(shù)6.4線索二叉樹(shù)從上節(jié)的討論可知：二叉樹(shù)的遍歷將得到一個(gè)二叉樹(shù)結(jié)點(diǎn)集合按一定規(guī)則排列的線性序列，在這個(gè)遍歷序列中，除第一個(gè)和最后一個(gè)結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)。在上節(jié)定義的二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)很容易到達(dá)其左、右子結(jié)點(diǎn)，而不能直接到達(dá)該結(jié)點(diǎn)在任意一個(gè)遍歷序列中的前驅(qū)或后繼結(jié)點(diǎn)，這種信息只能在遍歷的動(dòng)態(tài)過(guò)程中才能得到。下面介紹的線索樹(shù)結(jié)構(gòu)，在不增加很多存儲(chǔ)空間的條件下，能夠存儲(chǔ)遍歷過(guò)程中得到的信息，并在后續(xù)的使用中解決直接訪問(wèn)前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的問(wèn)題。6.4.1線索與線索二叉樹(shù)n個(gè)結(jié)點(diǎn)的二叉樹(shù)，總共有2n個(gè)鏈，僅需要n-1個(gè)鏈來(lái)指明各結(jié)點(diǎn)間的關(guān)系，其余n+1個(gè)鏈均為空值。利用空鏈作線索來(lái)指明結(jié)點(diǎn)在某種遍歷次序下的前驅(qū)和后繼結(jié)點(diǎn)，構(gòu)成線索二叉樹(shù)。對(duì)二叉樹(shù)以某種次序進(jìn)行遍歷并加上線索的過(guò)程稱為線索化。線索二叉樹(shù)中，原先非空的鏈保持不變，仍然指向該結(jié)點(diǎn)的左、右子結(jié)點(diǎn)，它記錄的是結(jié)點(diǎn)間的層次關(guān)系。原先空的左鏈用來(lái)指向遍歷中該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，原先空的右鏈指向后繼結(jié)點(diǎn)，它記錄的是結(jié)點(diǎn)間在遍歷時(shí)的順序關(guān)系。為了區(qū)別每條鏈?zhǔn)欠袷且粋€(gè)線索，可以在二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)中設(shè)置兩個(gè)狀態(tài)字段lefttag和righttag，用以標(biāo)記相應(yīng)鏈的狀態(tài)。線索二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)由5個(gè)域構(gòu)成：data,left,right,lefttag和righttag中序線索二叉樹(shù)6.4.2線索二叉樹(shù)類的實(shí)現(xiàn)1.定義線索二叉樹(shù)結(jié)點(diǎn)類:ThreadBinaryTreeNode<T>，其中有5個(gè)成員變量：data用于表示數(shù)據(jù)元素，left和right分別是指向左、右孩子結(jié)點(diǎn)的鏈，lefttag和righttag為線索標(biāo)記。線索二叉樹(shù)結(jié)點(diǎn)類也是自引用的泛型類，結(jié)點(diǎn)的值類型在對(duì)象實(shí)例化時(shí)決定。2.定義線索二叉樹(shù)類:ThreadBinaryTree，其中成員變量root指向二叉樹(shù)的根結(jié)點(diǎn)。6.4.3二叉樹(shù)的中序線索化設(shè)p指向一棵二叉樹(shù)的某個(gè)結(jié)點(diǎn)，front指向p的前驅(qū)結(jié)點(diǎn)，它的初值為null。當(dāng)p非空時(shí)，執(zhí)行以下操作：中序線索化p結(jié)點(diǎn)的左子樹(shù)。如果p的左子樹(shù)為空，設(shè)置p的lefttag標(biāo)記為true，它的left鏈為指向前驅(qū)結(jié)點(diǎn)front的線索。如果p的右子樹(shù)為空，設(shè)置p的righttag標(biāo)記為true如果前驅(qū)結(jié)點(diǎn)front非空并且它的右鏈為線索，設(shè)置front的right鏈為指向p的線索。移動(dòng)front，使front指向p。中序線索化p結(jié)點(diǎn)的右子樹(shù)。如果一開(kāi)始讓p指向二叉樹(shù)的根結(jié)點(diǎn)root，則上述過(guò)程線索化整個(gè)二叉樹(shù)。6.4.4線索二叉樹(shù)的遍歷中序線索二叉樹(shù)中查找中根次序的后繼結(jié)點(diǎn)。中序線索二叉樹(shù)的中根次序遍歷。中序線索二叉樹(shù)中查找先根次序的后繼結(jié)點(diǎn)。中序線索二叉樹(shù)的先根次序遍歷。1.中序線索二叉樹(shù)中查找中根次序的后繼結(jié)點(diǎn)設(shè)p指向當(dāng)前結(jié)點(diǎn)，執(zhí)行以下操作：如果p結(jié)點(diǎn)的右子樹(shù)為線索，則p的right鏈為其后繼結(jié)點(diǎn)，設(shè)置p為該結(jié)點(diǎn)。否則說(shuō)明p的右子樹(shù)為非空，則p的后繼結(jié)點(diǎn)是p的右子樹(shù)上第一個(gè)中序訪問(wèn)的結(jié)點(diǎn)，即p的右孩子的最左邊的子孫結(jié)點(diǎn)，設(shè)置p為該結(jié)點(diǎn)。返回p，作為當(dāng)前結(jié)點(diǎn)在中根次序下的后繼結(jié)點(diǎn)。在線索二叉樹(shù)結(jié)點(diǎn)類ThreadBinaryTreeNode中，增加NextNodeInOrder方法，以查找某結(jié)點(diǎn)在中根次序下的后繼結(jié)點(diǎn)。public

ThreadBinaryTreeNode<T>NextNodeInOrder(){ThreadBinaryTreeNode<T>p=this;if