二叉樹的存儲(chǔ)與遍歷實(shí)現(xiàn)實(shí)驗(yàn)報(bào)告

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)五學(xué)院軟件學(xué)院班級(jí)13級(jí).NET班學(xué)號(hào)1328624004姓名—振—龍-二叉樹的存儲(chǔ)與遍歷實(shí)現(xiàn)實(shí)驗(yàn)報(bào)告學(xué)號(hào)1328624004姓名劉振龍時(shí)間2014.10.10專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)班級(jí).Net實(shí)驗(yàn)題目：二叉樹的存儲(chǔ)與遍歷的實(shí)現(xiàn)一、 實(shí)驗(yàn)?zāi)康模毫私舛鏄涞拇鎯?chǔ)與遍歷的運(yùn)算算法的實(shí)現(xiàn)；分析算法的空間復(fù)雜度和插入和刪除及遍歷的時(shí)間復(fù)雜度；3?總結(jié)二叉樹順序存儲(chǔ)與遍歷的特點(diǎn)。了解二叉樹的基本操作在順序存儲(chǔ)上的實(shí)現(xiàn)和遍歷上的實(shí)現(xiàn)；以二叉樹的各種操作(建立、插入、刪除和遍歷等)；掌握二叉樹順序存儲(chǔ)結(jié)構(gòu)的定義和基本操作的實(shí)現(xiàn)；二、 實(shí)驗(yàn)分析：(1).二叉樹的順序存儲(chǔ)的實(shí)現(xiàn)。Q建立一個(gè)二叉樹(先中后都可)，@在演示過程中必須按ENTER鍵，方可看到運(yùn)行結(jié)果。@(1)本實(shí)驗(yàn)建立一個(gè)中序二叉樹；(2)進(jìn)行二叉樹的遍歷。二.概要設(shè)計(jì)1?二叉樹的存儲(chǔ)：ADTTree{數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D為空集，則稱為空樹；若D中僅含一個(gè)數(shù)據(jù)元素，則關(guān)系R為空集；否則R={H},H是如下二元關(guān)系：在D中存在唯一的稱為根的數(shù)據(jù)元素root,它在關(guān)系H下無(wú)前驅(qū)；若D-{root}豐0,則存在D-{root}的一個(gè)劃分D,D,D,-,D(m>0)，即對(duì)于任意的jHk(1Wj,KWin)有DPD=0,且對(duì)任意的i=1,2,…,m。惟一存在數(shù)據(jù)元素xGD,有<ro0t,x\eii iH；3)對(duì)應(yīng)于D-{root}的以上劃分，H-{<root,x>,<root,x>,…，<root,x>}有惟一的一個(gè)劃分H電，H,…,H(m>0)，即對(duì)于任意的jHk(1Wj,kWm)有HPH=，且對(duì)

任意的”i(1WiWm)，H是D上的二元關(guān)系，(D,H)是一棵符合本

定義的樹，稱為根root的子樹。lnitBiTree(&T);DestroyBiTree(&T);BiTreeEmpty(T);CreateBiTree(&T,definition);BiTreeDepth(T);Value(T,e);ClearBiTree(&T);DeleteChild(T,p,LR); Root(T);Assign(T,&e,value); InsertChild(T,p,LR,c);Parent(T,e); LeftChild(T,e); RightChild(T,e);LeftSibling(T,e); RightSibling(T,e);PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());typedefstructTriTNode{//結(jié)點(diǎn)結(jié)構(gòu)TElemType data;struetTriTNode*lchild,*rch訂d; //左右孩子指針structTriTNode*parent;//雙親指針}TriTNode,*TriTree;2.#defineMAX_TREE_SIZE100//二叉樹的最大結(jié)點(diǎn)數(shù)typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)SqBiTreebt;voidPreOrderTraverse但iTreeT,void(*visit)(TEIemTypee)){//先序遍歷二叉樹if(T){visit(T->data); //訪問根結(jié)點(diǎn)PreOrderTraverse(T->lehild,visit);//先序遍歷左子樹PreOrderTraverse(T->rehild,visit);〃先序遍歷右子樹}}voidPreOrderTraverse(BiTreeT,void(*visit)(TElemType e)){//先序遍歷二叉樹的非遞歸算法InitStack(S); push(S,T);while(!StackEmpty(S)){while(GetTop(S,P)&&P){visit(P->data);push(S,P->lchild);}pop(S,P);if(!StackEmpty(S)){pop(S,P);push(S,P->rchild);}//if}//while}//PreOrderTraversevoidInOrderTraverse(BiTreeT,void(*visit)(TElemType e)){//中序遍歷二叉樹if⑴{InOrderTraverse(T->lchild,visit);//中序遍歷左子樹visit(T->data); //訪問根結(jié)點(diǎn)1:InOrderTraverse(T->rchild,visit);〃中序遍歷右子樹}//2:}//InOrderTraversevoidLevelOrderTraverse(BiTreeT,Status(*viste)(TElemTypee)){//按層次遍歷二叉鏈表存儲(chǔ)的二叉樹if(T){InitQueue(Q);//初始化一個(gè)隊(duì)列EnQueue(Q,T);〃根進(jìn)隊(duì)列while(!QueueEmpty(Q)){DelQueue(Q,P);viste(p->data);〃訪問if(P->lchild)EnQueue(Q,P->lchild);//左孩子進(jìn)隊(duì)列if(P->rchild)EnQueue(Q,P->rchild);//右孩子進(jìn)隊(duì)列}//while}//if}//LevelOrderTraverse三實(shí)驗(yàn)步驟(包括主要步驟、代碼分析等)#include<stdio.h>#include<stdary.h>#defineMAXSIZE100typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;BiTreeCreateBiTree(){BiTreeT;charch=getchar();if(ch=='#')T=NULL;else{T=(BiTNode*)malloc(sizeof(BiTNode));T->data=ch;T->lchild=CreateBiTree();T->rchild=CreateBiTree();}returnT;}〃遞歸生成二叉樹，用#代表空子樹voidpreorder(BiTreet){if(t){printf("%c”,t->data);preorder(t->lchild);preorder(t->rchild);}}〃遞歸先序遍歷voidInorder(BiTreeT){if(T){Inorder(T->lchild);printf("%c",T->data);Inorder(T->rchild);}}〃遞歸中序遍歷voidpostorder(BiTreet){if(t){preorder(t->lchild);preorder(t->rchild);printf("%c",t->data);}}〃遞歸后序遍歷voidNInorder(BiTreeT){BiTreestack[MAXSIZE];BiTreep=T;inttop=-1;while(plltop!=-l)if(P){top++;stack[top]=p;p=p->lchild;}else{p=stack[top];top--;printf("%c",p->data);p=p->rchild;}}}〃非遞歸中序遍歷main(){BiTreeT;printf("pleaseinputthetree:");T=CreateBiTree();printf("\n");getch();printf("thetreeafterpreorderis:");preorder(T);printf("\n");getch();printf("thetreeafterineorderis:");Inorder(T);printf("\n");getch();printf("thetreeafterpostorderis:");postorder(T);printf("\n");

getch();printf("thetreeafternoinorderis:");Nlnorder(T);printf("\n");getch();遍遍遍-主中匚程擇歸歸歸出述遞遞遞退月皂訓(xùn)，空樹個(gè)臭二一工遍遍遍朿>結(jié)亡一車回n=n<◎54F遍遍遍-主中匚程擇歸歸歸出述遞遞遞退月皂訓(xùn)，空樹個(gè)臭二一工遍遍遍朿>結(jié)亡一車回n=n<◎54F3G2ffil:lM6B可匯段更翦：遞歸先序、中序、后序遍歷。元"5111/-fL1的樹廳叉遍二人擇歸歸歸出立屠遞遞遞退是請(qǐng)請(qǐng)」23.0.i労歸中序謊歷二又橋:CBEGDFA逸歸先丿予逓丿力一乂校油BCEEGF<>1>：8依次輸耳個(gè)權(quán)值〔整型)：64378119父值為5的圭逍的編碼為：0佃巫宿知的學(xué)裳的編刃為：血父匿為4的宇卷的編碼為:詢1父值為3的宇備的編謁為江血0曳値為?的宇笹的編碼^=100及值為8的學(xué)徒的編碼為江価巫隹知訥字苻餡編碼^1：00MS為咿字符的編刃為心1vessanukeytocontinue四.體驗(yàn)分析：(1)本次實(shí)驗(yàn)是完成二叉樹的存儲(chǔ)和遍歷，通過本次實(shí)驗(yàn)我學(xué)會(huì)了如何建立一個(gè)二叉樹的存儲(chǔ)及遍歷，存儲(chǔ)為順序遍歷分為先中后三次遍歷，本次試驗(yàn)中先完成了建立即存儲(chǔ)，兒后依次完成了三