計(jì)算機(jī)軟件基礎(chǔ)課件：樹和二叉樹

樹和二叉樹BasicsofComputerSoftware答辯人：XXX

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

0)個(gè)結(jié)點(diǎn)的有限集合。

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

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

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

15、與無序樹對應(yīng)，有序樹(OrderedTree)是指樹中任意一個(gè)結(jié)點(diǎn)的各孩子結(jié)點(diǎn)有嚴(yán)格排列次序的樹。二叉樹是有序樹，因?yàn)槎鏄渲忻總€(gè)孩子結(jié)點(diǎn)都確切定義為是該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)還是右孩子結(jié)點(diǎn)。

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

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

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

滿二叉樹(FullBinaryTree)

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

深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號從1至n的結(jié)點(diǎn)一一對應(yīng)時(shí)，稱為完全二叉樹滿二叉樹891011121314154123567缺3個(gè)結(jié)點(diǎn)的完全二叉樹89101112412356789104123567缺5個(gè)結(jié)點(diǎn)的完全二叉樹

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

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

0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度為

log2(n)

＋1

891011121314154123567說明：

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

問：有100個(gè)節(jié)點(diǎn)的完全二叉樹的深度是多少？性質(zhì)5

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

i/2

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

n/2

2502491二叉樹的存儲結(jié)構(gòu)PART3完全二叉樹的順序表示二叉樹的存儲結(jié)構(gòu)12489105637順序表示法：利用完全二叉樹的性質(zhì)，存放到連續(xù)地址空間中123456789101234^5678^^^^91091235647810一般二叉樹的順序表示12345678910123456789101112131415二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)ABCDFE二叉鏈表lchildrchilddatatypedefcharTreeData;//結(jié)點(diǎn)數(shù)據(jù)類型typedefstructnode //結(jié)點(diǎn)定義{

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

ABCDFEroot二叉鏈表ABCDFE三叉鏈表二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)lchildparentdatarchild三叉鏈表

ABCDFEroottypedefcharTreeData;//結(jié)點(diǎn)數(shù)據(jù)類型typedefstructnode //結(jié)點(diǎn)定義{

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

二叉樹的基本算法PART3

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

91235647810設(shè)根結(jié)點(diǎn)為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二叉樹遍歷練習(xí)二叉樹先序遍歷算法的定義：若二叉樹非空，則：訪問根結(jié)點(diǎn)(V)；前序遍歷左子樹(L)；前序遍歷右子樹(R)。先序遍歷算法(PreorderTraversal)先序遍歷算法描述:PreOrder(BinTreeNode*T){if(T!=NULL){printf(“%d”,T->data);PreOrder(T->lChild);PreOrder(T->rChild);}}二叉樹中序遍歷算法的定義：若二叉樹非空，則：中序遍歷左子樹(L)；訪問根結(jié)點(diǎn)(V)；中序遍歷右子樹(R)。中序遍歷算法(PreorderTraversal)中序遍歷算法描述:InOrder(BinTreeNode*T){if(T!=NULL){InOrder(T->lChild);printf(“%d”,T->data);InOrder(T->rChild);}}二叉樹后序遍歷算法的定義：若二叉樹非空，則：后序遍歷左子樹(L)；后序遍歷右子樹(R)。訪問根結(jié)點(diǎn)(V)；后序遍歷算法(PreorderTraversal)后序遍歷算法描述:PostOrder(BinTreeNode*T){if(T!=NULL){PostOrder(T->lChild);PostOrder(T->rChild);printf(“%d”,T->data);}}--/+*abcdef后序遍歷結(jié)果abcd-*+ef/-中序遍歷結(jié)果a+b*c-d-e/f先序遍歷結(jié)果-+a*b-cd/ef二叉樹遍歷的應(yīng)用（先序建立二叉樹）先建樹根再建左子樹再建右子樹按先序遍歷的原則建立二叉樹1123說明：當(dāng)前結(jié)點(diǎn)為空的時(shí)候，也必須告訴算法，要建一個(gè)空的二叉樹，因此可以用輸入特殊值代表該結(jié)點(diǎn)為空的方式來處理。輸入：1空空輸入：12空空3空空輸入序列為ABC@@DE@G@@F@@@ABCDEGF@@@@@@@@說明：輸入結(jié)點(diǎn)值的順序必須對應(yīng)二叉樹結(jié)點(diǎn)前序遍歷的順序。并約定以輸入序列中不可能出現(xiàn)的值作為空結(jié)點(diǎn)的值以結(jié)束遞歸。例如用“@”表示字符序列或正整數(shù)序列空結(jié)點(diǎn)。

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

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

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

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

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

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

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

}求二叉樹中葉子結(jié)點(diǎn)的個(gè)數(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否則：至少有一層，再加上左子樹和右子樹中高度的最大值。復(fù)制二叉樹(遞歸算法)*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;}思考題：能否用中序或后序的方法判斷二叉樹等價(jià)(遞歸算法)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的二叉樹思考題：能否用先序或中序的方法算法思路：若：二叉樹不為空，則：應(yīng)該先刪除二叉樹的左右子樹，最后再刪除根節(jié)點(diǎn)。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的結(jié)點(diǎn)BinTreeNode*Parent(BinTreeNode*T,intx）

{//找當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)，并返回

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的結(jié)點(diǎn)的雙親結(jié)點(diǎn)交換二叉樹各結(jié)點(diǎn)的左、右子樹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我們可以用這個(gè)序列構(gòu)造出不同的二叉樹結(jié)論：某個(gè)二叉樹的一個(gè)遍歷序列，不能唯一確定這棵二叉樹

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

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

231

213

132

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

例：先序序列：ABHFDECKG

和中序序列：HBDFAEKCGAEBHFDCKGAEKCGBHFDKCGAEBHFDAEBHFDCKGAEKCGBHDFAHBDFEKCG前序序列:ABHFDECKG中序序列:HBDFAEKCG,則構(gòu)造過程如下：

二叉排序樹定義：一棵空樹，或者是具有下列性質(zhì)的二叉樹：（1）若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；（2）若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；（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特點(diǎn)：對二叉排序樹進(jìn)行中序遍歷可得到有序序列5030802090108540352523887066二叉排序樹的構(gòu)建過程：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由關(guān)鍵字序列3，1，2，5，4構(gòu)造而得的二叉排序樹：

→由關(guān)鍵字序列1，2，3，4，5構(gòu)造而得的二叉排序樹：→同一組數(shù)據(jù)，輸入順序不同，構(gòu)造的二叉排序樹不同，查找效率也不同2134535412ASL=(1+2+3+4+5)/5=3ASL=(1+2+3+2+3)/5=2.2BinTreeInsertBST(BinTreeT,inte)//建立過程就是不斷將新數(shù)據(jù){BinTreep;//插入到二叉排序樹的過程if(T==nil)//空樹的時(shí)候?qū)⒈驹刈鳛楦Y(jié)點(diǎn){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;}二叉排序樹的插入算法：一個(gè)無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個(gè)有序序列每次插入的新結(jié)點(diǎn)都是二叉排序樹上新的葉子結(jié)點(diǎn)插入時(shí)不必移動其它結(jié)點(diǎn)，僅需修改某個(gè)結(jié)點(diǎn)的指針樹和森林PART5樹與森林ACFEBDG雙親表示法順序表示法。孩子兄弟表示法左孩子右兄弟，即鏈表表示法樹的存儲結(jié)構(gòu)0102ACFEBDG0123456ABCDEFG-1000113dataparent注意：結(jié)點(diǎn)A是根結(jié)點(diǎn)，所以其雙親是-1樹與森林：樹的存儲結(jié)構(gòu)01雙親表示法用一組連續(xù)空間存儲樹的結(jié)點(diǎn)，同時(shí)在結(jié)點(diǎn)中附設(shè)一個(gè)指針，存放雙親結(jié)點(diǎn)在表中的位置用雙親表示實(shí)現(xiàn)的樹定義#defineMaxSize 100//最大結(jié)點(diǎn)個(gè)數(shù)typedefcharTreeData;//結(jié)點(diǎn)數(shù)據(jù)typedefstruct{//樹結(jié)點(diǎn)定義

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

data

child1child2child3childdABCDEFG

空鏈域：n(d-1)+1個(gè)ACFEBDG樹與森林：樹的存儲結(jié)構(gòu)02樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)

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

A

空鏈域：n+1個(gè)樹與森林：樹的存儲結(jié)構(gòu)（鏈?zhǔn)酱鎯Γ﹖ypedefcharTreeData;typedefstructnode{TreeDatadata;structnode*firstChild,*nextSibling;}TreeNode;typedefTreeNode*Tree;用左子女-右兄弟表示實(shí)現(xiàn)的樹定義樹與森林：樹的存儲結(jié)構(gòu)（孩子兄弟表示法）樹和二叉樹的轉(zhuǎn)換：利用孩子兄弟表示法ABDCEGFABCDEFG樹與森林：樹和二叉樹的轉(zhuǎn)換T1T2T3BCDGIJEKAFHT2FG3棵樹的森林各棵樹的二叉樹表示森林的二叉樹表示ABDCET1

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

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

wi與該結(jié)點(diǎn)到根的路徑長度

li的乘積的和?；舴蚵鼧鋷?quán)路徑長度達(dá)到最小的二叉樹即為霍夫曼樹。在霍夫曼樹中，權(quán)值越大的結(jié)點(diǎn)離根越近。二叉樹的應(yīng)用—哈夫曼樹WPL=2*2+4*2+5*2+7*2=36245747257254帶權(quán)路徑長度最小,是霍夫曼樹WPL=2*1+4*2+5*3+7*3=46WPL=7*1+5*2+2*3+4*3=35二叉樹的應(yīng)用—哈夫曼樹1.由給定的n個(gè)權(quán)值{w0