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

中国矿业大学徐海学院计算机系软件认知实践报告姓 名： 张鹏 学 号： 22100479 姓 名： 陆陈坤 学 号： 22100470 专 业： 计算机科学与技术 设计题目： 二叉排序树的实现 指导教师： 孙锦程 2011年12月目 录第1章 题目概述1第1.1节 题目要求1第1.2节 主要难点1第2章 系统流程图2第3章 数据结构和算法3第4章 核心代码分析9第5章 复杂度分析10中国矿业大学徐海学院软件认知实践报告第1章 题目概述用顺序和二叉链表作存储结构实现二叉排序树。第1.1节 题目要求1)以回车(n)为输入结束标志,输入数列L，生成一棵二叉排序树T；2)对二叉排序树T作中序遍历，输出结果；3)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；第1.2节 主要难点1: 使用树的动态顺序存储结构，先初始化一个数组。2：建立一个插入函数，通过调用该函数边查找边插入建立二叉排序树。3：q.data=(int *)malloc(N*sizeof(int); /*重新初始化一个数组Q*/第2章 系统流程图下一页NYprintf(输入完成n);crewi=num; i+;if(num= =-1)While(num!=-1)scanf(%d,&num);BST T; int crewN; int i=0; int k=0; int num,ch=0,j; printf(请输入一串数字，以数字-1结束:);Main()开始Switch(ch)NNYNNYbreak;输出：输入的字符无效Default:判断是否为平衡二叉树break;break;删除元素break;中序遍历二叉树Case(2)Case(3)Case(1)Case(0)结束YYExit(0);N T=create(crew,i); printf(nn*操作选项*);printf(n* *); printf(n* 0: 退出 *); printf(n* 1: 中序遍历二叉排序树 *); printf(n* 2: 删除元素 *); printf(n* 3: 判断是否为平衡树 *);printf(n*);+第3章 数据结构和算法#include#include#define N 100 /*二叉树结点的最大数目*/typedef struct int *data; /*数组首址指针*/ int lenth; /*数组长度*/BST;insert(BST T,int i,int key) /*插入函数*/ if(iN) printf(失败!); /*插入不成功*/ if(T.datai=0) T.datai=key; /*被插结点是新的根结点*/ else if(keyT.datai) insert(T,2*i+1,key); /*在右子树中继续查找*/BST create(int *crew,int num) /*创建二叉排序树的函数*/ BST T; int i,j; T.data=(int *)malloc(N*sizeof(int); /*数组初始化*/ for(j=0;jN;j+) T.dataj=0; T.lenth=0; for(i=0;inum;i+) /*边查找边插入建立二叉排序树*/ insert(T,1,crewi); +T.lenth; /*记录树中结点的个数*/ return (T);inordertraverse(BST T,int i) /*中序遍历函数*/ if(T.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(keyT.datai) search(T,key,2*i);/*在左子树中继续查找*/ else search(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;iN;i+) q.datai=0; q.lenth=0; for(i=1;i0;i+)/*T中不为要删结点的元素全部复制到Q*/ if(T.datai=0|T.datai=key) continue; insert(q,1,T.datai); -T.lenth; +q.lenth; return(q); int balanceBST(BST T,int i,int *k) /*判断是否为平衡二叉树的函数*/ int dep1,dep2; if(!T.datai)return(0); else dep1=balanceBST(T,T.data2*i,k); dep2=balanceBST(T,T.data2*i+1,k); if(dep1-dep2)1|(dep1-dep2)dep2) return(dep1+1); else return(dep2+1);void main() BST T; int crewN; int i=0; int k=0; int num,ch=0,j; printf(请输入一串数字，以数字-1结束:); do scanf(%d,&num); if(num=-1) printf(输入完成n); else crewi=num; i+; while(num!=-1); T=create(crew,i); printf(nn*操作选项*);printf(n* *);/*主程序菜单*/ printf(n*0: 退出 *); printf(n*1: 中序遍历二叉排序树 *); printf(n*2: 删除元素 *); printf(n*3: 判断是否为平衡树 *); printf(n*); while(ch=ch) printf(n 选择您要进行的操作:); scanf(%d,&ch); switch(ch) case 0: exit(0); /*0退出*/ case 1: printf( 中序遍历二叉排序树的结果:n ); inordertraverse(T,1);/*1中序遍历*/ break; case 2: printf( 请输入你要删除的数字:); scanf(%d,&num); /*3删除某个结点*/ j=search(T,num,1); if(j) T=cancle(T,num); printf( 删除成功!n ); inordertraverse(T,1); i-; else printf( 你要删除的结点不存在!,num); break;case 3: k=0; balanceBST(T,i,&k); if(k=0) printf(是平衡树);else printf(不是平衡树); break; default: printf(输入字符无效，请重新选择!n); break; /*输入无效字符*/ 第4章 核心代码分析insert(BST T,int i,int key) /*插入函数*/ if(iN) printf(失败!); /*插入不成功*/ if(T.datai=0) T.datai=key; /*被插结点是新的根结点*/ else if(keyT.