2023年樹和二叉樹實(shí)驗(yàn)報告

樹和二叉樹實(shí)驗(yàn)報告課程一數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)名稱樹和二叉樹系別.計(jì)算機(jī)學(xué)院專業(yè)班級軟件134姓名.徐雅欣學(xué)號實(shí)驗(yàn)日期：2023年6月7日實(shí)驗(yàn)?zāi)康模海?）掌握二叉樹,二叉樹排序數(shù)的概念及存儲方法。（二）掌握二叉樹的遍歷算法（三）純熟掌握編寫實(shí)現(xiàn)樹的各種運(yùn)算的算法二.實(shí)驗(yàn)內(nèi)容（-）實(shí)驗(yàn)題目一:建立一棵二叉樹并中序遍歷（填空）.要點(diǎn)分析：中序遍歷的遍歷規(guī)則是（前中后），既先訪問左子樹，在訪問當(dāng)前節(jié)點(diǎn),最后訪問右子樹。.程序源代碼：#include<stdio.h>#include<ma11oc.h>struetnode（?chardata;structnode*lchild,*rchild;}bnode;typedefstructnode*blink;blinkadd（blinkbt,charch）{?if(bt==NULL)

■C:\Users\Administrator\Desktop\程序\shiyanwu\Debug逐次遍歷.exe"創(chuàng)建一顆二叉樹＜紛表示空:二叉數(shù)層次遍歷為：ABCDEPressanykeytocontinue口X(四)實(shí)驗(yàn)題目4：編寫程序，對二叉樹進(jìn)行先序遍歷,并打印層號?？赬】.要點(diǎn)分析：從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結(jié)點(diǎn)及左、右子樹這三個基本部分組成。因此，在任一給定結(jié)點(diǎn)上，可以按某種順序執(zhí)行三個操作：(1)訪問結(jié)點(diǎn)自身(N),(2)遍歷該結(jié)點(diǎn)的左子樹(L),(3)遍歷該結(jié)點(diǎn)的右子樹(R)。根據(jù)遍歷的原則：先左后右，對于先序遍歷，顧名思義就是先訪問根節(jié)點(diǎn)，再訪問左子樹，最后訪問右子樹,2.程序源代碼：#include<stdio.h>include<std1ib.h>include<mal1oc.h>defineMAXSIZE50typedefcharDataType；structnodeDataTypedata;structnode*lchiId;〃指向左孩子結(jié)點(diǎn)structnode*rchild；//指向右孩子結(jié)點(diǎn)nt1evel;}BitNode;typedefstructnode*BiTree;voidCreateBiTree(BiTree*T)(eDataTypech;ch=getchar();?if(ch=='#')o*T=NULL;?else{*T=(BiTree)mal1oc(sizeof(BitNode))；〃生成根節(jié)點(diǎn)aif(!(*T))?exit(-1)；。(*T)->data=ch;CrcateBiTree(&(*T)->lchild);//構(gòu)造左子樹CreateBiTree(&(*T)->rchild);//構(gòu)造右子樹}voidPreOrder(BiTreeT,int1eve1)//先序遍歷的遞歸實(shí)現(xiàn)Mf(T)。(,sprintf(“為2c%2d\n〃，T->data,1eve1);?PreOrder(T->lchi1d,++level)；PreOrder(T—>rchild,leve1);)voidmainO(密訂reeT=NULL;6intlev=1;printf("創(chuàng)建一顆二叉樹:\n")；?CreateBiTree(&T);叩rintf('\n");printf("二叉數(shù)先序遍歷及各點(diǎn)相應(yīng)的層號為：\n〃);ogetchar();PreOrder〕,lev);3.實(shí)驗(yàn)結(jié)果:IL-H°IxB二叉數(shù)先序遍歷及各點(diǎn)對應(yīng)的層號為：■B2C2D3E3c:IPressanykeytocontinue（五）實(shí)驗(yàn)題目5：編寫程序,實(shí)現(xiàn)二叉樹的先序，中序，后序遍歷，并求深度0.要點(diǎn)分析：了解先序，中序，后序。.程序源代碼：#include<stdio.h>include<std1ib.h>include<malloc.h>#defineMAXSIZE50typedefcharDataType;structnodeDataTypedata;structnode*lchild;//指向左孩子結(jié)點(diǎn)ostructnode*rchi1d;〃指向右孩子結(jié)點(diǎn)}BitNode;typedefstructnode*BiTree；voidCreateBiTree(BiTree*T)DataTypech;ch=getchar();f(ch=='#')o*T=NULL;else?*T=(BiTree)malloc(sizeof(BitNode));//生成根節(jié)點(diǎn)aif(!(*T))。exit(-1);a(*T)—>data=ch;CreateBiTree(&(*T)->lchild)；//構(gòu)造左子樹CreateBiTree(&(*T)->rchild);〃構(gòu)造右子樹})voidPreOrder(BiTreeT)〃先序遍歷的遞歸實(shí)現(xiàn)(f(T)(0。printfC%2c",T->data)；3PreOrder(T->1child);PreOrder(T—>rchiid)；voidInOi*der(BiTreeT)//中序遍歷的遞歸實(shí)現(xiàn)oif(T)。(InOrder(T->lchiId);printf(“/2c”,T->data)；InOrder(T->rchiId);。})voidPostOrder(BiTreeT)〃后序遍歷的遞歸實(shí)現(xiàn)(if(T)(。PostOrdcr(T—>lchi1d);PostOrder(T—>rchild);aprintf("%2cM,T->data);}BiTreeFindNode(BiTreeT,DataTypee)〃查找節(jié)點(diǎn)(BiTreep；oifgNULL)returnNULL：elseif(T->data==e)returnT;史Ise(?p=FindNode(T->lchi1d,e);~if(p!=NULL)。?>returnp;。else。oreturnFindNode(T—>rchild,e)；。})intBitTreeDepth(BiTreeT)(int1childepth,rchildepth;式f(T==NULL)^return0;e1se{1chiIdepth=BitTrceDcpth(T—>lchild);rchi1deplh=BitTreeDepth(T->rchi1d)；。if(Ichildepth>rchildepth)8return(lchiIdepth+1);oe1sereturn(rchildepth+1)；voidmain()(BiTreeT=NULL,root：ointh;?DataTypee;叩rintf(〃創(chuàng)建一顆二又樹＜#＞表達(dá)子樹為空：\n");eCreateBiTree(&T)；叩rintf("\n");oprintf("二叉數(shù)的先序遍歷為:\n")；PreOrder(T);printf('\n");?printf("二叉數(shù)的中序遍歷為:\n");?InOrder(T);printf("\n");叩rintf(〃二叉數(shù)的后序遍歷為：\n〃)；?PostOrder(T);?printf(〃\n〃);?h=BitTreeDepth(T);printf("這課二義數(shù)的深度為%d:”,h)；egetchar()；"rintf(”\n\n輸入要查找節(jié)點(diǎn)：〃)；“/scanf&e);e=getchar();root=FindNode(T,e);h=BitTreeDepth(root);PrintfC\n以%c結(jié)點(diǎn)為根的子樹深度為%d:",e,h）;3.實(shí)驗(yàn)結(jié)果:'C:\Users\Administrator\Desktop\程序\shiyanwu\Debug選序、中序、，看序且求深度.exe"創(chuàng)建一顆二叉樹“）表示子樹為空:ABttltCDttttEtttt二叉數(shù)的先序遍歷為：ABCDE二叉數(shù)的巾序遍歷為：BADCE二叉數(shù)的后序遍歷為：BDECA這課二叉數(shù)的深度為3：輸入要查找節(jié)點(diǎn)：（六）實(shí)驗(yàn)題目6:編寫遞歸算法,求二叉樹中以元素值為x的結(jié)點(diǎn)為根的子樹的深度。1.要點(diǎn)分析:遞歸過程?般通過函數(shù)或子過程來實(shí)現(xiàn)。遞歸方法:在函數(shù)或子過程的內(nèi)逆,直接或者間接地調(diào)用自己的算法。遞歸算法所體現(xiàn)的“反復(fù)”?般有三個規(guī)定：一是每次調(diào)用在規(guī)模上都有所縮?。ㄍǔＪ菧p半）；二是相鄰兩次反復(fù)之間有緊密的聯(lián)系，前一次要為后一次做準(zhǔn)備（通常前一次的輸出就作為后一次的輸入）;三是在問題的規(guī)模極小時必須用直接給出解答而不再進(jìn)行遞歸調(diào)用，因而每次遞歸調(diào)用都是有條件的(以規(guī)模未達(dá)成直接解答的大小為條件)，無條件遞歸調(diào)用將會成為死循環(huán)而不能止常結(jié)束。2.程序源代碼：#include"stdio.h"#include'stdlib.h"#inc1ude"string,h'a#definenul1Onstructnode(chardata；astructnode*lchild;astructnode*rchild；);aa//先序，中序建樹astructnode*create(char*pre,char*ord,intn)a{structnode*head；Aintordsit;ahead=nul1；if(n<=0)(returnnu11;a}ae1se(head=(structnode*)malloc(sizeof(structnode))；Ahead->data=*pre;Ahead—>lchild二head—>rchiId二null;aordsit=0;while(ord[ordsit]!=*pre){7)rdsil++;a}head—>Ichiid=create(pre+1,ord?ordsit);ead—>rchild=create(pre+ordsit+1,ord+ordsit+1,n-ordsit-1);returnhead：。bt=(blink)ma11oc(sizeof(bnode));bt->data=ch;??bt->lchi1d=bt—>rchild=NULL;}oelseif(ch<bt->data)~bt->lchild=add(bt—>1child,ch);else<4)t->rchild=add(bt->rchild,ch);returnbt；)voidinorder(blinkbt){if(bt)。(。inorder(bt—>Ichi1d);printfC%2c",bt—>data);inorder(bt->rchild);0})main()(blinkroot=NULL;inti,n；charx;seanf("%d*,&n);for(i=0;i<=n;i4-+)//中序遞歸遍歷Avoidinorder(structnode*head){aif(!head)Areturn;acIsea(Ainorder(head->lchiId)；printf("%c",head->data);inorder(head->rchi1d)；a}}中序非遞歸遍歷voidinorderi(structnode*head)(structnode*p;structnode*stack[20]；inttop=0;ap=head;while(p|11op!=0){Awhile(p){Astack[top++]=p;p=p->lchiId;}Ap=stack[-top];printf(飛c”,p->data);ap=p->rchild;}A}a〃主函數(shù)Aintmain()a{astructnode*head；acharpre[30],ord[30]；intn；agets(pre);gets(ord);an=str1en(pre);Ahead=create(pre,ord,n);Ainorder(head);

printf("\n");inorder1(head);aprintf("\n");a}3.實(shí)驗(yàn)結(jié)果:在運(yùn)用程序設(shè)計(jì)求解問題實(shí)現(xiàn)功能時,我們一方面要對問題進(jìn)行分析，將所要實(shí)現(xiàn)的功能分解成若干子功能來實(shí)現(xiàn),這就需要對設(shè)計(jì)方法不斷優(yōu)化。隊(duì)以同一問題，解決的方法很多，但尋求一個簡樸的方法,一個可以用簡樸的計(jì)算機(jī)語言語句實(shí)驗(yàn)的方法，才是問題額求解方法設(shè)計(jì)的關(guān)鍵。就像本次課程設(shè)計(jì)中實(shí)現(xiàn)二叉樹樹樁輸出時,有很多方法來擬定二叉樹結(jié)點(diǎn)和數(shù)組的相應(yīng)關(guān)系，但適合計(jì)算機(jī)的簡樸方法才是最佳最重要的。◎X=getcheir():groot=add(root,x);)inorder(root);?printf("\n")：)3.實(shí)驗(yàn)結(jié)果：皿事丁m7VpE?「二I-口x8ephqsbmaabehmpqsPressanykeytocontinue（二）實(shí)驗(yàn)題目2:編寫程序,求二叉樹的節(jié)點(diǎn)數(shù)和葉子樹。.要點(diǎn)分析：.定理：二叉樹假如有vO個葉子節(jié)點(diǎn)，那么就有v0-1個度為二的節(jié)點(diǎn)就是v0-l=v2a定理:二叉樹有N個節(jié)點(diǎn)N=v0+vl+v2即節(jié)點(diǎn)總數(shù)等于度為0,1,2的節(jié)點(diǎn)的和。.程序源代碼:#include<stdio.h>#inc1ude<ma1loc.h>闔defineERROR0^defineOK1#defineOVERFLOW-2#defineTRUE1typcdefintStatus；AtypedefcharTEIcmType；typedefstructBiTNode{TElemTypedata;structBiTNode*Ichi1d,*rchi1d;(BiTNode,*BiTree：Mntcount=0；AStatusCreateBiTree(BiTree*T){charch；Ascanf("%c”,&ch);if(ch==,')(*T)=NULL；ac1so)Aif(!((*T)=(BiTNode*)ma11oc(sizeof(BiTNode))))^exit(OVERFLOW);^(*T)->data=ch;^CreateBiTree(&((*T)->1chi1d));^CreateBiTree(&((*T)->rchild));}returnOK；}aStatusCountleaf(BiTreeT)(if(T){if((!T->lchild)&&(!T->rchiId))count++；aCountleaf(T->lchi1d)；aCountleaf(T->rchild)；A)Areturncount;)StatusDepth(BiTreeT){intdepthval,depthleft=0,depthright=0；Aif(!T)depthva1=0；Ae1se{depthleft=Depth(T->lchiId)；Mepthright=Depth(T->rchi1d)；depthval=l+(depth1eft>depthright?depthleft:depthright)；a}returndepthva1;}aStatusPreordcr(BiTrecT)a{if(T)a{printf(“猊"，T->data);Preorder(T->1child);Preorder(T->rchild)；a})StatusInOrderTraverse(BiTreeT,Status(*Visit)(TE1emTypee))(aStackS；InitStack(S);p=T；Awhile(p=!StackEmpty(S)){Mf(p){Push(S,p)；p=p—>lchild;}else{Pop(S,p);if(!Visit(p->data))returnERROR；Ap=p->rchi1(1；a}a}returnOK;}Avoidmain(){BiTreeT；Aprintf("pleaseinputaTree：/，);CreateBiTree(&T);printf("theTreeis:")；reorder(T)printfInOrderTraverse(T)；printf("\n")；Aprintf("thenumberofleavesis:〃)printfCountleaf(T));Pprintf("theDepthofthetreeis:〃)；printfDepth(T));petch();△}3.實(shí)驗(yàn)結(jié)果:'C:\Users\Administrator\Desktop\^/?\shiyanwu\Debug\^i5^?^WlH^^.exe'按照先序字符創(chuàng)建一顆二叉樹〈以1t號表示空工ABDttttGHttttIttttCEttttFtttt這舜二叉科的節(jié)點(diǎn)鰲髻：9這楝二叉樹的葉子數(shù)皂5Pressanykeytocontinue(三)實(shí)驗(yàn)題目3：編寫程序，實(shí)現(xiàn)按層次遍歷二叉樹。.要點(diǎn)分析:定義：1、滿二叉樹：一棵深度為k且有2的k次方減I個結(jié)點(diǎn)的二叉樹稱為滿二叉樹2、完全二叉樹:假如有深度為k的，有n個結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為k的滿二叉樹中編號從1至n的結(jié)點(diǎn)一一相應(yīng)時，稱之為完全二叉樹。性質(zhì)：I、二叉樹的第i層上至多有2的i—1次方個結(jié)點(diǎn)(i>=1)。2、深度為k的二叉樹至多有2的k次方減1個結(jié)點(diǎn)(k>=l)。、對任何一棵二叉樹T,假如其終端結(jié)點(diǎn)數(shù)為nO,度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。4、具有n個結(jié)點(diǎn)的完全二叉樹的深度為以2為底n的對數(shù)取下限加1。5a、假如對一棵有n個結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號，則對任?結(jié)點(diǎn)i(gvi=vn)有：1(a)假如i=l,則結(jié)點(diǎn)i是二叉樹的根，無雙親；假如i>l,則雙親PARENT(i)是結(jié)點(diǎn)［i/2卜(2)假如2i>n,則結(jié)點(diǎn)i無左孩子(結(jié)點(diǎn)i為葉子結(jié)點(diǎn));否則其左孩子LCHILD(i)是結(jié)點(diǎn)2i⑶假如2i+l>n,則結(jié)點(diǎn)i無右孩子；否則其右孩子RCHILD(i)是結(jié)點(diǎn)2i+l.存儲結(jié)構(gòu):順序存儲結(jié)構(gòu)（數(shù)組方式），鏈?zhǔn)酱鎯Y(jié)構(gòu)（二叉鏈表）.程序源代碼:#include<stdio.h>#include<stdlib.h>include<mal1oc.h>defineMAXS