2024年樹和二叉樹實驗報告

樹和二叉樹試驗報告課程數(shù)據(jù)結(jié)構(gòu)試驗名稱樹和二叉樹系別____計算機學(xué)院專業(yè)班級__軟件134_____姓名__徐雅欣____學(xué)號_00406134試驗日期：年6月7日試驗?zāi)繕?掌握二叉樹，二叉樹排序數(shù)的概念及存儲措施。掌握二叉樹的遍歷算法純熟掌握編寫實現(xiàn)樹的各種運算的算法試驗內(nèi)容（－）試驗題目一：建立一棵二叉樹并中序遍歷（填空）1.要點分析：中序遍歷的遍歷規(guī)則是（前中后），既先訪問左子樹，在訪問目前節(jié)點，最后訪問右子樹。2.程序源代碼：#include<stdio.h>#include<malloc.h>structnode{ chardata; structnode*lchild,*rchild;}bnode;typedefstructnode*blink;blinkadd(blinkbt,charch){ if(bt==NULL) { bt=(blink)malloc(sizeof(bnode)); bt->data=ch; bt->lchild=bt->rchild=NULL; } elseif(ch<bt->data) bt->lchild=add(bt->lchild,ch); else bt->rchild=add(bt->rchild,ch);returnbt;}voidinorder(blinkbt){ if(bt) { inorder(bt->lchild); printf("%2c",bt->data);inorder(bt->rchild); }}main(){ blinkroot=NULL; inti,n; charx; scanf("%d",&n); for(i=0;i<=n;i++) { x=getchar(); root=add(root,x); } inorder(root); printf("\n");}3.試驗成果：（二）試驗題目2：編寫程序，求二叉樹的節(jié)點數(shù)和葉子樹。1.要點分析：.定理：二叉樹假如有v0個葉子節(jié)點，那么就有v0-1個度為二的節(jié)點就是v0-1=v2

定理：二叉樹有N個節(jié)點N=v0+v1+v2即節(jié)點總數(shù)等于度為0，1，2的節(jié)點的和。2.程序源代碼：#include<stdio.h>

#include<malloc.h>

#defineERROR0

#defineOK1

#defineOVERFLOW-2

#defineTRUE1

typedefintStatus;

typedefcharTElemType;typedefstructBiTNode

{TElemTypedata;

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;

intcount=0;

StatusCreateBiTree(BiTree*T)

{

charch;

scanf("%c",&ch);

if(ch=='')(*T)=NULL;

else{

if(!((*T)=(BiTNode*)malloc(sizeof(BiTNode))))

exit(OVERFLOW);

(*T)->data=ch;

CreateBiTree(&((*T)->lchild));

CreateBiTree(&((*T)->rchild));

}

returnOK;

}

StatusCountleaf(BiTreeT)

{if(T)

{if((!T->lchild)&&(!T->rchild))count++;

Countleaf(T->lchild);

Countleaf(T->rchild);

}

returncount;

}

StatusDepth(BiTreeT)

{intdepthval,depthleft=0,depthright=0;

if(!T)depthval=0;

else

{depthleft=Depth(T->lchild);

depthright=Depth(T->rchild);

depthval=1+(depthleft>depthright?depthleft:depthright);

}

returndepthval;

}

StatusPreorder(BiTreeT)

{if(T)

{printf("%c",T->data);

Preorder(T->lchild);

Preorder(T->rchild);

}

}

StatusInOrderTraverse（BiTreeT，Status

（*Visit）（TElemTypee））{

StackS；InitStack（S）；p=T;

while(p=!StackEmpty（S）){

if

（p）{Push(S,p);p=p->lchild;}

else{Pop(S,p);if(!Visit(p->data))returnERROR;

p=p->rchild;

}

}

returnOK;

}

voidmain()

{BiTreeT;

printf("pleaseinputaTree:");

CreateBiTree(&T);

printf("theTreeis:");

Preorder(T);

printf("\n");

InOrderTraverse（T）；

printf("\n");

printf("thenumberofleavesis:");

printf("%d",Countleaf(T));

printf("\n");

printf("theDepthofthetreeis:");

printf("%d",Depth(T));

getch();

}3.試驗成果：（三）試驗題目3：編寫程序，實現(xiàn)按層次遍歷二叉樹。1.要點分析：定義：1、滿二叉樹：一棵深度為k且有2的k次方減1個結(jié)點的二叉樹稱為滿二叉樹2、完全二叉樹：假如有深度為k的，有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時，稱之為完全二叉樹。性質(zhì)：1、二叉樹的第i層上至多有2的i-1次方個結(jié)點(i>=1)。

2、深度為k的二叉樹至多有2的k次方減1個結(jié)點(k>=1)。

3、對任何一棵二叉樹T，假如其終端結(jié)點數(shù)為n0,度為2的結(jié)點數(shù)為n2,則n0=n2+1。

4、具備n個結(jié)點的完全二叉樹的深度為以2為底n的對數(shù)取下限加1。

5、假如對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序編號，則對任一結(jié)點i(1=<i=<n)有：

(1)假如i=1,則結(jié)點i是二叉樹的根,無雙親;假如i>1,則雙親PARENT(i)是結(jié)點[i/2]

(2)假如2i>n,則結(jié)點i無左孩子(結(jié)點i為葉子結(jié)點);否則其左孩子LCHILD(i)是結(jié)點2i

(3)假如2i+1>n,則結(jié)點i無右孩子;否則其右孩子RCHILD(i)是結(jié)點2i+1.存儲結(jié)構(gòu)：次序存儲結(jié)構(gòu)（數(shù)組方式），鏈式存儲結(jié)構(gòu)（二叉鏈表）2.程序源代碼：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineMAXSIZE50typedefcharDataType;structnode{ DataTypedata; structnode*lchild; structnode*rchild;}BitNode;typedefstructnode*BiTree;voidCreateBiTree(BiTree*T){ DataTypech; ch=getchar(); if(ch=='#') *T=NULL; else { *T=(BiTree)malloc(sizeof(BitNode)); if(!(*T)) exit(-1); (*T)->data=ch;CreateBiTree(&(*T)->lchild);CreateBiTree(&(*T)->rchild); }}voidLayerOrder(BiTreeT){ BiTreequeue[MAXSIZE]; //BitNode*p; BiTreep; intfront,rear; front=rear=-1; rear++; queue[rear]=T; while(front!=rear) { front=(front+1)%MAXSIZE; p=queue[front]; printf("%2c",p->data); if(p->lchild!=NULL) { rear=(rear+1)%MAXSIZE; queue[rear]=p->lchild; } if(p->rchild!=NULL) { rear=(rear+1)%MAXSIZE; queue[rear]=p->rchild; } } printf("\n");}voidmain(){ BiTreeT=NULL; printf("創(chuàng)建一顆二叉樹<#>表示空:\n"); CreateBiTree(&T); printf("\n"); printf("二叉數(shù)層次遍歷為:\n"); LayerOrder(T);}3.試驗成果：（四）試驗題目4：編寫程序，對二叉樹進行先序遍歷，并打印層號。1.要點分析：從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結(jié)點及左、右子樹這三個基本部分組成。因此，在任一給定結(jié)點上，能夠按某種次序執(zhí)行三個操作：（1）訪問結(jié)點自身(N)，（2）遍歷該結(jié)點的左子樹(L)，（3）遍歷該結(jié)點的右子樹(R)。依照遍歷的標準：先左后右，對于先序遍歷，顧名思義就是先訪問根節(jié)點，再訪問左子樹，最后訪問右子樹，2.程序源代碼：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineMAXSIZE50typedefcharDataType;structnode{ DataTypedata; structnode*lchild;//指向左孩子結(jié)點 structnode*rchild;//指向右孩子結(jié)點 intlevel;}BitNode;typedefstructnode*BiTree;voidCreateBiTree(BiTree*T){ DataTypech; ch=getchar(); if(ch=='#') *T=NULL; else { *T=(BiTree)malloc(sizeof(BitNode));//生成根節(jié)點 if(!(*T)) exit(-1); (*T)->data=ch;CreateBiTree(&(*T)->lchild);//結(jié)構(gòu)左子樹CreateBiTree(&(*T)->rchild);//結(jié)構(gòu)右子樹 }}voidPreOrder(BiTreeT,intlevel)//先序遍歷的遞歸實現(xiàn){ if(T) { printf("%2c%2d\n",T->data,level); PreOrder(T->lchild,++level);PreOrder(T->rchild,level); }}voidmain(){ BiTreeT=NULL; intlev=1; printf("創(chuàng)建一顆二叉樹:\n"); CreateBiTree(&T); printf("\n"); printf("二叉數(shù)先序遍歷及各點對應(yīng)的層號為:\n"); getchar(); PreOrder(T,lev);}3.試驗成果：（五）試驗題目5：編寫程序，實現(xiàn)二叉樹的先序，中序，后序遍歷，并求深度。1.要點分析：了解先序，中序，后序。2.程序源代碼：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineMAXSIZE50typedefcharDataType;structnode{ DataTypedata; structnode*lchild;//指向左孩子結(jié)點 structnode*rchild;//指向右孩子結(jié)點}BitNode;typedefstructnode*BiTree;voidCreateBiTree(BiTree*T){ DataTypech; ch=getchar(); if(ch=='#') *T=NULL; else { *T=(BiTree)malloc(sizeof(BitNode));//生成根節(jié)點 if(!(*T)) exit(-1); (*T)->data=ch;CreateBiTree(&(*T)->lchild);//結(jié)構(gòu)左子樹CreateBiTree(&(*T)->rchild);//結(jié)構(gòu)右子樹 }}voidPreOrder(BiTreeT)//先序遍歷的遞歸實現(xiàn){ if(T) { printf("%2c",T->data); PreOrder(T->lchild);PreOrder(T->rchild); }}voidInOrder(BiTreeT)//中序遍歷的遞歸實現(xiàn){ if(T) { InOrder(T->lchild); printf("%2c",T->data);InOrder(T->rchild); }}voidPostOrder(BiTreeT)//后序遍歷的遞歸實現(xiàn){ if(T) { PostOrder(T->lchild);PostOrder(T->rchild); printf("%2c",T->data); }}BiTreeFindNode(BiTreeT,DataTypee)//查找節(jié)點{ BiTreep; if(T==NULL) returnNULL; elseif(T->data==e) returnT; else { p=FindNode(T->lchild,e); if(p!=NULL) returnp; else returnFindNode(T->rchild,e); }}intBitTreeDepth(BiTreeT){ intlchildepth,rchildepth; if(T==NULL) return0; else { lchildepth=BitTreeDepth(T->lchild); rchildepth=BitTreeDepth(T->rchild); if(lchildepth>rchildepth) return(lchildepth+1); else return(rchildepth+1); }}voidmain(){ BiTreeT=NULL,root; inth; DataTypee; printf("創(chuàng)建一顆二叉樹<#>表示子樹為空:\n"); CreateBiTree(&T); printf("\n"); printf("二叉數(shù)的先序遍歷為:\n"); PreOrder(T); printf("\n"); printf("二叉數(shù)的中序遍歷為:\n"); InOrder(T); printf("\n"); printf("二叉數(shù)的后序遍歷為:\n"); PostOrder(T); printf("\n"); h=BitTreeDepth(T);printf("這課二叉數(shù)的深度為%d:",h); getchar(); printf("\n\n輸入要查找節(jié)點:"); //scanf("%c",&e); e=getchar();root=FindNode(T,e);h=BitTreeDepth(root); printf("\n以%c結(jié)點為根的子樹深度為%d:",e,h);printf("\n");}3.試驗成果：（六）試驗題目6：編寫遞歸算法，求二叉樹中以元素值為x的結(jié)點為根的子樹的深度。1.要點分析：遞歸過程一般通過函數(shù)或子過程來實現(xiàn)。遞歸措施：在函數(shù)或子過程的內(nèi)部，直接或者間接地調(diào)用自己的算法。遞歸算法所體現(xiàn)的“重復(fù)”一般有三個要求：一是每次調(diào)用在規(guī)模上都有所縮小(一般是減半)；二是相鄰兩次重復(fù)之間有緊密的聯(lián)系，前一次要為后一次做準備(一般前一次的輸出就作為后一次的輸入)；三是在問題的規(guī)模極小時必須用直接給出解答而不再進行遞歸調(diào)用，因而每次遞歸調(diào)用都是有條件的(以規(guī)模未達成直接解答的大小為條件)，無條件遞歸調(diào)用將會成為死循環(huán)而不能正常結(jié)束。2.程序源代碼：#include"stdio.h"

#include"stdlib.h"

#include"string.h"

#definenull0

structnode

{

chardata;

structnode*lchild;

structnode*rchild;

};

//先序，中序建樹

structnode*create(char*pre,char*ord,intn)

{

structnode*head;

intordsit;

head=null;

if(n<=0)

{

returnnull;

}

else

{

head=(structnode*)malloc(sizeof(structnode));

head->data=*pre;

head->lchild=head->rchild=null;

ordsit=0;

while(ord[ordsit]!=*pre)

{

ordsit++;

}

head->lchild=create(pre+1,ord,ordsit);

head->rchild=create(pre+ordsi