數(shù)據(jù)結構-樹和二叉樹課件

二叉樹三．二叉樹存貯結構

1二叉樹的順序結構

二叉樹的順序存儲結構就是用一維數(shù)組存儲二叉樹中的結點，并且結點的存儲位置（下標）應能體現(xiàn)結點之間的邏輯關系——父子關系。

如何利用數(shù)組下標來反映結點之間的邏輯關系?完全二叉樹和滿二叉樹中結點的序號可以唯一地反映出結點之間的邏輯關系。6.2二叉樹三．二叉樹存貯結構

1二叉樹的346.2

二叉樹完全二叉樹的順序存儲CDEFGHIJ以編號為下標ABCDEFGHIJ數(shù)組下標123456789106.2二叉樹完全二叉樹的順序存儲2

二叉樹二叉樹的順序存儲ABCDFGE按照完全二叉樹編號ABCDFGE123561013ABC∧DE∧∧∧F∧∧G數(shù)組下標12345678910111213以編號為下標6.2二叉樹二叉樹的順序存儲ABCDFGE按照完全366.2

二叉樹二叉樹的順序存儲結構一般僅存儲完全二叉樹和滿二叉樹。6.2二叉樹二叉樹的順序存儲結構一376.2

二叉樹2二叉樹的鏈式存儲結構 1）基本思想：令二叉樹的每個結點對應一個鏈表結點，鏈表結點除了存放與二叉樹結點有關的數(shù)據(jù)信息外，還要設置指示左右孩子的指針。

結點結構：lchilddatarchild其中，data：數(shù)據(jù)域，存放該結點的數(shù)據(jù)信息；lchild：左指針域，存放指向左孩子的指針；rchild：右指針域，存放指向右孩子的指針。

6.2二叉樹2二叉樹的鏈式存儲結構 1）基本386.2

二叉樹二叉樹的二叉鏈表存儲表示：TypedefstructBiNode{TElemTypedata;structBiNode*lchild,*rchild;//左右孩子指針}BiNode,*BiTree;6.2二叉樹二叉樹的二叉鏈表存儲表示：396.2

二叉樹

2）二叉鏈表二叉鏈表中每個結點至少包含三個域：數(shù)據(jù)域、左指針域、右指針域

ABCDEFGGFEDBA∧∧∧∧∧∧∧∧C在n個結點的二叉樹中，有n+1個空鏈域。6.2二叉樹2）二叉鏈表ABCDEFGGFED406.2

二叉樹3）三叉鏈表三叉鏈表中每個結點至少包含四個域：數(shù)據(jù)域、雙親指針域、左指針域、右指針域結點結構：lchilddataparent其中，data：數(shù)據(jù)域，存放該結點的數(shù)據(jù)信息；parent:雙親指針域，存放指向指向雙親節(jié)點的指針；lchild：左指針域，存放指向左孩子的指針；rchild：右指針域，存放指向右孩子的指針。

rchild6.2二叉樹3）三叉鏈表結點結構：lchild416.2

二叉樹ABCDEFGA∧B∧D∧E∧F∧CG∧∧∧∧6.2二叉樹ABCDEFGA∧B∧D∧E∧F∧CG42第六章樹和二叉樹

6.3二叉樹的遍歷一.二叉樹的遍歷方法二.遍歷的遞歸算法第六章樹和二叉樹6.3二叉樹的遍歷436.3二叉樹的遍歷一、二叉樹的遍歷方法

二叉樹的遍歷是指從根結點出發(fā)，按照某種次序訪問二叉樹中的所有結點，使得每個結點被訪問一次且僅被訪問一次。二叉樹遍歷操作的結果？非線性結構線性化抽象操作，可以是對結點進行的各種處理，這里簡化為輸出結點的數(shù)據(jù)。前序遍歷中序遍歷后序遍歷層序遍歷

對于線性結構由于每個結點只有一個直接后繼，遍歷是很容易的事。

二叉樹是非線性結構，每個結點可能有兩個后繼，如何訪問二叉樹的每個結點，而且每個結點僅被訪問一次？6.3二叉樹的遍歷一、二叉樹的遍歷方法二44二叉樹的遍歷方式：DLR、LDR、LRD、DRL、RDL、RLD

如果限定先左后右，則二叉樹遍歷方式有三種：前序：DLR中序：LDR后序：LRD層序遍歷：按二叉樹的層序編號的次序訪問各結點。

考慮二叉樹的組成：根結點D左子樹L右子樹R二叉樹6.3二叉樹的遍歷二叉樹的遍歷方式：如果限定先左后右，則二叉樹遍歷方式有三種：451、先序（根）遍歷若二叉樹為空，則空操作返回；否則：①訪問根結點；②先序遍歷根結點的左子樹；③先序遍歷根結點的右子樹。先序遍歷序列：ABDGCEFABCDEFG6.3二叉樹的遍歷1、先序（根）遍歷先序遍歷序列：ABDGCEFA466.3二叉樹的遍歷2、中序（根）遍歷若二叉樹為空，則空操作返回；否則：①中序遍歷根結點的左子樹；②訪問根結點；③中序遍歷根結點的右子樹。

中序遍歷序列：DGBAECFABCDEFG6.3二叉樹的遍歷2、中序（根）遍歷中序遍歷序列：DG476.3二叉樹的遍歷3、后序（根）遍歷若二叉樹為空，則空操作返回；否則：①后序遍歷根結點的左子樹；②后序遍歷根結點的右子樹；③訪問根結點。后序遍歷序列：GDBEFCAABCDEFG6.3二叉樹的遍歷3、后序（根）遍歷后序遍歷序列：GD484、層序遍歷二叉樹的層次遍歷是指從二叉樹的第一層（即根結點）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序對結點逐個訪問。

層序遍歷序列：ABCDEFGABCDEFG6.3二叉樹的遍歷4、層序遍歷層序遍歷序列：ABCDEFGABCD496.3二叉樹的遍歷ABCDEFGHK例如：先序序列：中序序列：后序序列：A

BCD

EFGHKBDC

A

EHGKFDCBHKGFE

A6.3二叉樹的遍歷ABCDEFGHK例如：先序序列：中序506.3二叉樹的遍歷二.遍歷的遞歸算法voidPreorder(BiTreeT,void(*visit)(TElemType&e)){//先序遍歷二叉樹

if(T!==NULL){

visit(T->data);//訪問結點

Preorder(T->lchild,visit);//遍歷左子樹

Preorder(T->rchild,visit);//遍歷右子樹}}先序遍歷遞歸算法6.3二叉樹的遍歷二.遍歷的遞歸算法voidPreo516.3二叉樹的遍歷二叉樹前序遍歷的非遞歸算法的關鍵：在前序遍歷過某結點的整個左子樹后，如何找到該結點的右子樹的根指針。解決辦法：在訪問完該結點后，將該結點的指針保存在棧中，以便以后能通過它找到該結點的右子樹。

先序遍歷——非遞歸算法6.3二叉樹的遍歷二叉樹前序遍歷的非遞歸算法的關鍵：在前52AGBCDFE先序遍歷算法的執(zhí)行軌跡ABDGCEFA棧內容BDGCEFAGBCDFE先序遍歷算法的執(zhí)行軌跡ABDGCEFA棧內容B531.棧s初始化；2.循環(huán)直到root為空或棧s為空2.1當root不空時循環(huán)2.1.1輸出root->data;（可將輸出變?yōu)槿魏翁幚恚?/p>

2.1.2將指針root的值保存到棧中；2.1.3繼續(xù)遍歷root的左子樹2.2如果棧s不空，則2.2.1將棧頂元素彈出至root；2.2.2準備遍歷root的右子樹；步驟：1.棧s初始化；步驟：546.3二叉樹的遍歷voidPreorder(BiTreeT,void(*visit)(TElemType&e)){InitStack(&S);p=T;while(p!==NULL||!StackEmpty(S)){if(p!==NULL){

visit(p->data);//訪問結點Push(&S,p);p=p->lchild}else{Pop(&S,&p);p=p->rchild}}先序遍歷非遞歸算法（偽代碼）6.3二叉樹的遍歷voidPreorder(BiTr556.3二叉樹的遍歷2中序遍歷遞歸算法voidInorder(BiTreeT,void(*visit)(TElemType&e)){//中序遍歷二叉樹

if(T!==NULL){Preorder(T->lchild,visit);//遍歷左子樹

visit(T->data);//訪問結點

Preorder(T->rchild,visit);//遍歷右子樹}}6.3二叉樹的遍歷2中序遍歷遞歸算法voidIno566.3二叉樹的遍歷中序遍歷非遞歸算法：voidInorder(BiTreeT,void(*visit)(TElemType&e)){InitStack(&S);p=T;while(p!==NULL||!StackEmpty(S)){if(p!==NULL){Push(&S,p);p=p->lchild}else{Pop(&S,&p);

visit(T->data);//訪問結點p=p->rchild}}6.3二叉樹的遍歷中序遍歷非遞歸算法：voidInor576.3二叉樹的遍歷3后序遍歷遞歸算法voidPostorder(BiTreeT,void(*visit)(TElemType&e)){//后序遍歷二叉樹

if(T!==NULL){Preorder(T->lchild,visit);//遍歷左子樹Preorder(T->rchild,visit);//遍歷右子樹visit(T->data);//訪問結點}}6.3二叉樹的遍歷3后序遍歷遞歸算法voidPos58若已知一棵二叉樹的前序序列和中序序列，能否唯一確定這棵二叉樹呢？怎樣確定？

例如：已知一棵二叉樹的先序遍歷序列和中序遍歷序列分別為ABCDEFGHI和BCAEDGHFI，如何構造該二叉樹呢?

6.3二叉樹的遍歷若已知一棵二叉樹的前序序列和中序序列，能否唯一確定這棵二叉樹59先序：ABCDEFG

HI中序：BCAEDGHFI先序：BC中序：BC

BCDEFGHIA先序：DEFGHI中序：EDGHFIABCDEFGHI6.3二叉樹的遍歷先序：ABCDEFGHI先序：BCD60先序：FG

HI中序：GHFI先序：DEFGHI中序：EDGHFIABCDEFGHIABCDEFIGH6.3二叉樹的遍歷先序：FGHI先序：DEFGHIABCDE61第六章樹和二叉樹

6.4遍歷的應用1.二叉樹的基本應用2.建立二叉存儲鏈表

第六章樹和二叉樹6.4遍歷的應用626.4遍歷的應用遍歷二叉樹是二叉樹各種操作的基礎，遍歷算法中對每個結點的訪問操作可以是多種形式及多個操作，根據(jù)遍歷算法的框架，適當修改訪問操作的內容，可以派生出很多關于二叉樹的應用算法。6.4遍歷的應用遍歷二叉樹是二叉樹各種操作的基636.4遍歷的應用例1編寫求二叉樹的葉子結點個數(shù)的算法

輸入：二叉樹的二叉鏈表

結果：二叉樹的葉子結點個數(shù)基本思想：遍歷操作訪問二叉樹的每個結點，而且每個結點僅被訪問一次。所以可在二叉樹遍歷的過程中，統(tǒng)計葉子結點的個數(shù)。voidleaf(BiTreeT){//n計數(shù)二叉樹的葉子結點的個數(shù)，初值n=0if(T){

if(T->lchild==null&&T->rchild==null)n=n+1;

leaf(T->lchild);leaf(T->rchild);}//if}//leafABCDEFG6.4遍歷的應用例1編寫求二叉樹的葉子結點個數(shù)的64例2

求二叉樹的結點個數(shù)。

voidCount(BiNode*root)//n為全局量并已初始化為0{if(root){Count(root->lchild);

n++;Count(root->rchild);}}6.4遍歷的應用例2求二叉樹的結點個數(shù)。voidCount(BiNod65例3、求二叉樹的深度。

intDepth(BiNode*root){if(root==NULL)return0;else{hl=Depth(root->lchild);hr=Depth(root->rchild);

returnmax(hl,hr)+1;}}6.4遍歷的應用二叉樹的深度應為其左、右子樹深度的最大值加1。例3、求二叉樹的深度。intDepth(BiNode666.4遍歷的應用

例4為二叉樹建立二叉存儲鏈表輸入：二叉樹的先序序列結果：建立二叉樹的二叉存儲鏈表

按先序編歷的順序輸入先序序列（設每個元素是一個字符），建立二叉鏈表的所有結點并完成相應結點的鏈接。為了建立一棵二叉樹，將二叉樹中每個結點的空指針引出一個虛結點，其值為一特定值如“#”，以標識其為空，把這樣處理后的二叉樹稱為原二叉樹的擴展二叉樹。6.4遍歷的應用例4為二叉樹建立二叉存儲鏈表67擴展二叉樹的先序遍歷序列:AB#D##C##DBAC#DBAC####6.4遍歷的應用擴展二叉樹的先序遍歷序列:AB#D##C##686.4遍歷的應用StatusCreateBiTree(BiTree&T){//假設擴展二叉樹的先序遍歷序列由鍵盤輸入，T為指向根結點的指針scanf(&ch);if(ch==‘#’)T=NULL;//若ch==‘#’則T=NULL返回else{//若ch!=‘’

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;//建立（根）結點CreateBiTree(T->lchild);//構造左子樹，并將左子樹根結點指針//賦給（根）結點的左孩子域CreateBiTree(T->rchild);//構造右子樹，并將右子樹根結點指針//賦給（根）結點的右孩子域}returnOK;}//CreateBiTree6.4遍歷的應用StatusCreateBiTree69

小結1二叉樹：或為空樹，或由根及兩顆不相交的左子樹、右子樹構成，并且左、右子樹本身也是二叉樹；2二叉樹即可以用順序結構存儲，也可用鏈式結構存儲；3遍歷：按某種搜索路徑訪問二叉樹的每個結點，每個結點僅被訪問一次。二叉樹的遍歷可以分解為：訪問根，遍歷左子樹和遍歷右子樹，本課程介紹了三種遍歷算法：先序遍歷、中序遍歷、后序遍歷；

70第六章樹和二叉樹

6.5線索二叉樹

1.線索二叉樹的概念2線索鏈表3.*線索二叉樹的遍歷第六章樹和二叉樹6.5線索二叉樹716.5線索二叉樹一、線索二叉樹遍歷的目的：

將二叉樹中的結點按一定規(guī)律（先、中、后序）線性化的過程。問題：當以二叉鏈表作為存儲結構時，只能找到某結點的左、右孩子信息，不能得到結點在某種遍歷序列中的前驅和后繼信息。解決辦法：◆重新遍歷，在遍歷過程中得到前驅、后繼信息。但這種動態(tài)訪問浪費時間。◆充分利用二叉鏈表的空鏈域，將遍歷過程中結點的前驅、后繼信息保留下來。6.5線索二叉樹一、線索二叉樹遍歷的目的：問題：當以72ltaglchilddatarchildrtag0:lchild指向該結點的左孩子1:lchild指向該結點的前驅結點0:rchild指向該結點的右孩子1:rchild指向該結點的后繼結點ltag=rtag=結點結構6.5線索二叉樹線索：將二叉鏈表中的空指針域指向前驅結點和后繼結點的指針被稱為線索；線索化：使二叉鏈表中結點的空鏈域存放其前驅或后繼信息的過程稱為線索化；線索二叉樹：加上線索的二叉樹稱為線索二叉樹。ltaglchilddatarchildrtag73ABCDEFGABCDEFGABCDEFGABCDEFGABDGCEFDGBAECFGDBEFCANULLNULLNULLNULL先序中序后序ABCDEFGABCDEFGABCDEFGABCDEFGAB74ABCDEFGDGBAECFNULLNULL中序找前驅結點1、P↑Ltag=1,P↑Lchild為前驅2、“根”P的前驅結點是中序遍歷P的左子樹時訪問的最后一個結點找后繼結點1、P↑Rtag=1,P↑Rchild為后繼驅2、“根”P的后繼結點是其右子樹的“最左下端”的結點ABCDEFGDGBAECFNULLNULL中序找前驅結點找75A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧∧中序線索鏈表的建立過程已經(jīng)建立起二叉鏈表DGBAECFA頭指針BCDEFG∧∧∧∧∧∧0000000000000076A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧∧中序線索鏈表的建立過程中序遍歷二叉鏈表p為正在訪問的結點pre為剛訪問的結點p1DDGBAECFA頭指針BCDEFG∧∧∧∧∧∧0000000000000077A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧∧中序線索鏈表的建立過程中序遍歷二叉鏈表p為正在訪問的結點pre為剛訪問的結點pre1p1DGDGBAECFA頭指針BCDEFG∧∧∧∧∧∧0000000000000078A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧中序遍歷二叉鏈表p為正在訪問的結點pre為剛訪問的結點pre11p1中序線索鏈表的建立過程DGBDGBAECFA頭指針BCDEFG∧∧∧∧∧∧0000000000000079A頭指針BCDEFG∧∧∧∧∧∧00000000000000中序遍歷二叉鏈表p為正在訪問的結點pre為剛訪問的結點pre11p11中序線索鏈表的建立過程DGBADGBAECFA頭指針BCDEFG∧∧∧∧∧∧0000000000000080A頭指針BCDEFG∧∧∧∧∧00000000000000中序遍歷二叉鏈表p為正在訪問的結點pre為剛訪問的結點pre11p111中序線索鏈表的建立過程DGBAEDGBAECFA頭指針BCDEFG∧∧∧∧∧00000000000000中81A頭指針BCDEFG∧∧∧∧00000000000000中序遍歷二叉鏈表p為正在訪問的結點pre為剛訪問的結點pre11p1111中序線索鏈表的建立過程DGBAECDGBAECFA頭指針BCDEFG∧∧∧∧00000000000000中序82A頭指針BCDEFG∧∧∧00000000000000中序遍歷二叉鏈表p為正在訪問的結點pre為剛訪問的結點pre11p11111中序線索鏈表的建立過程DGBAECFDGBAECFA頭指針BCDEFG∧∧∧00000000000000中序遍83A頭指針BCDEFG∧∧00000000000000中序遍歷二叉鏈表p為正在訪問的結點pre為剛訪問的結點pre11111111中序線索鏈表的建立過程DGBAECFDGBAECFA頭指針BCDEFG∧∧00000000000000中序遍歷84第六章樹和二叉樹

6.6樹和森林一.樹的存儲結構二.樹和二叉樹的轉換三.

樹的遍歷四.森林

第六章樹和二叉樹6.6樹和森林856.6樹和森林

一．樹的存貯結構1、雙親表示法基本思想：用一維數(shù)組來存儲樹的各個結點（一般按層序存儲），數(shù)組中的一個元素對應樹中的一個結點，包括結點的數(shù)據(jù)信息以及該結點的雙親在數(shù)組中的下標。

data

parentdata：存儲樹中結點的數(shù)據(jù)信息parent：存儲該結點的雙親在數(shù)組中的下標6.6樹和森林一．樹的存貯結構基本思想：用一維數(shù)組來存866.6樹和森林#defineMAX_TREE_SIZE100typestructPTNode//結點結構{TEleTypedata;//數(shù)據(jù)域intparent;//雙親在數(shù)組中的下標}PTNode;Typedefstruct{//樹結構PTNodenodes[MAX_TREE_SIZE]intr,n//根的位置和結點數(shù)}PTree樹的雙親表示法實質上是一個靜態(tài)鏈表。6.6樹和森林#defineMAX_TREE_SIZE876.6樹和森林012345678

A-1B0C0D1E1F1G2H2I

4ACBHFEDGI找某一結點的雙親，按照該結點的雙親下表即可找到。但求某一結點的孩子，要遍歷整個結構。6.6樹和森林0A-1AC886.6樹和森林2、孩子表示法鏈表中的每個結點包括一個數(shù)據(jù)域和多個指針域，每個指針域指向該結點的一個孩子結點。方案一：指針域的個數(shù)等于樹的度datachild1child2……childd其中：data：數(shù)據(jù)域，存放該結點的數(shù)據(jù)信息；child1~childd：指針域，指向該結點的孩子。

6.6樹和森林2、孩子表示法鏈表中的每個896.6樹和森林∧缺點：浪費空間ACBHFEDGIA∧B∧C∧D∧E∧F∧G∧H∧I∧∧∧∧∧∧∧∧∧∧∧6.6樹和森林∧缺點：浪費空間ACBHFEDGIA∧B∧906.6樹和森林方案二：

指針域的個數(shù)等于該結點的度data

degree

child1

child2

……

childd其中：data：數(shù)據(jù)域，存放該結點的數(shù)據(jù)信息；degree：度域，存放該結點的度；child1~childd：指針域，指向該結點的孩子。

6.6樹和森林方案二：指針域的個數(shù)等于該結點的度da91缺點：結點結構不一致ACBHFEDGIA2B3C2E1I0G0H0F0D06.6樹和森林缺點：結點結構不一致ACBHFEDGIA2B3C926.6樹和森林方案三：將結點的所有孩子放在一起，構成線性表?；舅枷耄?/p>

把每個結點的孩子排列起來，看成是一個線性表，且以單鏈表存儲，則n個結點共有n個孩子鏈表。這n個單鏈表共有n個頭指針，這n個頭指針又組成了一個線性表，構成孩子鏈表的表頭數(shù)組。

6.6樹和森林方案三：將結點的所有孩子放在一起，構成線性93

6.6樹和森林childnext孩子結點typedefstructCTNode{intchild;structCTNode*next;};Typedefstruct{