數(shù)據(jù)結構實驗報告三

第第頁數(shù)據(jù)結構實驗報告三

甘肅政法學院

本科生實驗報告

（）

姓名:學院:專業(yè):班級:

實驗課程名稱:實驗日期:指導教師及職稱:實驗成績:

開課時間：2023-2023學年第二學期

甘肅政法學院實驗管理中心印制

實驗題目姓名

第七章、樹形結構班級

小組合作學號

否

一、實驗目的

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

三、實驗內容與步驟

7.1實現(xiàn)二叉樹的各種基本運算的算法【編寫一個程序exp7-1.cpp,實現(xiàn)二叉樹的各種基本運算的算法。(1)輸出二叉樹b(2)輸出H節(jié)點的左右孩子節(jié)點值(3)輸出二叉樹b的深度(4)輸出二叉樹b的寬度(5)輸出二叉樹b的節(jié)點個數(shù)(6)輸出二叉樹b的葉子節(jié)點個數(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(二叉樹的基本運算如下:\n);printf((1)輸出二叉樹:);DispBTNode(b);printf(\n);printf((2)H節(jié)點:);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é)點個數(shù):%d\n,Nodes(b));printf((6)二叉樹b的葉子節(jié)點個數(shù):%d\n,LeafNodes(b));printf((7)釋放二叉樹b\n);DestroyBTNode(b);

}

2輸入程序并運行，如圖○

7.2實現(xiàn)二叉樹的各種遍歷算法編寫一個程序exp7-2.cpp,實現(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é)點PreOrder(b-lchild);//遞歸訪問左子樹PreOrder(b-rchild);//遞歸訪問右子樹}}voidPreOrder1(BTNode*b){BTNode*St[MaxSize],*p;inttop=-1;if(b!=NULL){top++;//根節(jié)點入棧St[top]=b;while(top-1)//棧不為空時循環(huán){p=St[top];//退棧并訪問該節(jié)點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é)點

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é)點}}voidPostOrder1(BTNode*b){BTNode*St[MaxSize];BTNode*p;intflag,top=-1;//棧指針置初值if(b!=NULL){do{while(b!=NULL)//將t的所有左節(jié)點入棧{top++;St[top]=b;b=b-lchild;}p=NULL;//p指向當前節(jié)點的前一個已訪問的節(jié)點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);

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

//t指向右子樹

}}voidTravLevel(BTNode*b){BTNode*Qu[MaxSize];//定義循環(huán)隊列intfront,rear;//定義隊首和隊尾指針front=rear=0;//置隊列為空隊列if(b!=NULL)printf(%c,b-data);rear++;//節(jié)點指針進入隊列Qu[rear]=b;while(rear!=front)//隊列不為空{front=(front+1)%MaxSize;b=Qu[front];//隊頭出隊列if(b-lchild!=NULL)//輸出左孩子,并入隊列{printf(%c,b-lchild-data);rear=(rear+1)%MaxSize;Qu[rear]=b-lchild;}if(b-rchild!=NULL)//輸出右孩子,并入隊列{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輸入程序并運行，如圖○

圖8

7.3求二叉樹從根節(jié)點到葉子節(jié)點的路徑對7.1的二叉樹，設計一個程序exp7-3.cpp完成如下功能：(1)輸出所有葉子節(jié)點(2)輸出所有葉子節(jié)點到根節(jié)點的路徑(3)輸出(2)中的第一條最長路徑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;//隊頭出隊列//*b為葉子節(jié)點//根節(jié)點指針進入隊列//根節(jié)點沒有雙親節(jié)點//隊列不為空//存放當前節(jié)點指針//存放雙親節(jié)點在隊列中的位置//定義順序隊列//定義隊頭和隊尾指針//置隊列為空隊列

if(b-lchild==NULLb-rchild==NULL){printf(%c到根節(jié)點逆路徑:,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;}//左孩子入隊列

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

//右孩子入隊列

voidAllPath1(BTNode*b,ElemTypepath[],intpathlen){inti;if(b!=NULL){if(b-lchild==NULLb-rchild==NULL){printf(%c到根節(jié)點逆路徑:%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){//恢復環(huán)境//將當前節(jié)點放入路徑中//路徑長度增1//*b為葉子節(jié)點

if(pathlenlongpathlen)//若當前路徑更長,將路徑保存在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);//將當前節(jié)點放入路徑中//路徑長度增1//遞歸掃描左子樹//遞歸掃描右子樹//恢復環(huán)境

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

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

}2輸入程序并運行，如圖

○

圖12

7.4由遍歷序列構造二叉樹【設計一個程序exp7-4.cpp實現(xiàn)由先序遍歷以及由中序遍歷序列構造一顆二叉樹的功能要求以括號表示和凹入表示法輸入該二叉樹。并用“ABDEHJKLMNCFGI”和“DBJHLKMNEAFCGI”以及由中序遍歷序列“DBJHLKMNEAFCGI”和后序遍歷序列“DJLNMKHEBFIGCA”進行驗證。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é)點*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中最右邊的那個字符for(q=post;qpost+m;q++)//在in中用maxp指向這個字符,用maxin標識它在in中的下標if(*p==*q){k=q-post;if(kmaxpost){maxpost=k;maxp=p;maxin=p-in;}}s=(BTNode*)malloc(sizeof(BTNode));//創(chuàng)建二叉樹節(jié)點*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é)點入棧level[top][0]=width;level[top][1]=2;//2表示是根while(top-1){p=St[top];//退棧并凹入顯示該節(jié)點值n=level[top][0];switch(level[top][1]){case0:type='L';break;//左節(jié)點之后輸出(L)case1:type='R';break;//右節(jié)點之后輸出(R)case2:type='B';break;//根節(jié)點之后前輸出(B)}for(i=1;i=n;i++)//其中n為顯示場寬,字符以右對齊顯示printf();printf(%c(%c),p-data,type);for(i=n+1;i=MaxWidth;i+=2)printf(--);printf(\n);top--;if(p-rchild!=NULL){//將右子樹根節(jié)點入棧top++;St[top]=p-rchild;level[top][0]=n+width;//顯示場寬增widthlevel[top][1]=1;//1表示是右子樹}if(p-lchild!=NULL){//將左子樹根節(jié)點入棧top++;St[top]=p-lchild;level[top][0]=n+width;//顯示場寬增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(構造一棵二叉樹b:\n);printf(括號表示法:);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(構造一棵二叉樹b:\n);printf(括號表示法:);DispBTNode(b);printf(\n);printf(凹入表示法:\n);DispBTNode1(b);printf(\n);DestroyBTNode(b);

}2運行程序，如圖

○

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

1輸入程序如下：○//4.cpp:Definestheentrypointfortheconsoleapplication#includestdafx.h//文件名:exp7-5.cpp#includestdio.h#includemalloc.h#defineMaxSize100typedefcharElemType;typedefstructnode{ElemTypedata;intltag,rtag;//增加的線索標記structnode*lchild;//左孩子指針structnode*rchild;//右孩子指針}TBTNode;voidCreateTBTNode(TBTNode*b,char*str){TBTNode*St[MaxSize],*p=NULL;inttop=-1,k,j=0;charch;b=NULL;//建立的二叉樹初始時為空ch=str[j];while(ch!='\0')//str未掃描完時循環(huán){switch(ch){case'(':top++;St[top]=p;k=1;break;//為左節(jié)點case')':top--;break;case',':k=2;break;//為右節(jié)點default:p=(TBTNode*)malloc(sizeof(TBTNode));p-data=ch;p-lchild=p-rchild=NULL;if(b==NULL)//*p為二叉樹的根節(jié)點b=p;else//已建立二叉樹根節(jié)點{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)//前驅線索{p-lchild=pre;//建立當前節(jié)點的前驅線索p-ltag=1;}elsep-ltag=0;if(pre-rchild==NULL)//后繼線索{pre-rchild=p;//建立前驅節(jié)點的后繼線索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é)點root-ltag=0;root-rtag=1;root-rchild=b;if(b==NULL)//空二叉樹root-lchild=root;else{root-lchild=b;pre=root;//pre是*p的前驅節(jié)點,供加線索用Thread(b);//中序遍歷線索化二叉樹pre-rchild=root;//最后處理,加入指向根節(jié)點的線索pre-rtag=1;root-rchild=pre;//根節(jié)點右線索化}returnroot;}voidInOrder(TBTNode*tb)//被ThInOrder算法調用{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é)點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算法調用{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é)點{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運行程序，如圖

○

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

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

//節(jié)點值

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