計算機軟件基礎課件：樹和二叉樹

樹和二叉樹BasicsofComputerSoftware答辯人：XXX

目錄樹的定義與基本概念1二叉樹及其性質2二叉樹的存儲結構3二叉樹的遍歷45樹和森林哈夫曼樹及其的應用6二叉排序樹及其查找7樹的定義與基本概念PART1線性結構的特征：線性結構的特點是數(shù)據(jù)元素之間存在一對一的線性關系線性結構有兩種不同的存儲結構，即順序存儲和鏈式存儲。分別稱為順序表和鏈表，順序表中的數(shù)據(jù)元素是連續(xù)的，鏈表中的存儲元素不一定是連續(xù)的線性結構中存在兩種操作受限的使用場景，即隊列和棧。棧的插入和刪除操作只能在線性表的一端進行，就是我們常說的先進后出（FILO），而隊列的插入刪除操作分別限定在線性表的兩端進行，即先進先出(FIFO)非線性結構的特征：非線性結構中各個數(shù)據(jù)元素不再保持在一個線性序列中，每個數(shù)據(jù)元素可能與零個或者多個其他數(shù)據(jù)元素發(fā)生聯(lián)系。根據(jù)關系的不同，可分為層次結構和群結構常見的非線性結構有：多維數(shù)組、廣義表、樹(二叉樹等)、圖等。（其中多維數(shù)組是由多個一維數(shù)組組成的，所以不再是線性結構）樹的概念和基本術語樹的定義：樹是有n(n

0)個結點的有限集合。

如果n=0，稱為空樹；如果n>0，則：

有且僅有一個特定的稱之為根(Root)的結點，它只有直接后繼，但沒有直接前驅；當n>1，除根以外的其它結點劃分為m(m>0)個互不相交的有限集T1,T2,…,Tm，其中每個集合本身又是一棵樹，并且稱為根的子樹。ACGBDEFKLHMIJA只有根結點的樹ACGBDEFKLHMIJ有13個結點的樹其中：A是根其余結點分成三個互不相交的子集T1={B,E,F,K,L}；T2={C,G}；T3={D,H,I,J,M},T1,T2,T3都是根A的子樹，且本身也是一棵樹空樹樹根家譜可以用樹描述電氣學院計算機學院航飛學院土木工程學院經(jīng)管學院單位的組織結構軟件的模塊結構樹的基本術語1層2層4層3層height=4ACGBDEFKLHMIJ結點結點的度樹的度葉子結點分支結點孩子雙親祖先子孫兄弟結點層次堂兄弟樹的深度樹的度有序樹和無序樹森林1、結點(Node)：表示樹中的數(shù)據(jù)元素，由數(shù)據(jù)項和數(shù)據(jù)元素之間的關系組成。在圖中，共有13個結點。2、結點的度(DegreeofNode)：結點所擁有的子樹的個數(shù)，在圖中，結點A的度為3。3、樹的度(DegreeofTree)：樹中各結點度的最大值。在圖5.1中，樹的度為3。4、葉子結點(LeafNode)：度為0的結點，也叫終端結點。結點K、L、F、G、M、I、J都是葉子結點。5、分支結點(BranchNode)：度不為0的結點，也叫非終端結點或內部結點。在圖5.1中，結點A、B、C、D、E、H是分支結點。6、孩子(Child)：結點子樹的根。在圖中，結點B、C、D是結點A的孩子。H、I、J是D的孩子7、雙親(Parent)：結點的上層結點叫該結點的雙親。在圖中，結點B、C、D的雙親是結點A。8、祖先(Ancestor)：從根到該結點所經(jīng)分支上的所有結點。在圖中，結點E的祖先是A和B。m的祖先是a，d，h9、子孫(Descendant)：以某結點為根的子樹中的任一結點稱為該節(jié)點的子孫。在圖中，除A之外的所有結點都是A的子孫。d的子孫是h、i、j、m10、兄弟(Brother)：同一雙親的孩子。在圖5.1中，結點B、C、D互為兄弟。EF互為兄弟11、結點的層次(LevelofNode)：從根結點到樹中某結點所經(jīng)路徑上的分支數(shù)稱為該結點的層次。根結點的層次規(guī)定為1，其余結點的層次等于其雙親結點的層次加1。即a的層次為1，bcd的層次為2，klm的層次為4

12、堂兄弟(Sibling)：同一層的雙親不同的結點。在圖中，G和H互為堂兄弟。13、樹的深度(DepthofTree)：樹中結點的最大層次數(shù)。在圖中，樹的深度為4。14、無序樹(UnorderedTree)：樹中任意一個結點的各孩子結點之間的次序構成，無關緊要的樹。通常指無序樹。

15、與無序樹對應，有序樹(OrderedTree)是指樹中任意一個結點的各孩子結點有嚴格排列次序的樹。二叉樹是有序樹，因為二叉樹中每個孩子結點都確切定義為是該結點的左孩子結點還是右孩子結點。

16、森林(Forest)：m(m≥0)棵樹的集合。自然界中的樹和森林的概念差別很大，但在數(shù)據(jù)結構中樹和森林的概念差別很小。從定義可知，一棵樹有根結點和m個子樹構成，若把樹的根結點刪除，則樹變成了包含m棵樹的森林。當然，根據(jù)定義，一棵樹也可以稱為森林。二叉樹及其性質PART2二叉樹(BinaryTree)的基本概念定義：一棵二叉樹是n(n

0)個結點的一個有限集合，該集合或者為空（稱為空二叉樹），或者是由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。621754389101112完全二叉樹621754389101113141512滿二叉樹2154367一般二叉樹2154367二叉樹的特點每個結點最多有兩棵子樹，所以二叉樹中不存在度大于2的結點左子樹和右子樹是有順序的，次序不能任意顛倒即使樹中某結點只有一棵子樹，也要區(qū)分它是左子樹還是右子樹二叉樹的形態(tài)只有根的二叉樹空二叉樹L有根且有一個左子樹R有根且有一個右子樹LR有根且左右子樹均有思考題：畫出3個節(jié)點的二叉樹的所有形態(tài)性質1：在二叉樹的第i層上至多有2i－1個結點。二叉樹的性質證明：[證明用歸納法]—略設：深度為10的二叉樹，問：第6層上最多有多少節(jié)點？第6層上最少有多少結點？第10層上最多有多少節(jié)點？第10層上最少有多少結點？問：第i層上結點數(shù)什么時候可以達到最大？——1個結點——32個結點(25)——512個結點(29)——1個結點答：i層之前每一層都達到了結點數(shù)的最大個數(shù)性質2深度為k的二叉樹至多有2k-1個結點(k

1)。二叉樹的性質設：深度為6的二叉樹，問：這棵二叉樹最少有多少結點？這棵二叉樹最多有多少結點？設：深度為10的二叉樹，問：這棵二叉樹最少有多少結點？這棵二叉樹最多有多少結點？——6個結點——63個結點(26-1)——1023個結點(210-1)——10個結點性質3對任何一棵二叉樹T,如果其葉結點數(shù)為n0,度為2的結點數(shù)為n2,則n0＝n2＋1.二叉樹的性質2154367216543621754389101113141512n0=4n2=3n0=8n2=7n0=3n2=2定義1

滿二叉樹(FullBinaryTree)

一棵深度為k且有2k-1個結點的二叉樹稱為滿二叉樹。兩種特殊形態(tài)的二叉樹滿二叉樹62175438910111314151262175432131定義2完全二叉樹(CompleteBinaryTree)

深度為k，有n個結點的二叉樹當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時，稱為完全二叉樹滿二叉樹891011121314154123567缺3個結點的完全二叉樹89101112412356789104123567缺5個結點的完全二叉樹

換一種描述：若設二叉樹的高度為h，則共有h層。除第h層外，其它各層(0h-1)的結點數(shù)都達到最大個數(shù)，第h層從右向左連續(xù)缺若干結點，這就是完全二叉樹。定義2完全二叉樹(CompleteBinaryTree)完全二叉樹891011124123567非完全二叉樹891011124123567216543非完全二叉樹2154367非完全二叉樹結論：

滿二叉樹一定是一個完全二叉樹完全二叉樹不一定是滿二叉樹891011121314154123567問：一個深度為4的完全二叉樹最少有多少結點？最多有多少結點？問：一個深度為k的完全二叉樹最少有多少結點？最多有多少結點？答：最少8個結點最多15個結點答：最少2k-1個結點最多2K-1個結點性質4具有n(n

0)個結點的完全二叉樹的深度為

log2(n)

＋1

891011121314154123567說明：

運算符代表向下取整，即取整數(shù)部分

問：有100個節(jié)點的完全二叉樹的深度是多少？性質5

如將一棵有n個結點的完全二叉樹自頂向下，同一層自左向右連續(xù)給結點編號1…n，則有以下關系：若i=1,則i無雙親若i>1,則i的雙親為

i/2

若2*i<=n,則i的左孩子結點編號為2*i，若2*i+1<=n,則i的右孩子結點編號為2*i+1891011124123567假設：一棵有500個結點的完全二叉樹，則，210號結點的雙親結點編號是多少？左孩子結點編號分別是多少？右孩子結點編號分別是多少？再問：如果要求201、250號和300號結點的雙親和左右孩子呢？——105——420——421拓展問題：有n個結點的完全二叉樹中有多少個葉子結點（n0）、單孩子結點（n1），雙孩子結點（n2）？891011124123567當n=12時：n0=？n1=？n2=？當n=500時：n0=？n1=？n2=？當n=501時：n0=？n1=？n2=？615n0=n-

n/2

2502491二叉樹的存儲結構PART3完全二叉樹的順序表示二叉樹的存儲結構12489105637順序表示法：利用完全二叉樹的性質，存放到連續(xù)地址空間中123456789101234^5678^^^^91091235647810一般二叉樹的順序表示12345678910123456789101112131415二叉樹的鏈式存儲結構ABCDFE二叉鏈表lchildrchilddatatypedefcharTreeData;//結點數(shù)據(jù)類型typedefstructnode //結點定義{

TreeDatadata;structnode*lchild,*rchild;}BinTreeNode;typedefBinTreeNode*BinTree;//根指針

ABCDFEroot二叉鏈表ABCDFE三叉鏈表二叉樹的鏈式存儲結構lchildparentdatarchild三叉鏈表

ABCDFEroottypedefcharTreeData;//結點數(shù)據(jù)類型typedefstructnode //結點定義{

TreeDatadata;structnode*lchild,*rchild，*parent;}BinTreeNode;typedefBinTreeNode*BinTree;//根指針

二叉樹的基本算法PART3

二叉樹的基本算法（基于二叉鏈表）遍歷算法建立算法查詢算法刪除算法二叉樹的算法是以二叉樹的定義和遍歷操作為基礎的二叉樹遍歷二叉樹的遍歷：就是按某種次序訪問二叉樹中的結點，要求每個結點訪問一次且僅訪問一次。

91235647810設根結點為V，左子樹記作L，右子樹記作RLR則可能的遍歷次序有：前序：VLR

中序：LVR

后序：LRV

VRLRVLRLV

若規(guī)定先左后右遍歷下列二叉樹91235647810LR先序遍歷：1-L-R其中L：2-Lm-空其中Lm：4-7-8R：3-5-Rm其中Rm：6-9-10Lm后序：Rm先序序列：12478356910同理中序：74821539610784259106312146850937先序：ABEFCDG中序：EFBCGDA后序：FEGDCBA先序：ABHFDECKG中序：HBDFAEKCG后序：HDFBKGCEA先序：5031249768中序：0123456789后序：2143068795二叉樹遍歷練習二叉樹先序遍歷算法的定義：若二叉樹非空，則：訪問根結點(V)；前序遍歷左子樹(L)；前序遍歷右子樹(R)。先序遍歷算法(PreorderTraversal)先序遍歷算法描述:PreOrder(BinTreeNode*T){if(T!=NULL){printf(“%d”,T->data);PreOrder(T->lChild);PreOrder(T->rChild);}}二叉樹中序遍歷算法的定義：若二叉樹非空，則：中序遍歷左子樹(L)；訪問根結點(V)；中序遍歷右子樹(R)。中序遍歷算法(PreorderTraversal)中序遍歷算法描述:InOrder(BinTreeNode*T){if(T!=NULL){InOrder(T->lChild);printf(“%d”,T->data);InOrder(T->rChild);}}二叉樹后序遍歷算法的定義：若二叉樹非空，則：后序遍歷左子樹(L)；后序遍歷右子樹(R)。訪問根結點(V)；后序遍歷算法(PreorderTraversal)后序遍歷算法描述:PostOrder(BinTreeNode*T){if(T!=NULL){PostOrder(T->lChild);PostOrder(T->rChild);printf(“%d”,T->data);}}--/+*abcdef后序遍歷結果abcd-*+ef/-中序遍歷結果a+b*c-d-e/f先序遍歷結果-+a*b-cd/ef二叉樹遍歷的應用（先序建立二叉樹）先建樹根再建左子樹再建右子樹按先序遍歷的原則建立二叉樹1123說明：當前結點為空的時候，也必須告訴算法，要建一個空的二叉樹，因此可以用輸入特殊值代表該結點為空的方式來處理。輸入：1空空輸入：12空空3空空輸入序列為ABC@@DE@G@@F@@@ABCDEGF@@@@@@@@說明：輸入結點值的順序必須對應二叉樹結點前序遍歷的順序。并約定以輸入序列中不可能出現(xiàn)的值作為空結點的值以結束遞歸。例如用“@”表示字符序列或正整數(shù)序列空結點。

voidCrtBinTree(BinTreeNode&T){TreeDatax;scanf("%d",&x);//讀入根結點的值

if(x==0) T=nil;else{T=(BinTreeNode*)malloc(sizeof(BinTreeNode));

T->data=x;//建立根結點CrtBinTree(T->lChild);CrtBinTree(T->rChild);}}//先序建立二叉樹的子程序

建立二叉樹的主程序main(){bintreebt1;crtbintree(bt1);inorder(bt1);}

說明：先序遍歷建立二叉樹一般用在二叉樹結構固定的情況下思考題：能否用中序或后序的方法建立二叉樹？intCount(BinTreeNode*T){if(T==nil)return0;elsereturn1+Count(T->lChild)+Count(T->rChild);}計算二叉樹結點個數(shù)(遞歸算法)算法思路：若：二叉樹如果為空，則：結點個數(shù)為0否則：至少有一個根結點，再加上左子樹和右子樹的結點個數(shù)之和。問題：用三個遍歷算法能實現(xiàn)嗎？intLeaf_Count(BitreeT){if(T==nil)return0;//空樹沒有葉子elseif(T->lchild==nil&&T->rchild==nil)return1;//葉子結點

elsereturnLeaf_Count(T->lchild)+Leaf_Count(T->rchild);

//左子樹的葉子數(shù)加上右子樹的葉子數(shù)

}求二叉樹中葉子結點的個數(shù)算法思路：若：二叉樹為空，則：葉子數(shù)為0否則，若根是葉子，則：葉子樹是1，否則：葉子數(shù)是左子樹和右子樹的葉子數(shù)之和。判斷葉子的條件：左右孩子為空intHeight(BinTreeNode*T){if(T==NULL)return0;else { intm=Height(T->lChild); intn=Height(T->rChild)); return(m>n)?m+1:n+1;}}求二叉樹的高度(遞歸算法)算法思路：若：二叉樹為空，則：高度為0否則：至少有一層，再加上左子樹和右子樹中高度的最大值。復制二叉樹(遞歸算法)*BinTreeNodeCopy(BinTreeNode*T){ if(T==nil)returnnil; BinTreeNode*temp=newBinTreeNode; Temp->data=T->data; Temp->lchild=Copy(T->lchild); Temp->rchild=Copy(T->rchild); returntemp;}思考題：能否用中序或后序的方法判斷二叉樹等價(遞歸算法)intEqual(BinTreeNode*a,BinTreeNode*b){if(a==NULL&&b==NULL)return1;if(a!==NULL&&b!==NULL &&a->data==b->data &&equal(a->lChild,b->lChild) &&equal(a->rChild,b->rChild)) return1;return0;//如果a和b的子樹不等同，則函數(shù)返回0}思考題：能否用中序或后序的方法

Void destroy(BinTreeNode*t){if(t!=nil){destroy(t->lChild); destroy(t->rChild); free(t);}}刪除根為t的二叉樹思考題：能否用先序或中序的方法算法思路：若：二叉樹不為空，則：應該先刪除二叉樹的左右子樹，最后再刪除根節(jié)點。BinTreeNode*Find(BinTreeNode*T,intx）{

if(T==nil)returnnil;if(T->data==x) returnT;//找到

elseif((p=Find(T->lchild,x))!=nil)returnp; //在左子樹中找

elsereturnFind(T->rchild,x);//在右子樹中找}在二叉樹中查找元素值等于x的結點BinTreeNode*Parent(BinTreeNode*T,intx）

{//找當前結點的雙親結點，并返回

if(T==nil)returnnil;if(T->lchild->data==x||T->rchild->data==x) returnT;//找到

elseif((p=Parent(T->lchild,x))!=nil)returnp; //在左子樹中找

elsereturnParent(T->rchild,x);//在右子樹中找}在二叉樹中查找元素值等于x的結點的雙親結點交換二叉樹各結點的左、右子樹voidunknown(BinTreeNode*T){BinTreeNode*p=T,*temp;if(p!=nil){temp=T->leftChild;T->leftChild=T->rightChild;T->rightChild=temp;unknown(T->leftChild);unknown(T->rightChild);}}思考題：能否用先序或中序的方法612345789612375849二叉樹的確定例如：先序排列為：123456789我們可以用這個序列構造出不同的二叉樹結論：某個二叉樹的一個遍歷序列，不能唯一確定這棵二叉樹

例如,先序序列為{1,2,3}，可得5種不同的二叉樹123123123123123設給定后序序列{3，2，1}后，任然有4種二叉樹對應√√×√√結論：根據(jù)某二叉樹的先序和后序序列，不能唯一確定這棵二叉樹

例如,先序序列為{1,2,3}，可得5種不同的二叉樹123123123123123中序321

231

213

132

123經(jīng)證明：根據(jù)某二叉樹中序以及先序和后序中的一個序列，就能唯一確定這棵二叉樹二叉樹的確定由二叉樹的先序和中序序列或后序和中序序列可唯一地確定一棵二叉樹。

例：先序序列：ABHFDECKG

和中序序列：HBDFAEKCGAEBHFDCKGAEKCGBHFDKCGAEBHFDAEBHFDCKGAEKCGBHDFAHBDFEKCG前序序列:ABHFDECKG中序序列:HBDFAEKCG,則構造過程如下：

二叉排序樹定義：一棵空樹，或者是具有下列性質的二叉樹：（1）若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；（2）若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；（3）左、右子樹也分別為二叉排序樹；567030254236807590先序：56,30,25,42,36,70,80,75,90后序：25,36,42,30,75,90,80,70,56中序：25,30,36,42,56,70,75,80,90特點：對二叉排序樹進行中序遍歷可得到有序序列5030802090108540352523887066二叉排序樹的構建過程：567030254236807590如輸入順序是：56,30,42,70,25,80,36,75,90先序：56,30,25,42,36,70,80,75,90后序：25,36,42,30,75,90,80,70,56中序：25,30,36,42,56,70,75,80,90由關鍵字序列3，1，2，5，4構造而得的二叉排序樹：

→由關鍵字序列1，2，3，4，5構造而得的二叉排序樹：→同一組數(shù)據(jù)，輸入順序不同，構造的二叉排序樹不同，查找效率也不同2134535412ASL=(1+2+3+4+5)/5=3ASL=(1+2+3+2+3)/5=2.2BinTreeInsertBST(BinTreeT,inte)//建立過程就是不斷將新數(shù)據(jù){BinTreep;//插入到二叉排序樹的過程if(T==nil)//空樹的時候將本元素作為根結點{T=(BinTreeNode*)malloc(sizeof(BinTreeNode));T->data=e;T->lchild=T->rchild=nil;}elseif(e<T->data)T->lchild=InsertBST(T->lchild,e);elseif(e>T->data)T->rchild=InsertBST(T->rchild,e);returnT;}二叉排序樹的插入算法：一個無序序列可以通過構造一棵二叉排序樹而變成一個有序序列每次插入的新結點都是二叉排序樹上新的葉子結點插入時不必移動其它結點，僅需修改某個結點的指針樹和森林PART5樹與森林ACFEBDG雙親表示法順序表示法。孩子兄弟表示法左孩子右兄弟，即鏈表表示法樹的存儲結構0102ACFEBDG0123456ABCDEFG-1000113dataparent注意：結點A是根結點，所以其雙親是-1樹與森林：樹的存儲結構01雙親表示法用一組連續(xù)空間存儲樹的結點，同時在結點中附設一個指針，存放雙親結點在表中的位置用雙親表示實現(xiàn)的樹定義#defineMaxSize 100//最大結點個數(shù)typedefcharTreeData;//結點數(shù)據(jù)typedefstruct{//樹結點定義

TreeDatadata;intparent;}TreeNode;TreeNodeTree[MaxSize];//樹樹與森林：樹的存儲結構第一種方案：用和樹的度等數(shù)量的鏈域

data

child1child2child3childdABCDEFG

空鏈域：n(d-1)+1個ACFEBDG樹與森林：樹的存儲結構02樹的鏈式存儲結構結點結構

datafirstChildnextSiblingABCDEFG第二種方案：樹的左子女-右兄弟表示（二叉鏈表表示）BCDGFE

A

空鏈域：n+1個樹與森林：樹的存儲結構（鏈式存儲）typedefcharTreeData;typedefstructnode{TreeDatadata;structnode*firstChild,*nextSibling;}TreeNode;typedefTreeNode*Tree;用左子女-右兄弟表示實現(xiàn)的樹定義樹與森林：樹的存儲結構（孩子兄弟表示法）樹和二叉樹的轉換：利用孩子兄弟表示法ABDCEGFABCDEFG樹與森林：樹和二叉樹的轉換T1T2T3BCDGIJEKAFHT2FG3棵樹的森林各棵樹的二叉樹表示森林的二叉樹表示ABDCET1

HIKJT3樹和二叉樹的轉換：利用孩子兄弟表示法樹與森林：樹和二叉樹的轉換樹的遍歷樹與森林02廣度優(yōu)先遍歷按層遍歷01深度優(yōu)先遍歷先跟次序遍歷后跟次序遍歷樹的先根次序遍歷結論：樹的先根遍歷可以借助對應二叉樹的前序遍歷算法實現(xiàn)ACFEBDGABDCEGF算法描述：當樹非空時訪問根結點依次先根遍歷根的各棵子樹樹先根遍歷結果：ABEFCDG對應二叉樹前序遍歷結果：ABEFCDG結果相同樹與森林：深度優(yōu)先遍歷結論：樹的后根遍歷可以借助對應二叉樹的中序遍歷算法實現(xiàn)ACFEBDGABDCEGF算法描述：當樹非空時：（1）依次后根遍歷根的各棵子樹（2）訪問根結點樹后根遍歷結果：EFBCGDA對應二叉樹中序遍歷結果：EFBCGDA結果相同樹的后根次序遍歷樹與森林：深度優(yōu)先遍歷廣度優(yōu)先遍歷——按層遍歷ACFEBDG廣度優(yōu)先遍歷結果：ABCDEFG樹與森林哈夫曼樹及其應用PART6二叉樹的應用—哈夫曼樹路徑長度(PathLength)

兩個結點之間的路徑長度PL是連接兩結點的路徑上的分支數(shù)。樹的外部路徑長度是各葉結點(外結點)到根結點的路徑長度之和EPL?！攸c樹的內部路徑長度是各非葉結點(內結點)到根結點的路徑長度之和IPL。樹的路徑長度PL=EPL+IPL123645781234567812364578樹的外部路徑長度EPL=2*3+3*1=9樹的外部路徑長度EPL=1*1+2*1+3*1+4*1=10二叉樹的應用—哈夫曼樹帶權路徑長度(WeightedPathLength,WPL) 二叉樹的帶權(外部)路徑長度是樹的各葉子結點所帶的權值

wi與該結點到根的路徑長度

li的乘積的和?；舴蚵鼧鋷嗦窂介L度達到最小的二叉樹即為霍夫曼樹。在霍夫曼樹中，權值越大的結點離根越近。二叉樹的應用—哈夫曼樹WPL=2*2+4*2+5*2+7*2=36245747257254帶權路徑長度最小,是霍夫曼樹WPL=2*1+4*2+5*3+7*3=46WPL=7*1+5*2+2*3+4*3=35二叉樹的應用—哈夫曼樹1.由給定的n個權值{w0