《软件认知实践》-二叉排序树

1、国矿业大学徐海学院计算机系软件认知实践报告名:张鹏 学号：22100479名:陆陈坤 学 号： 22100470业:计算机科学与技术孙锦程二叉排序树的实现指导教师:2011年12月第 1 章 题目概述第 1.1 节 题目要求系统流程图第 1.2 节 主要难点 第2章第3章数据结构和算法第4章核心代码分析第5章复杂度分析10中国矿业大学徐海学院软件认知实践报告第1章题目概述用顺序和二叉链表作存储结构实现二叉排序树。第1.1节题目要求1) 以回车('n')为输入结束标志,输入数列L,生成一棵二叉排序树T;2) 对二叉排序树T作中序遍历，输出结果；3) 输入元素X,查找二叉排序树T,

2、若存在含x的结点,则删除该结点，并作中 序遍历(执行操作2);否则输出信息“无X”；第1.2节主要难点1:使用树的动态顺序存储结构，先初始化一个数组。2:建立一个插入函数，通过调用该函数边查找边插入建立二叉排序树。3： q.data=(int *)malloc(N*sizeof(int); /*重新初始化一个数组 Q*/10第2章系统流程图NCase(O)NCase(1)NCase(2)NCase(3)Default:/Switch(ch)YExit(0);结束、A.结束丿Y中序遍历二叉树break;Y删除兀素break;iY判断是否为平衡二叉树rbreak;1输出：输入的字符无效kbreak

3、;41FT=create(crew,i);+printf("nn*作选*")prin tf("n*");prin tf("n*0:退出*");prin tf("n*1:中序遍历二叉排序树*");prin tf("n*2:删除元素*");prin tf("n*3:判断是否为平衡树*");printf("n*");第3章数据结构和算法#i ncludevstdio.h>#defi neN 100/*二叉树结点的最大数目typ edefstructint*

4、data; /*数组首址指针*/intlen th;/*数组长度*/#in clude<stdlib.h>BST;*/insert(BST T,int i,int key)/* 插入函数 */if(i<1|i>N)printf("失败!"); /* 插入不成功 */if(T.datai=0) T.datai=key; /* 被插结点是新的根结点 */else if(key<T.datai) insert(T,2*i,key); /* 在左子树中继续查找相应位置*/else if(key>T.datai) insert(T,2*i+1,ke

5、y); /* 在右子树中继续查找 */BST create(int *crew,int num) /* 创建二叉排序树的函数 */ BST T;int i,j;T.data=(int *)malloc(N*sizeof(int); /* 数组初始化 */ for(j=O;jvN;j+) T.dataj=0;T.le nth=O;for(i=0;i<num;i+)/*边查找边插入建立二叉排序树*/in sert(T,1,crewi);+T.lenth;/*记录树中结点的个数*/return (T);inordertraverse(BST T,int i) /* 中序遍历函数 */ if(T

6、.datai)inordertraverse(T,2*i); /*中序遍历根的左子树*/printf("%d",T.datai); /* 输出根结点 */ inordertraverse(T,2*i+1);/* 中序遍历根的右子树 */int search(BST T,int key,int i)/* 查找函数 */if(!T.datai) return(0); /* 查找不成功 */else if(key=T.datai) return(i);/* 查找成功 */else if(key<T.datai) search(T,key,2*i);/* 在左子树中继续查找

7、*/elsesearch(T,key,2*i+1); /*在右子树中继续查找 */ BST cancle(BST T,int key) /*删除函数 */BST q;int i;q.data=(int *)malloc(N*sizeof(int); /* 重新初始化一个数组 Q*/for(i=0;ivN;i+)q.datai=O;q.le nth=0;for(i=1;i<N&&T.le nth>0;i+)/*T中不为要删结点的元素全部复制到 Q*/if(T.datai=0|T.datai=key) continue;in sert(q,1,T.datai);-T.l

8、e nth;+q.le nth;return(q);int balanceBST(BST T,int i,int *k)/*判断是否为平衡二叉树的函数*/ int dep 1,de p2;if(!T.datai)return(O);elsedep 仁bala nceBST(T,T.data2*i,k);dep 2=bala nceBST(T,T.data2*i+1,k);if(dep1-dep2)>1|(dep1-dep2)v-1) *k=dep1-dep2;/*用 k值记录是否存在不平衡现象*/if(de p1>de p2) retum(de p1+1);elseretur n(

9、dep 2+1);void main()BSTT;intintcrewN; i=0; int k=0;intnu m,ch=0,j;printf（"请输入一串数字，以数字-1结束:"）;doscan f("%d",&nu m);if(num=-1)printf("输入完成 n");else crewi=num; i+; while( nu m!=-1); T=create(crew,i);printf ("nn*操作选*"prin tf("n*");/* 主程序菜单*/prin tf(&

10、quot;n*0:退出*");prin tf("n*1:中序遍历二叉排序树*");prin tf("n*2:删除元素*");prin tf("n*3:判断是否为平衡树*");printf ("n*");while(ch=ch)printf（"n选择您要进行的操作:"）;scan f("%d",&ch); switch(ch)case 0: exit(0);/*0 退出 */case 1:case 2:printf（"中序遍历二叉排序树的结果：n&q

11、uot;）;inordertraverse(T,1);/*1中序遍历 */break;printf（"请输入你要删除的数字："）;scanf("%d",&num);/*3 删除某个结点 */j=search(T, nu m,1); if(j)T=ca ncle(T ,nu m);printf("删除成功!n");ino rdertraverse(T,1);else printf（" 你要删除的结点不存在!",num）;break;case 3: k=0;bala nceBST(T,i,&k); if

12、(k=O)printf("是平衡树");else printf（"不是平衡树"）;break;default:printf（"输入字符无效，请重新选择！n"）;break; /*输入无效字符*/第4章核心代码分析insert(BST T,int i,int key)/* 插入函数 */if(i<1|i>N)printf("失败!"); /* 插入不成功 */if(T.datai=0) T.datai=key; /* 被插结点是新的根结点 */else if(key<T.datai) insert(T,2*i,key); /*在左子树中继续查找相应位置*/else if(key>T.datai) insert(T,2*i+1,key); /* 在右子树中继续查找 */本程序将输入的数字写进数组，以数组的第2*i作为结点的左孩子的值，2*i+1 作为结点的右孩子的值。本程序运行结果如下图：書燹磊串数字，以数字士吉聿;右45 3 42 67 5 66 1Z -1初寸舉作选项MMWMK萬KKKK萬耳*退出中遍历二叉排序材 fl#