數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告三

第第頁數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告三

甘肅政法學(xué)院

本科生實(shí)驗(yàn)報(bào)告

（）

姓名:學(xué)院:專業(yè):班級(jí):

實(shí)驗(yàn)課程名稱:實(shí)驗(yàn)日期:指導(dǎo)教師及職稱:實(shí)驗(yàn)成績(jī):

開課時(shí)間：2023-2023學(xué)年第二學(xué)期

甘肅政法學(xué)院實(shí)驗(yàn)管理中心印制

實(shí)驗(yàn)題目姓名

第七章、樹形結(jié)構(gòu)班級(jí)

小組合作學(xué)號(hào)

否

一、實(shí)驗(yàn)?zāi)康?/p>

7.1實(shí)現(xiàn)二叉樹的各種基本運(yùn)算的算法7.2實(shí)現(xiàn)二叉樹的各種遍歷算法7.3求二叉樹從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑7.4由遍歷序列構(gòu)造二叉樹7.5實(shí)現(xiàn)中序線索化二叉樹7.6構(gòu)造哈夫曼樹7.7用二叉樹來表示代數(shù)表達(dá)式二.實(shí)驗(yàn)環(huán)境安裝了Windows7操作系統(tǒng)，并且安裝了MicrosoftVisualC++6.0。

三、實(shí)驗(yàn)內(nèi)容與步驟

7.1實(shí)現(xiàn)二叉樹的各種基本運(yùn)算的算法【編寫一個(gè)程序exp7-1.cpp,實(shí)現(xiàn)二叉樹的各種基本運(yùn)算的算法。(1)輸出二叉樹b(2)輸出H節(jié)點(diǎn)的左右孩子節(jié)點(diǎn)值(3)輸出二叉樹b的深度(4)輸出二叉樹b的寬度(5)輸出二叉樹b的節(jié)點(diǎn)個(gè)數(shù)(6)輸出二叉樹b的葉子節(jié)點(diǎn)個(gè)數(shù)(7)釋放二叉樹b1輸入程序如下：○#includestdafx.h//文件名:exp7-1.cpp#includestdio.h#includealgo7-1.cpptypedefcharElemType;//typedefstructnode//{//////ElemTypedata;structnode*lchild;structnode*rchild;//數(shù)據(jù)元素//指向左孩子//指向右孩子

//}BTNode;//externvoidCreateBTNode(BTNode*b,char*str);//externBTNode*FindNode(BTNode*b,ElemTypex);//externBTNode*LchildNode(BTNode*p);//externBTNode*RchildNode(BTNode*p);//externintBTNodeDepth(BTNode*b);//externvoidDispBTNode(BTNode*b);//externintBTWidth(BTNode*b);//externintNodes(BTNode*b);//externintLeafNodes(BTNode*b);//externvoidDestroyBTNode(BTNode*b);voidmain()

{

BTNode*b,*p,*lp,*rp;;CreateBTNode(b,A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))));printf(二叉樹的基本運(yùn)算如下:\n);printf((1)輸出二叉樹:);DispBTNode(b);printf(\n);printf((2)H節(jié)點(diǎn):);p=FindNode(b,'H');if(p!=NULL){lp=LchildNode(p);if(lp!=NULL)printf(左孩子為%c,lp-data);elseprintf(無左孩子);rp=RchildNode(p);if(rp!=NULL)printf(右孩子為%c,rp-data);elseprintf(無右孩子);}printf(\n);printf((3)二叉樹b的深度:%d\n,BTNodeDepth(b));printf((4)二叉樹b的寬度:%d\n,BTWidth(b));printf((5)二叉樹b的節(jié)點(diǎn)個(gè)數(shù):%d\n,Nodes(b));printf((6)二叉樹b的葉子節(jié)點(diǎn)個(gè)數(shù):%d\n,LeafNodes(b));printf((7)釋放二叉樹b\n);DestroyBTNode(b);

}

2輸入程序并運(yùn)行，如圖○

7.2實(shí)現(xiàn)二叉樹的各種遍歷算法編寫一個(gè)程序exp7-2.cpp,實(shí)現(xiàn)二叉樹的各種遍歷算法。1輸入程序如下：○#includestdafx.h//文件名:exp7-2.cpp#includestdio.h#includealgo7-1.cpp#includemalloc.h#defineMaxSize100typedefcharElemType;voidPreOrder(BTNode*b)//先序遍歷的遞歸算法{if(b!=NULL){printf(

%c,b-data);//訪問根節(jié)點(diǎn)PreOrder(b-lchild);//遞歸訪問左子樹PreOrder(b-rchild);//遞歸訪問右子樹}}voidPreOrder1(BTNode*b){BTNode*St[MaxSize],*p;inttop=-1;if(b!=NULL){top++;//根節(jié)點(diǎn)入棧St[top]=b;while(top-1)//棧不為空時(shí)循環(huán){p=St[top];//退棧并訪問該節(jié)點(diǎn)top--;printf(%c,p-data);if(p-rchild!=NULL)//右孩子入棧{top++;St[top]=p-rchild;}if(p-lchild!=NULL)//左孩子入棧{top++;St[top]=p-lchild;}}printf(\n);}}voidInOrder(BTNode*b)//中序遍歷的遞歸算法{if(b!=NULL){InOrder(b-lchild);//遞歸訪問左子樹printf(%c,b-data);//訪問根節(jié)點(diǎn)

InOrder(b-rchild);}

//遞歸訪問右子樹

}voidInOrder1(BTNode*b){BTNode*St[MaxSize],*p;inttop=-1;if(b!=NULL){p=b;while(top-1||p!=NULL){while(p!=NULL){top++;St[top]=p;p=p-lchild;}if(top-1){p=St[top];top--;printf(%c,p-data);p=p-rchild;}}printf(\n);}}voidPostOrder(BTNode*b)//后序遍歷的遞歸算法{if(b!=NULL){PostOrder(b-lchild);//遞歸訪問左子樹PostOrder(b-rchild);//遞歸訪問右子樹printf(%c,b-data);//訪問根節(jié)點(diǎn)}}voidPostOrder1(BTNode*b){BTNode*St[MaxSize];BTNode*p;intflag,top=-1;//棧指針置初值if(b!=NULL){do{while(b!=NULL)//將t的所有左節(jié)點(diǎn)入棧{top++;St[top]=b;b=b-lchild;}p=NULL;//p指向當(dāng)前節(jié)點(diǎn)的前一個(gè)已訪問的節(jié)點(diǎn)flag=1;

while(top!=-1flag){b=St[top];if(b-rchild==p){printf(%c,b-data);top--;p=b;}else{b=b-rchild;flag=0;}}}while(top!=-1);printf(\n);

//取出當(dāng)前的棧頂元素//右子樹不存在或已被訪問,訪問之//訪問*b節(jié)點(diǎn)//p指向則被訪問的節(jié)點(diǎn)

//t指向右子樹

}}voidTravLevel(BTNode*b){BTNode*Qu[MaxSize];//定義循環(huán)隊(duì)列intfront,rear;//定義隊(duì)首和隊(duì)尾指針front=rear=0;//置隊(duì)列為空隊(duì)列if(b!=NULL)printf(%c,b-data);rear++;//節(jié)點(diǎn)指針進(jìn)入隊(duì)列Qu[rear]=b;while(rear!=front)//隊(duì)列不為空{(diào)front=(front+1)%MaxSize;b=Qu[front];//隊(duì)頭出隊(duì)列if(b-lchild!=NULL)//輸出左孩子,并入隊(duì)列{printf(%c,b-lchild-data);rear=(rear+1)%MaxSize;Qu[rear]=b-lchild;}if(b-rchild!=NULL)//輸出右孩子,并入隊(duì)列{printf(%c,b-rchild-data);rear=(rear+1)%MaxSize;Qu[rear]=b-rchild;}}printf(\n);}voidmain(){BTNode*b;CreateBTNode(b,A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))));printf(二叉樹b:);DispBTNode(b);printf(\n);printf(層次遍歷序列:);TravLevel(b);printf(先序遍歷序列:\n);

printf(遞歸算法:);PreOrder(b);printf(\n);printf(非遞歸算法:);PreOrder1(b);printf(中序遍歷序列:\n);printf(遞歸算法:);InOrder(b);printf(\n);printf(非遞歸算法:);InOrder1(b);printf(后序遍歷序列:\n);printf(遞歸算法:);PostOrder(b);printf(\n);printf(非遞歸算法:);PostOrder1(b);DestroyBTNode(b);}}

2輸入程序并運(yùn)行，如圖○

圖8

7.3求二叉樹從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑對(duì)7.1的二叉樹，設(shè)計(jì)一個(gè)程序exp7-3.cpp完成如下功能：(1)輸出所有葉子節(jié)點(diǎn)(2)輸出所有葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑(3)輸出(2)中的第一條最長(zhǎng)路徑1輸入程序如下：○#includestdafx.h//文件名:exp7-3.cpp#includestdio.h#includemalloc.h#includealgo7-1.cpp#defineMaxSize100typedefcharElemType;

Node*b);voidAllPath(BTNode*b){structsnode{BTNode*node;intparent;}Qu[MaxSize];intfront,rear,p;front=rear=-1;rear++;Qu[rear].node=b;Qu[rear].parent=-1;while(frontrear){front++;b=Qu[front].node;//隊(duì)頭出隊(duì)列//*b為葉子節(jié)點(diǎn)//根節(jié)點(diǎn)指針進(jìn)入隊(duì)列//根節(jié)點(diǎn)沒有雙親節(jié)點(diǎn)//隊(duì)列不為空//存放當(dāng)前節(jié)點(diǎn)指針//存放雙親節(jié)點(diǎn)在隊(duì)列中的位置//定義順序隊(duì)列//定義隊(duì)頭和隊(duì)尾指針//置隊(duì)列為空隊(duì)列

if(b-lchild==NULLb-rchild==NULL){printf(%c到根節(jié)點(diǎn)逆路徑:,b-data);p=front;while(Qu[p].parent!=-1){printf(%c,Qu[p].node-data);p=Qu[p].parent;}printf(%c\n,Qu[p].node-data);}if(b-lchild!=NULL){rear++;Qu[rear].node=b-lchild;Qu[rear].parent=front;}//左孩子入隊(duì)列

if(b-rchild!=NULL){rear++;Qu[rear].node=b-rchild;Qu[rear].parent=front;}}}

//右孩子入隊(duì)列

voidAllPath1(BTNode*b,ElemTypepath[],intpathlen){inti;if(b!=NULL){if(b-lchild==NULLb-rchild==NULL){printf(%c到根節(jié)點(diǎn)逆路徑:%c,b-data,b-data);for(i=pathlen-1;i=0;i--)printf(%c,path[i]);printf(\n);}else{path[pathlen]=b-data;pathlen++;AllPath1(b-lchild,path,pathlen);//遞歸掃描左子樹AllPath1(b-rchild,path,pathlen);//遞歸掃描右子樹pathlen--;}}}voidLongPath(BTNode*b,ElemTypepath[],intpathlen,ElemTypelongpath[],intlongpathlen){inti;if(b==NULL){//恢復(fù)環(huán)境//將當(dāng)前節(jié)點(diǎn)放入路徑中//路徑長(zhǎng)度增1//*b為葉子節(jié)點(diǎn)

if(pathlenlongpathlen)//若當(dāng)前路徑更長(zhǎng),將路徑保存在longpath中{for(i=pathlen-1;i=0;i--)longpath[i]=path[i];longpathlen=pathlen;}}else{path[pathlen]=b-data;pathlen++;LongPath(b-lchild,path,pathlen,longpath,longpathlen);LongPath(b-rchild,path,pathlen,longpath,longpathlen);pathlen--;}}voidDispLeaf(BTNode*b){if(b!=NULL){if(b-lchild==NULLb-rchild==NULL)printf(%c,b-data);else{DispLeaf(b-lchild);DispLeaf(b-rchild);}}}voidmain(){BTNode*b;ElemTypepath[MaxSize],longpath[MaxSize];inti,longpathlen=0;CreateBTNode(b,A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))));printf(二叉樹b:);DispBTNode(b);printf(\n);//將當(dāng)前節(jié)點(diǎn)放入路徑中//路徑長(zhǎng)度增1//遞歸掃描左子樹//遞歸掃描右子樹//恢復(fù)環(huán)境

printf(b的葉子節(jié)點(diǎn):);DispLeaf(b);printf(\n);printf(AllPath:\n);AllPath(b);printf(AllPath1:\n);AllPath1(b,path,0);LongPath(b,path,0,longpath,longpathlen);printf(第一條最長(zhǎng)逆路徑長(zhǎng)度:%d\n,longpathlen);printf

(第一條最長(zhǎng)逆路徑:);for(i=longpathlen-1;i=0;i--)printf(%c,longpath[i]);printf(\n);DestroyBTNode(b);

}2輸入程序并運(yùn)行，如圖

○

圖12

7.4由遍歷序列構(gòu)造二叉樹【設(shè)計(jì)一個(gè)程序exp7-4.cpp實(shí)現(xiàn)由先序遍歷以及由中序遍歷序列構(gòu)造一顆二叉樹的功能要求以括號(hào)表示和凹入表示法輸入該二叉樹。并用“ABDEHJKLMNCFGI”和“DBJHLKMNEAFCGI”以及由中序遍歷序列“DBJHLKMNEAFCGI”和后序遍歷序列“DJLNMKHEBFIGCA”進(jìn)行驗(yàn)證。1輸入程序如下：○#includestdafx.h//文件名:exp7-4.cpp#includestdio.h#includemalloc.h

#includealgo7-1.cpp#defineMaxSize100#defineMaxWidth40typedefcharElemType;//typedefstructnode//{//ElemTypedata;//數(shù)據(jù)元素//structnode*lchild;//指向左孩子//structnode*rchild;//指向右孩子//}BTNode;//externvoidDispBTNode(BTNode*b);//externvoidDestroyBTNode(BTNode*b);BTNode*CreateBT1(char*pre,char*in,intn){BTNode*s;char*p;intk;if(n=0)returnNULL;s=(BTNode*)malloc(sizeof(BTNode));//創(chuàng)建二叉樹節(jié)點(diǎn)*ss-data=*pre;for(p=in;pin+n;p++)//在中序序列中找等于*ppos的位置kif(*p==*pre)break;k=p-in;s-lchild=CreateBT1(pre+1,in,k);s-rchild=CreateBT1(pre+k+1,p+1,n-k-1);returns;}BTNode*CreateBT2(char*post,char*in,intn,intm){BTNode*s;char*p,*q,*maxp;intmaxpost,maxin,k;if(n=0)returnNULL;maxpost=-1;for(p=in;pin+n;p++)//求in中全部字符中在post中最右邊的那個(gè)字符for(q=post;qpost+m;q++)//在in中用maxp指向這個(gè)字符,用maxin標(biāo)識(shí)它在in中的下標(biāo)if(*p==*q){k=q-post;if(kmaxpost){maxpost=k;maxp=p;maxin=p-in;}}s=(BTNode*)malloc(sizeof(BTNode));//創(chuàng)建二叉樹節(jié)點(diǎn)*ss-data=post[maxpost];s-lchild=CreateBT2(post,in,maxin,m);s-rchild=CreateBT2(post,maxp+1,n-maxin-1,m);returns;}voidDispBTNode1(BTNode*b)//以凹入表表示法輸出一棵二叉樹{BTNode*St[MaxSize],*p;

intlevel[MaxSize][2],top=-1,n,i,width=4;chartype;if(b!=NULL){top++;St[top]=b;//根節(jié)點(diǎn)入棧level[top][0]=width;level[top][1]=2;//2表示是根while(top-1){p=St[top];//退棧并凹入顯示該節(jié)點(diǎn)值n=level[top][0];switch(level[top][1]){case0:type='L';break;//左節(jié)點(diǎn)之后輸出(L)case1:type='R';break;//右節(jié)點(diǎn)之后輸出(R)case2:type='B';break;//根節(jié)點(diǎn)之后前輸出(B)}for(i=1;i=n;i++)//其中n為顯示場(chǎng)寬,字符以右對(duì)齊顯示printf();printf(%c(%c),p-data,type);for(i=n+1;i=MaxWidth;i+=2)printf(--);printf(\n);top--;if(p-rchild!=NULL){//將右子樹根節(jié)點(diǎn)入棧top++;St[top]=p-rchild;level[top][0]=n+width;//顯示場(chǎng)寬增widthlevel[top][1]=1;//1表示是右子樹}if(p-lchild!=NULL){//將左子樹根節(jié)點(diǎn)入棧top++;St[top]=p-lchild;level[top][0]=n+width;//顯示場(chǎng)寬增widthlevel[top][1]=0;//0表示是左子樹}}}}voidmain(){BTN

ode*b;ElemTypepre[]=ABDEHJKLMNCFGI;ElemTypein[]=DBJHLKMNEAFCGI;ElemTypepost[]=DJLNMKHEBFIGCA;b=CreateBT1(pre,in,14);printf(先序序列:%s\n,pre);printf(中序序列:%s\n,in);printf(構(gòu)造一棵二叉樹b:\n);printf(括號(hào)表示法:);DispBTNode(b);printf(\n);printf(凹入表示法:\n);DispBTNode1(b);printf(\n\n);printf(中序序列:%s\n,in);

printf(后序序列:%s\n,post);b=CreateBT2(post,in,14,14);printf(構(gòu)造一棵二叉樹b:\n);printf(括號(hào)表示法:);DispBTNode(b);printf(\n);printf(凹入表示法:\n);DispBTNode1(b);printf(\n);DestroyBTNode(b);

}2運(yùn)行程序，如圖

○

7.5實(shí)現(xiàn)中序線索化二叉樹設(shè)計(jì)一個(gè)程序exp7-5.cpp實(shí)現(xiàn)中序線索化二叉樹采用遞歸和非遞歸兩種方式輸出線索中序序列。

1輸入程序如下：○//4.cpp:Definestheentrypointfortheconsoleapplication#includestdafx.h//文件名:exp7-5.cpp#includestdio.h#includemalloc.h#defineMaxSize100typedefcharElemType;typedefstructnode{ElemTypedata;intltag,rtag;//增加的線索標(biāo)記structnode*lchild;//左孩子指針structnode*rchild;//右孩子指針}TBTNode;voidCreateTBTNode(TBTNode*b,char*str){TBTNode*St[MaxSize],*p=NULL;inttop=-1,k,j=0;charch;b=NULL;//建立的二叉樹初始時(shí)為空ch=str[j];while(ch!='\0')//str未掃描完時(shí)循環(huán){switch(ch){case'(':top++;St[top]=p;k=1;break;//為左節(jié)點(diǎn)case')':top--;break;case',':k=2;break;//為右節(jié)點(diǎn)default:p=(TBTNode*)malloc(sizeof(TBTNode));p-data=ch;p-lchild=p-rchild=NULL;if(b==NULL)//*p為二叉樹的根節(jié)點(diǎn)b=p;else//已建立二叉樹根節(jié)點(diǎn){switch(k){case1:St[top]-lchild=p;break;case2:St[top]-rchild=p;break;}}}j++;ch=str[j];}}voidDispTBTNode(TBTNode*b){if(b!=NULL){printf(%c,b-data);if(b-lchild!=NULL||b-rchild!=NULL){printf(();DispTBTNode(b-lchild);if(b-rchild!=NULL)printf(,);DispTBTNode(b-rchild);printf());}}}TBTNode*pre;//全局變量

voidThread(TBTNode*p){if(p!=NULL){Thread(p-lchild);//左子樹線索化if(p-lchild==NULL)//前驅(qū)線索{p-lchild=pre;//建立當(dāng)前節(jié)點(diǎn)的前驅(qū)線索p-ltag=1;}elsep-ltag=0;if(pre-rchild==NULL)//后繼線索{pre-rchild=p;//建立前驅(qū)節(jié)點(diǎn)的后繼線索pre-rtag=1;}elsepre-rtag=0;pre=p;Thread(p-rchild);//右子樹線索化}}TBTNode*CreateThread(TBTNode*b)//中序線索化二叉樹{TBTNode*root;root=(TBTNode*)malloc(sizeof(TBTNode));//創(chuàng)建根節(jié)點(diǎn)root-ltag=0;root-rtag=1;root-rchild=b;if(b==NULL)//空二叉樹root-lchild=root;else{root-lchild=b;pre=root;//pre是*p的前驅(qū)節(jié)點(diǎn),供加線索用Thread(b);//中序遍歷線索化二叉樹pre-rchild=root;//最后處理,加入指向根節(jié)點(diǎn)的線索pre-rtag=1;root-rchild=pre;//根節(jié)點(diǎn)右線索化}returnroot;}voidInOrder(TBTNode*tb)//被ThInOrder算法調(diào)用{if(tb-lchild!=NULLtb-ltag==0)/

/有左孩子InOrder(tb-lchild);printf(%c,tb-data);if(tb-rchild!=NULLtb-rtag==0)//有右孩子InOrder(tb-rchild);}voidThInOrder(TBTNode*tb)//中序遞歸算法{InOrder(tb-lchild);}voidThInOrder1(TBTNode*tb)//中序非遞歸算法{TBTNode*p=tb-lchild;//指向根節(jié)點(diǎn)while(p!=tb){while(p-ltag==0)p=p-lchild;printf(%c,p-data);while(p-rtag==1p-rchild!=tb){p=p-rchild;printf(%c,p-data);}

p=p-rchild;}}voidDestroyTBTNode1(TBTNode*tb)//被DestroyTBTNode算法調(diào)用{if(tb!=NULL){if(tb-lchild!=NULLtb-ltag==0)//有左孩子DestroyTBTNode1(tb-lchild);if(tb-rchild!=NULLtb-rtag==0)//有右孩子DestroyTBTNode1(tb-rchild);free(tb);}}voidDestroyTBTNode(TBTNode*tb)//釋放中序線索二叉樹的所有節(jié)點(diǎn){DestroyTBTNode1(tb-lchild);free(tb);}voidmain(){TBTNode*b,*tb;CreateTBTNode(b,A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))));printf(二叉樹:);DispTBTNode(b);printf(\n);tb=CreateThread(b);printf(線索中序序列:\n);printf(遞歸算法:);ThInOrder(tb);printf(\n);printf(非遞歸算法:);ThInOrder1(tb);printf(\n);DestroyTBTNode(tb);

}2運(yùn)行程序，如圖

○

7.6構(gòu)造哈夫曼樹設(shè)計(jì)一個(gè)程序exp7-6.cpp構(gòu)造一顆哈弗曼樹，輸出對(duì)應(yīng)哈弗曼樹編碼和平均查找長(zhǎng)度。1輸入程序如下○#includestdafx.h//文件名:exp7-6.cpp#includestdio.h#includestring.h#defineN50#defineM2*N-1typedefstruct{chardata[5];

//葉子節(jié)點(diǎn)數(shù)//樹中節(jié)點(diǎn)總數(shù)

//節(jié)點(diǎn)值

intweight;//權(quán)重intparent;//雙親節(jié)點(diǎn)intlchild;//左孩子節(jié)點(diǎn)intrchild;//右孩子節(jié)點(diǎn)}HTNode;typedefstruct{charcd[N];//存放哈夫曼碼intstart;}HCode;voidCreateHT(HTNodeht[],intn){inti,k,lnode,rnode;intmin1,min2;for(i=0;i2*n-1;i++)//所有節(jié)點(diǎn)的相關(guān)域置初值-1ht[i].parent=ht[i].lchild=ht[i].rchild=-1;for(i=n;i2*n-1;i++)//構(gòu)造哈夫曼樹{min1=min2=32767;//lnode和rnode為最小權(quán)重的兩個(gè)節(jié)點(diǎn)位置lnode=rnode=-1;for(k=0;k=i-1;k++)if(ht[k].parent==-1)//只在尚未構(gòu)造二叉樹的節(jié)點(diǎn)中查找{if(ht[k].weightmin1){min2=min1;rnode=lnode;min1=ht[k].weight;lnode=k;}elseif(ht[k].weightmin2){min2=ht[k].weight;rnode=k;}}ht[lnode].parent=i;ht[rnode].parent=i;ht[i].weight=ht[lnode].weight+ht[rnode].weight;ht[i].l