二叉樹抽象數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)實驗報告

-z.數(shù)據(jù)構(gòu)造實驗報告題目：二叉樹抽象數(shù)據(jù)類型的實現(xiàn)學(xué)院***學(xué)院專業(yè)*********年級班別***********學(xué)號***********學(xué)生*************指導(dǎo)教師成績____________________2012年6月報告：容： □詳細(xì) □完整 □不完整設(shè)計方案： □非常合理 □合理 □較差實現(xiàn)： □全部實現(xiàn) □局部實現(xiàn) □未實現(xiàn)文檔格式： □規(guī) □根本規(guī) □不規(guī)辯論：□理解題目透徹，問題答復(fù)流利□理解題目較透徹，答復(fù)下列問題根本正確□局部理解題目，局部問題答復(fù)正確□未能完全理解題目，辯論情況較差總評成績：□優(yōu)□良□中□及格□不及格-z.一．實驗概要二叉樹抽象數(shù)據(jù)類型的實現(xiàn)二.實驗?zāi)康牧私舛鏄涞亩x以及各項根本操作。實現(xiàn)二叉樹存儲、遍歷及其他根本功能三.實驗儀器設(shè)備和材料Visualstudio2010四．實驗的容1.二叉樹類型定義以及各根本操作的簡要描述；ADTBinaryTree{數(shù)據(jù)對象D:D是具有一樣特性的數(shù)據(jù)元素的集合.數(shù)據(jù)關(guān)系R:假設(shè)D=?，則R=,稱BinaryTree為空二叉樹；假設(shè)D≠，則R={H}，H是如下二元關(guān)系：在D中存在惟一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；假設(shè)D-{root}≠?，則存在D-{root}={D1,Dr}，且D1∩Dr=?；假設(shè)D1≠?，則D1中存在惟一的元素*1，<root，*1>∈H，且存在Dr上的關(guān)系Hr∈H；H={<root，*1>，<root，*r>，H1,Hr}；〔D1，{H1}〕是一棵符合本定義的二叉樹，稱為根的左子樹，是一棵符合本定義的二叉樹，稱為根的右子樹。根本操作P:InitBiTree(&T);操作結(jié)果：構(gòu)造空二叉樹T。DestroyBiTree(&T);初始條件：二叉樹T存在。操作結(jié)果：銷毀二叉樹T。CreateBiTree(&T,definition);初始條件：definition給出二叉樹T的定義。操作結(jié)果：按definition構(gòu)造二叉樹T。ClearBiTree(&T);初始條件：二叉樹T存在。操作結(jié)果：將二叉樹T清為空樹。BiTreeEmpty(T);初始條件：二叉樹T存在。操作結(jié)果：假設(shè)T為空二叉樹，則返回TURE,否則FALSE。BiTreeDepth(T);初始條件：二叉樹T存在。操作結(jié)果：返回T的深度。Root(T);初始條件：二叉樹T存在。操作結(jié)果：返回T的根。Value(T,e);初始條件：二叉樹T存在，e是T中的*個結(jié)點。操作結(jié)果：返回e的值。Assign(T,&e,value);初始條件：二叉樹T存在，e是T中的*個結(jié)點。操作結(jié)果：結(jié)點e賦值為value。Parent(T,e);初始條件：二叉樹T存在，e是T中的*個結(jié)點。操作結(jié)果：假設(shè)e是T的非跟結(jié)點，則返回它的雙親，否則返回“空〞。LeftChild(T,e);初始條件：二叉樹T存在，e是T中的*個結(jié)點。操作結(jié)果：返回e的左孩子。假設(shè)e無左孩子，則返回“空〞。RightChild(T,e);初始條件：二叉樹T存在，e是T中的*個結(jié)點。操作結(jié)果：返回e的右孩子。假設(shè)e無右孩子，則返回“空〞。LeftSibling(T,e);初始條件：二叉樹T存在，e是T中的*個結(jié)點。操作結(jié)果：返回e的左兄弟。假設(shè)e無左孩子或無左兄弟，則返回“空〞。RightSibling(T,e);初始條件：二叉樹T存在，e是T中的*個結(jié)點。操作結(jié)果：返回e的右兄弟。假設(shè)e無右孩子或無右兄弟，則返回“空〞。}ADTBinaryTree2.所選擇的存儲構(gòu)造描述及在此存儲構(gòu)造上各根本操作的實現(xiàn)；3.源代碼主文件:main.ccp:#include"base.h" //公用頭文件、公共常量及公共函數(shù)等#include"bitree.h" //二叉樹二叉鏈表根本操作void Menu(); //菜單函數(shù)void Produce(char*str); //隨機(jī)產(chǎn)生二叉樹先序序列函數(shù)int main() //主函數(shù){ BiTree T,bt,insert_bt; char cmd,str[MA*SIZE],elem; int loc,temp; InitBiTree(T); //初始化二叉鏈表二叉樹 Menu(); //顯示菜單 while(1) { ClearLine(); //清空結(jié)果顯示區(qū) printf("請選擇操作：(按‘Q'退出)"); cmd=getch(); ClearLine(); fflush(stdin); switch(cmd) { case'0'://隨機(jī)創(chuàng)立一棵二叉樹 while(cmd!='y'&&cmd!='Y') { Produce(str); //隨機(jī)產(chǎn)生二叉樹先序序列 CreateBiTree(T,str);//用此序列建樹 ShowBiTree(T); //廣義表形式顯示 printf("使用創(chuàng)立的這個二叉樹<Y/N>?"); cmd=getch(); ClearLine(); } break; case'2'://手動創(chuàng)立一棵二叉樹 printf("請按二叉樹先序序列輸入二叉樹：(空結(jié)點用空格''表示)\n"); CreateBiTree(T); ClearLine(); printf("二叉樹創(chuàng)立成功!\n"); ShowBiTree(T); getch(); break; case'4'://銷毀二叉樹 DestroyBiTree(T); printf("二叉樹已被銷毀!"); getch(); break; case'6'://判空 if(BiTreeEmpty(T))printf("二叉樹是空二叉樹。"); else printf("二叉樹非空"); getch(); break; case'8'://求深度 printf("深度是%d",BiTreeDepth(T)); getch(); break; case'a'://求左孩子 ShowBiTree(T); printf("你想求哪個字符的左孩子？"); do{ elem=getchar(); ClearLine(); bt=SearchBiTree(T,elem); //查找指定的結(jié)點值elem if(!bt)printf("你輸入的結(jié)點不存在!請重新輸入："); }while(!bt); ClearLine(); bt=LeftChild(T,bt); //求左孩子 if(bt)printf("%c的左孩子是%c",elem,bt->data); else printf("%c沒有左孩子",elem); printf("\n參照二叉樹:"); ShowBiTree(T); getch(); break; case'c'://求右孩子 ShowBiTree(T); printf("你想求哪個字符的右孩子？"); do{ elem=getchar(); ClearLine(); bt=SearchBiTree(T,elem); if(!bt)printf("你輸入的結(jié)點不存在!請重新輸入："); }while(!bt); ClearLine(); bt=RightChild(T,bt); if(bt)printf("%c的右孩子是%c",elem,bt->data); else printf("%c沒有右孩子",elem); printf("\n參照二叉樹:"); ShowBiTree(T); getch(); break; case'1'://先序遍歷 if(!BiTreeEmpty(T)) { printf("先序遍歷序列為："); PreOrderTraverse(T,Visit); } elseprintf("二叉樹空，請先建樹!"); getch(); break; case'3'://中序遍歷 if(!BiTreeEmpty(T)) { printf("中序遍歷序列為："); InOrderTraverse(T,Visit); } elseprintf("二叉樹空，請先建樹!"); getch(); break; case'5'://后序遍歷 if(!BiTreeEmpty(T)) { printf("后序遍歷序列為："); PostOrderTraverse(T,Visit); } elseprintf("二叉樹空，請先建樹!");getch(); break; case'7'://層次遍歷 if(!BiTreeEmpty(T)) { printf("層次遍歷序列為："); LevelOrderTraverse(T,Visit); } elseprintf("二叉樹空，請先建樹!"); getch(); break; case'9'://插入一棵二叉樹為另一棵二叉樹的子樹 do{ //隨機(jī)創(chuàng)立一棵右孩子為空 Produce(str); //且層數(shù)小于4的樹 CreateBiTree(insert_bt,str); }while(insert_bt->rchild||BiTreeDepth(insert_bt)>3); printf("先隨機(jī)創(chuàng)立一棵右子樹空的二叉樹如圖\n"); ShowBiTree(insert_bt); //新創(chuàng)立的樹 getch(); printf("你想插入這棵樹為原樹哪個結(jié)點的子樹:\n"); ShowBiTree(T); bt=SearchBiTree(T,getchar()); ClearLine(); printf("你想插入為0.左孩子1.右孩子:"); fflush(stdin); scanf("%d",&loc); if(!InsertChild(T,bt,loc,insert_bt)) printf("插入出錯!"); else{ ClearLine(); printf("插入成功!插入后T廣義表形式為:\n"); ShowBiTree(T); } getch(); break; case'b'://刪除指定結(jié)點的子樹 ShowBiTree(T); printf("你想刪除哪個結(jié)點的子樹?"); fflush(stdin); bt=SearchBiTree(T,getchar()); printf("\n你想刪除0.左子樹1.右子樹:"); fflush(stdin); scanf("%d",&loc); ClearLine(); if(!DeleteChild(T,bt,loc))printf("刪除出錯!"); elseprintf("刪除成功，檢查結(jié)果\n"); ShowBiTree(T); getch(); break; case'e'://返回先序序列第i個結(jié)點的值 printf("請輸入一個結(jié)點的先序序列序號:"); scanf("%d",&loc); temp=loc; ClearLine(); elem=Value(T,temp); printf("參照二叉樹:"); ShowBiTree(T); printf("\n"); if(elem=='') printf("該結(jié)點不存在。"); elseprintf("先序序列第%d個結(jié)點值為%c",loc,elem); getch();break; case'd'://結(jié)點賦值 ShowBiTree(T); printf("請輸入要賦值的結(jié)點:"); do{ elem=getchar(); ClearLine(); bt=SearchBiTree(T,elem); if(!bt)printf("你輸入的結(jié)點不存在!請重新輸入："); }while(!bt);; ClearLine(); printf("請輸入新值:"); fflush(stdin); elem=getchar(); Assign(T,bt,elem); printf("賦值成功，請查看二叉樹狀態(tài).\n"); ShowBiTree(T); getch(); break; case'Q'://退出 case'q':e*it(0); } } return0;}void Menu()//顯示菜單函數(shù){ printf("0.隨機(jī)創(chuàng)立CreateBiTree()1.先序遍歷PreOrderTraverse()"); printf("\n\n2.手動創(chuàng)立CreateBiTree()3.中序遍歷InOrderTraverse()"); printf("\n\n4.銷毀DestoryBiTree()5.后序遍歷PostOrderTraverse()"); printf("\n\n6.判空BiTreeEmpty()7.層次遍歷LevelOrderTraverse()"); printf("\n\n8.求深度BiTreeDepth()9.插入子樹InsertChild()"); printf("\n\na.求左孩子LeftChild()b.刪除子樹DeleteChild()"); printf("\n\nc.求右孩子RightChild()d.結(jié)點賦值A(chǔ)ssign()"); printf("\n\ne.求結(jié)點值Value()"); printf("\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");}void Produce(char*str)//用隨機(jī)數(shù)產(chǎn)生二叉樹層次字符序列//使所有節(jié)點的字符不一樣，空節(jié)點用‘&’表示{ int e*ist[27],i,elem,ma*nodes=rand()%41; while(ma*nodes<15||ma*nodes>31)ma*nodes=rand()%41; /*隨機(jī)產(chǎn)生一個大于15小于31的隨機(jī)數(shù)作為結(jié)點個數(shù)*/ for(i=0;i<27;i++)e*ist[i]=0; //初始化存在數(shù)組，用于使所有結(jié)點值不同 i=1; while(i<ma*nodes) { elem=rand()%26; if(!e*ist[elem]&&str[i/2]!='&')//結(jié)點未生成且存在父節(jié)點 { str[i++]=elem+'A'; e*ist[elem]=1; } elsestr[i++]='&'; } str[i]='\0';}頭文件:base.h:#include"stdio.h"#include"conio.h"#include"stdlib.h"#include"windows.h"#include"malloc.h"#include"math.h"#define OK 1#define TRUE 1#define ERROR 0#define FALSE 0#define MA*SIZE 100 typedef int Status;typedef char TElemType; short where*() //返回光標(biāo)的*坐標(biāo){ CONSOLE_SCREEN_BUFFER_INFOcsbinfo; GetConsoleScreenBufferInfo(GetStdHandle(STD_OUTPUT_HANDLE),&csbinfo); returncsbinfo.dwCursorPosition.*;}short wherey() //返回光標(biāo)的y坐標(biāo){ CONSOLE_SCREEN_BUFFER_INFOcsbinfo; GetConsoleScreenBufferInfo(GetStdHandle(STD_OUTPUT_HANDLE),&csbinfo); returncsbinfo.dwCursorPosition.Y;}voidgoto*y(short*,shorty) //移動光標(biāo)到〔*，y〕坐標(biāo){ COORDpoint={*,y};SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),point);}voidClearLine(unsignedy=17)//去除第y行與y+1行的字符，并使光標(biāo)在行首，默認(rèn)去除第17至19行{ for(inti=0;i<256;i++) { goto*y(i,y); putchar(''); } goto*y(0,wherey()-3);}voidClearAera(unsigned*=96,unsignedy=17)//去除(0,y)-(*,y+1)區(qū)域的字符，并使光標(biāo)移動到y(tǒng){ for(unsignedi=0;i<*;i++) { goto*y(i%(*/2),y+(i/48)); putchar(''); } goto*y(0,y);}Status Visit(TElemTypee)//二叉樹結(jié)點visit函數(shù)，顯示字符的值{ printf("%c",e); returnOK;}******************華美的分割線***********************bitree.h:typedefchar TElemType;typedef struct BiTNode{ TElemType data; struct BiTNode *lchild; struct BiTNode *rchild;//左右孩子指針}BiTNode,*BiTree; void InitBiTree(BiTree&T)//構(gòu)造空二叉樹T{ T=NULL;} Status DestroyBiTree(BiTree&T)//銷毀二叉樹T{ if(!T) returnERROR; DestroyBiTree(T->lchild); //刪除左子樹 DestroyBiTree(T->rchild); //刪除右子樹 free(T); T=NULL; returnOK;}Status CreateBiTree(BiTree&T)//先序建立二叉樹T,空格表示空結(jié)點{ TElemTypech; fflush(stdin); ch=getche(); if(ch=='')T=NULL; else{ T=(BiTree)malloc(sizeof(BiTNode)); if(!T)e*it(OVERFLOW); T->data=ch; //生成頭結(jié)點 CreateBiTree(T->lchild); //構(gòu)造左子樹 CreateBiTree(T->rchild); //構(gòu)造右子樹 } returnOK;}Status CreateBiTree(BiTree&T,char*str,unsignedi=1)//str儲存著二叉樹的層次序列，str[i]=='&'表示結(jié)點不存在//i為當(dāng)前要創(chuàng)立結(jié)點對應(yīng)的數(shù)組序號節(jié)點//由字符數(shù)組str先序建立一棵二叉樹T{ if(str[i]=='&'||i>=strlen(str))T=NULL; //第i個結(jié)點不存在 else{ T=(BiTree)malloc(sizeof(BiTNode)); if(!T)e*it(OVERFLOW); T->data=str[i]; //生成根節(jié)點 CreateBiTree(T->lchild,str,i*2); //構(gòu)造左子樹 CreateBiTree(T->rchild,str,i*2+1); //構(gòu)造右子樹 } returnOK;}Status BiTreeEmpty(BiTreeT)//假設(shè)T為空二叉樹，則返回TRUE，否則返回FALSE{ if(!T) returnTRUE; else returnFALSE;}int BiTreeDepth(BiTreeT) //返回T的深度//利用層次遍歷求深度{ if(!T)return0; BiTree queue[200]; intdep=0; int rear=0,front=0; queue[rear++]=T; while(rear!=front) {T=queue[front++]; if(T->data) { dep++; if(T->lchild)queue[rear++]=T->lchild; if(T->rchild)queue[rear++]=T->rchild; } elsedep--; } returndep;}TElemType Value(BiTreeT,int &k)//返回二叉樹先序遍歷第k個節(jié)點的值，不存在則返回空格''{ if(!T||k<1) return''; if(--k==0&&T) returnT->data; BiTree stack[100],p=T; //定義數(shù)組棧 int top=0,i=-1; //初始化棧頂指針 while(p||top>0) //當(dāng)結(jié)點不空或棧不空 { if(p) {i++; if(i==k) returnp->data; stack[top++]=p; //根指針入棧，遍歷左子樹 p=p->lchild; } else{ //根指針退棧，遍歷右子樹 p=stack[--top]; p=p->rchild; } }}void Assign(BiTreeT,BiTree&p,TElemTypevalue)//二叉樹T存在，e是T中*個結(jié)點//結(jié)點p賦值為value{ if(p)p->data=value;}BiTree LeftChild(BiTreeT,BiTreep)//返回p的左孩子。假設(shè)p無左孩子，則返回“空〞{ returnp->lchild;}BiTree RightChild(BiTreeT,BiTreep)//返回p的右孩子。假設(shè)p無右孩子，則返回“空〞{ returnp->rchild;}Status InsertChild(BiTree&T,BiTree&p,intLR,BiTree&c)//二叉樹T存在，p指向T中*個結(jié)點，LR為0或1，非空二叉樹c與T不相交且右子樹為空。//根據(jù)LR為0或1，插入c為T中p所指向結(jié)點的左或右子樹。//p所指結(jié)點的原有左或右子樹則成為c的右子樹。{ if(!T||!c||!p||(LR!=0&&LR!=1)) returnERROR; //不符合條件 if(LR==0) //插入為左子樹 { c->rchild=p->lchild; p->lchild=c; } if(LR==1) //插入為右子樹 { c->rchild=p->rchild; p->rchild=c; } returnOK;}Status DeleteChild(BiTree&T,BiTree&p,int LR)//p指向T中*個結(jié)點，LR為0或1.//用隊列，根據(jù)LR為0或1，刪除T中P所指結(jié)點的左或右子樹{ if(!T||!p||(LR!=1&&LR!=0)) returnERROR; BiTree queue[200]; //定義數(shù)組隊列 int rear=0,front=0; //初始化隊列的頭指針和尾指針 if(LR==0&&p->lchild) //LR為0且所刪除左孩子存在 { queue[rear++]=p->lchild; //則左孩子入隊 p->lchild=NULL; } if(LR==1&&p->rchild) //LR為1且所刪除右孩子存在 { queue[rear++]=p->rchild; //則右孩子入隊 p->rchild=NULL; } while(rear!=front) //用隊列層次遍歷，刪除所要求的子樹 { p=queue[front++]; if(p->lchild)queue[rear++]=p->lchild; if(p->rchild)queue[rear++]=p->rchild; free(p); } returnOK;}Status PreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)) //非遞歸先序遍歷二叉樹。對每個節(jié)點調(diào)用Visit函數(shù){BiTree stack[100],p=T; //定義數(shù)組棧 int top=0; //初始化棧頂指針 while(p||top>0) //當(dāng)結(jié)點不空或棧不空 { if(p) { if(!Visit(p->data)) //訪問根節(jié)點 returnERROR; stack[top++]=p; //根指針入棧，遍歷左子樹 p=p->lchild; } else{ //根指針退棧，遍歷右子樹 p=stack[--top]; p=p->rchild; } } returnOK;}Status InOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee))//非遞歸中序遍歷二叉樹，對每個節(jié)點調(diào)用Visit。{ BiTree stack[100],p=T; //定義數(shù)組棧 int top=0; //初始化棧頂指針 while(p||top>0) { if(p) //根指針入棧，遍歷左子樹 { stack[top++]=p; p=p->lchild; } else{ //根指針退棧，遍歷右子樹 p=stack[--top]; if(!Visit(p->data)) returnERROR; p=p->rchild; } } returnOK;}Status PostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee))//用棧非遞歸后序遍歷二叉樹T。//與非遞歸先序中序的區(qū)別在于，多定義一visited數(shù)組，用來記錄訪問次數(shù)//第二次訪問時才退棧。{ BiTree stack[100],p=T; //定義數(shù)組棧 int top=0,visited[100]; //初始化棧頂指針與訪問次數(shù)數(shù)組 while(p||top>0) { if(p) //遍歷左子樹，置訪問數(shù)組為第一次訪問 { stack[top++]=p; visited[top-1]=0; p=p->lchild; } else{ if(visited[top-1]==0)//假設(shè)棧頂結(jié)點只訪問一次，遍歷右子樹 { p=stack[top-1]; visited[top-1]++; p=p->rchild; } elseif(visited[top-1]==1)//假設(shè)第二次訪問，則根指針退棧，訪問根節(jié)點。 if(!Visit(stack[--top]->data))returnERROR; } } returnOK;}Status LevelOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee))//用隊列層次遍歷二叉樹T。//對每個結(jié)點調(diào)用函數(shù)Visit一次且