数据结构实验报告精选.docx

数据结构实验报告

第一篇：数据结构实验报告数据结构实验报告一．题目要求1）编程实现二叉排序树，包括生成、插入，删除；2）对二叉排序树进行先根、中根、和后根非递归遍历；3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么?二．解决方案对于前三个题目要求，我们用一个程序实现代码如下#include#include#include#include“Stack.h”//栈的头文件，没有用上typedefintElemType;//数据类型typedefintStatus;//返回值类型//定义二叉树结构typedefstructBiTNode{ElemTypedata;structBiTNode*lChild,*rChild;//左右子树域}BiTNode,*BiTree;intInsertBST(BiTree&T,intkey){//插入二叉树函数if(T==NULL){T=(BiTree)malloc(sizeof(BiTNode));T->data=key;T->lChild=T->rChild=NULL;return1;}elseif(keydata){InsertBST(T->lChild,key);}elseif(key>T->data){InsertBST(T->rChild,key);}elsereturn0;}BiTreeCreateBST(inta[],intn){//创建二叉树函数BiTreebst=NULL;inti=0;while(i//数据域InsertBST(bst,a[i]);i++;}returnbst;}intDelete(BiTree&T){BiTreeq,s;}if(!(T)->rChild){//右子树为空重接它的左子树q=T;T=(T)->lChild;free(q);}else{if(!(T)->lChild){//若左子树空则重新接它的右子树q=T;T=(T)->rChild;}else{q=T;s=(T)->lChild;while(s->rChild){q=s;s=s->rChild;}(T)->data=s->data;//s指向被删除结点的前驱if(q!=T)q->rChild=s->lChild;elseq->lChild=s->lChild;free(s);}}return1;//删除函数，在T中删除key元素intDeleteBST(BiTree&T,intkey){if(!T)return0;else{if(key==(T)->data)returnDelete(T);else{if(keydata)returnDeleteBST(T->lChild,key);elsereturnDeleteBST(T->rChild,key);}}}intPosttreeDepth(BiTreeT){//求深度inthr,hl,max;if(!T==NULL){hl=PosttreeDepth(T->lChild);hr=PosttreeDepth(T->rChild);max=hl>hr?hl:hr;returnmax+1;}elsereturn0;}voidprinttree(BiTreeT,intnlayer){//打印二叉树if(T==NULL)return;printtree(T->rChild,nlayer+1);for(inti=0;i”);}printf(“%dn”,T->data);printtree(T->lChild,nlayer+1);}voidPreOrderNoRec(BiTreeroot)//先序非递归遍历{BiTreep=root;BiTreestack[50];intnum=0;while(NULL!=p||num>0){while(NULL!=p){printf(“%d”,p->data);stack[num++]=p;p=p->lChild;}num--;p=stack[num];p=p->rChild;}printf(“n”);}voidInOrderNoRec(BiTreeroot)//中序非递归遍历{BiTreep=root;}intnum=0;BiTreestack[50];while(NULL!=p||num>0){while(NULL!=p){stack[num++]=p;p=p->lChild;}num--;p=stack[num];printf(“%d”,p->data);p=p->rChild;}printf(“n”);voidPostOrderNoRec