二叉树的存储与遍历实现实验报告

数据结构实验报告实验五学院软件学院班级13级.NET班学号1328624004姓名—振—龙-二叉树的存储与遍历实现实验报告学号1328624004姓名刘振龙时间2014.10.10专业计算机科学与技术班级.Net实验题目：二叉树的存储与遍历的实现一、 实验目的：了解二叉树的存储与遍历的运算算法的实现；分析算法的空间复杂度和插入和删除及遍历的时间复杂度；3•总结二叉树顺序存储与遍历的特点。了解二叉树的基本操作在顺序存储上的实现和遍历上的实现；以二叉树的各种操作(建立、插入、删除和遍历等)；掌握二叉树顺序存储结构的定义和基本操作的实现；二、 实验分析：(1).二叉树的顺序存储的实现。Q建立一个二叉树(先中后都可)，@在演示过程中必须按ENTER键，方可看到运行结果。@(1)本实验建立一个中序二叉树；(2)进行二叉树的遍历。二.概要设计1•二叉树的存储：ADTTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；若D中仅含一个数据元素，则关系R为空集；否则R={H},H是如下二元关系：在D中存在唯一的称为根的数据元素root,它在关系H下无前驱；若D-{root}丰0,则存在D-{root}的一个划分D,D,D,-,D(m>0)，即对于任意的jHk(1Wj,KWin)有DPD=0,且对任意的i=1,2,…,m。惟一存在数据元素xGD,有<ro0t,x\eii iH；3)对应于D-{root}的以上划分，H-{<root,x>,<root,x>,…，<root,x>}有惟一的一个划分H电，H,…,H(m>0)，即对于任意的jHk(1Wj,kWm)有HPH=，且对

任意的”i(1WiWm)，H是D上的二元关系，(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{//结点结构TElemType data;struetTriTNode*lchild,*rch订d; //左右孩子指针structTriTNode*parent;//双亲指针}TriTNode,*TriTree;2.#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0号单元存储根结点SqBiTreebt;voidPreOrderTraverse但iTreeT,void(*visit)(TEIemTypee)){//先序遍历二叉树if(T){visit(T->data); //访问根结点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); //访问根结点1:InOrderTraverse(T->rchild,visit);〃中序遍历右子树}//2:}//InOrderTraversevoidLevelOrderTraverse(BiTreeT,Status(*viste)(TElemTypee)){//按层次遍历二叉链表存储的二叉树if(T){InitQueue(Q);//初始化一个队列EnQueue(Q,T);〃根进队列while(!QueueEmpty(Q)){DelQueue(Q,P);viste(p->data);〃访问if(P->lchild)EnQueue(Q,P->lchild);//左孩子进队列if(P->rchild)EnQueue(Q,P->rchild);//右孩子进队列}//while}//if}//LevelOrderTraverse三实验步骤(包括主要步骤、代码分析等)#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();遍遍遍-主中匚程择归归归出述递递递退月皂训，空树个臭二一工遍遍遍朿>结亡一车回n=n<◎54F遍遍遍-主中匚程择归归归出述递递递退月皂训，空树个臭二一工遍遍遍朿>结亡一车回n=n<◎54F3G2ffil:lM6B可匯段更翦：递归先序、中序、后序遍历。元"5111/-fL1的树厅叉遍二人择归归归出立屠递递递退是请请」23.0.i労归中序谎历二又桥:CBEGDFA逸归先丿予逓丿力一乂校油BCEEGF<>1>：8依次输耳个权值〔整型)：64378119父值为5的圭逍的编码为：0佃巫宿知的学裳的编刃为：血父匿为4的宇卷的编码为:询1父值为3的宇备的编谒为江血0曳値为?的宇笹的编码^=100及值为8的学徒的编码为江価巫隹知讷字苻餡編码^1：00MS为咿字符的编刃为心1vessanukeytocontinue四.体验分析：(1)本次实验是完成二叉树的存储和遍历，通过本次实验我学会了如何建立一个二叉树的存储及遍历，存储为顺序遍历分为先中后三次遍历，本次试验中先完成了建立即存储，儿后依次完成了三