数据结构实习报告

1、实习报告一：需求分析1 基本要求a) 以回车('n')为输入结束标志,输入数列L，生成一棵二叉排 序树T；b) 对二叉排序树T作中序遍历，输出结果；c) 输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；2 数据类型要实现二叉排序数，必须先定义数据类型，本设计的输入数据为整型，输出的数据也为整型。3 题目功能详细说明 要生成一棵二叉排序数T，元素类型为ElemType 在二叉排序树中查找其关键字等于给定值的结点是否存在 在二叉排序树中插入一个新结点，中序遍历所建二叉排序树，将得到一个按关键字有序的元素序列 二叉排序树

2、的查找，可多次查找，并输出查找的结果4最后对输出结构进行分析二概要分析1.二叉树是另一种树型结构，他的特点是每个结点至多只有两棵子树，并且，二叉树的子树有左右之分，其次序不能任意颠倒。2.二叉树的存储结构/-二叉树的顺序存储表示-#define MAX-TREE-SIZE 100 /二叉树的最大结点数Typedef TELem type sqbitreeMAX-TREE-SIZE;/0号单元存储根结点sqBiTree bt3.在不同的存储结构中,实现二叉树的操作方法也不同,如找结点X的双亲PARENT(T,E),在三叉链表中很容易实现,而在二叉链表中则需从根指针出发巡查.4. if(!t) *

3、p=f;return (0); /*查找不成功*/else if(key=t->data) *p=t;return (1); /*查找成功*/ else if(key<t->data) searchBST(t->lchild,key,t,p); /*在左子树中继续查找*/else searchBST(t->rchild,key,t,p); /*在右子树中继续查找*/5calculateASL(node *t,int *s,int *j,int i) /*计算平均查找长度*/ if(*t) i+; /*i记录当前结点的在当前树中的深度*/ *s=*s+i; /*s记

4、录已遍历过的点的深度之和*/ if(calculateASL(&(*t)->lchild,s,j,i)/*计算左子树的ASL*/三.详细程序#include<stdio.h># include<stdlib.h>typedef struct Tnode int data; /*输入的数据*/ struct Tnode *lchild,*rchild; /*结点的左右指针，分别指向结点的左右孩子*/ *node,BSTnode;searchBST(node t,int key,node f,node *p) /*查找函数*/ if(!t) *p=f;retu

5、rn (0); /*查找不成功*/else if(key=t->data) *p=t;return (1); /*查找成功*/ else if(key<t->data) searchBST(t->lchild,key,t,p); /*在左子树中继续查找*/else searchBST(t->rchild,key,t,p); /*在右子树中继续查找*/insertBST(node *t,int key) /*插入函数*/ node p=NULL,s=NULL; if(!searchBST(*t,key,NULL,&p) /*查找不成功*/ s=(node)m

6、alloc(sizeof(BSTnode); s->data=key; s->lchild=s->rchild=NULL; if(!p) *t=s; /*被插结点*s为新的根结点*/ else if(key<p->data) p->lchild=s;/*被插结点*s为左孩子*/ else p->rchild=s; /*被插结点*s为右孩子*/ return (1); else return (0);/*树中已有关键字一样的结点，不再插入*/ inorderTraverse(node *t) /*中序遍历函数*/ if(*t) if(inorderTra

7、verse(&(*t)->lchild) /*中序遍历根的左子树*/ printf("%d ",(*t)->data); /*输出根结点*/ if(inorderTraverse(&(*t)->rchild); /*中序遍历根的右子树*/ return(1) ; calculateASL(node *t,int *s,int *j,int i) /*计算平均查找长度*/ if(*t) i+; /*i记录当前结点的在当前树中的深度*/ *s=*s+i; /*s记录已遍历过的点的深度之和*/ if(calculateASL(&(*t)-

8、>lchild,s,j,i)/*计算左子树的ASL*/ (*j)+; /*j记录树中结点的数目*/ if(calculateASL(&(*t)->rchild,s,j,i) /*计算右子树的ASL*/ i-; return(1); else return(1); node Delete(node t,int key) /*删除函数*/ node p=t,q=NULL,s,f; while(p!=NULL) /*查找要删除的点*/ if(p->data=key) break; q=p; if(p->data>key) p=p->lchild; else

9、 p=p->rchild; if(p=NULL) return t; /*查找失败*/ if(p->lchild=NULL) /*p指向当前要删除的结点*/ if(q=NULL) t=p->rchild; /*q指向要删结点的父母*/ else if(q->lchild=p) q->lchild=p->rchild; /*p为q的左孩子*/ else q->rchild=p->rchild;/*p为q的右孩子*/ free(p); else /*p的左孩子不为空*/ f=p; s=p->lchild; while(s->rchild)

10、 /*左拐后向右走到底*/ f=s; s=s->rchild; if(f=p) f->lchild=s->lchild; /*重接f的左子树*/ else f->rchild=s->lchild; /*重接f的右子树*/ p->data=s->data; free (s); return t;int balanceBST(node t,int *i) /*判断是否为平衡二叉树的函数*/ int dep1,dep2; if(!t) return(0); else dep1=balanceBST(t->lchild,i); dep2=balanceB

11、ST(t->rchild,i); if(dep1-dep2)>1|(dep1-dep2)<-1) *i=dep1-dep2;/*用i值记录是否存在不平衡现象*/ if(dep1>dep2) return(dep1+1); else return(dep2+1);void main() node T=NULL; int num; int s=0,j=0,i=0; int ch=0; node p=NULL; printf("please input a list of numbers end with zero:"); do scanf("%

12、d",&num); if(!num) printf("you have finished your input!n"); else insertBST(&T,num); while(num); printf("nn-the menu of the opperation-n"); /*主程序菜单*/ printf("n 0: exit" ); printf("n 1: inorder travel the tree"); printf("n 2: the average searc

13、h length for the tree"); printf("n 3: delete"); printf("n 4: judge the balance"); while(ch=ch) printf("n choose the opperation to continue:"); scanf("%d",&ch); switch(ch) case 0: exit(0); /*0退出*/ case 1: printf(" The result of the inorder travers

14、e is:n "); inorderTraverse(&T); /*1中序遍历*/ break; case 2: s=0;j=0;i=0; calculateASL(&T,&s,&j,i); /*2计算平均查找长度*/ printf(" ASL=%d/%d",s,j); break; case 3: printf(" Please input the number you want to delete:"); scanf("%d",&num); /*3删除某个结点*/ if(searc

15、hBST(T,num,NULL,&p) T=Delete(T,num); printf(" You have delete the number successfully!n "); inorderTraverse(&T); else printf(" No node %d you want to delete!",num); break; case 4: i=0; balanceBST(T,&i); /*判断是否为平衡二插树*/ if(i=0) printf(" OK!The tree is a balanced tr

16、ee!"); else printf(" NO!"); break; default: printf("Your input is wrong!please input again!n"); break; /*输入无效字符*/ 四.结果输出112 5 4 1 6 0You have finished your input!-the menu of the opperation-0: exit1: inorder travel the tree2: the average search length for the tree3:delete4:

17、judge the balanceChoose the opperation to continue:1The result of the inorder traverse is:1 4 5 6 113Choose the opperation to continue2ASL=13/5Choose the opperation to continue:3Please input the number you want to delete:6You have delete the number successfully!1 4 5 113Choose the opperation to continue:4NO!Choose the opperation to con