关于二叉排序树的实现.docx

课程设计报告关于二叉排序树的实现一：需求分析1：基本要求以回车(\n)为输入结束标志,输入数列L，生成一棵二叉排 序树T；对二叉排序树T作中序遍历，输出结果；输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；2：设计要求：(1) 符合课题要求，实现相应功能；(2) 要求界面友好美观，操作方便易行；(3) 注意程序的实用性、安全性。3:设计所采用的数据结构1:利用数组思想,通过改变数组指针来表示数组的左右子树,左子树的下标为2*i,右子树的下标为2*i+1. 2：树的存储结构如下：#define N 100 /*二叉树结点的最大数目*/typedefstruct{int *data; /*数组首址指针*/intlenth; /*数组长度*/}BST;4：每个模块的功能要求: 初始化一个数组，开辟一块内存空间，先建立一个插入函数。 创建一棵二叉树，中序遍历该树在二叉排序树中查找其关键字等于给定值的结点是否存在删除所给结点，并对新树中序遍历最后，可以判断所给树是否为平衡树二：概要设计1:使用树的动态顺序存储结构，先初始化一个数组。2：建立一个插入函数，通过调用该函数边查找边插入建立二叉排序树3：通过递归调用，中序遍历树，以及判断其是否为平衡树4：q.data=(int *)malloc(N*sizeof(int)); /*重新初始化一个数组Q*/新的数组储存删除给定结点的新树5：要实现二叉排序树，要先创建二叉排序树，在以下程序中利用边查找边插入来建立二叉排序树。BST create(int *crew,int num) /*创建二叉排序树的函数*/{ BST T;inti,j;T.data=(int *)malloc(N*sizeof(int)); /*数组初始化*/for(j=0;jN;j++) T.data[j]=0;T.lenth=0; for(i=0;inum;i++) /*边查找边插入建立二插排序树*/ {insert(T,1,crew[i]); ++T.lenth; /*记录树中结点的个数*/ }return (T);}在这个过程中，调用了已经建立的函数insert(T,1,crew[i]); 为新结点查找到相应的位置，将其插入树中。6：中序遍历二叉排序树的结果应该是一列从小到大排列的数7：在删除函数中，要保证删除后得到的二叉树依然是二叉排序树，在下列程序中是利用重建一个新的二叉树，将不删除的元素复制到该树中。BST cancle(BST T,int key) /*删除函数*/{ BST q;inti;q.data=(int *)malloc(N*sizeof(int)); /*重新初始化一个链表Q*/for(i=0;iN;i++) q.data[i]=0;q.lenth=0; for(i=1;iNT.lenth0;i++)/*T中不为要删结点的元素全部复制到Q*/ {if(T.data[i]==0||T.data[i]==key) continue;insert(q,1,T.data[i]); --T.lenth; ++q.lenth; }return(q);}5：判断一棵树是否为平衡二叉树，看其左右子树的高度之差的绝对值是否小于等于1。 dep1=balanceBST(T,T.data[2*i],k); dep2=balanceBST(T,T.data[2*i+1],k); }if((dep1-dep2)1||(dep1-dep2)-1) *k=dep1-dep2;/*用k值记录是否存在不平衡现象*/if(dep1dep2) return(dep1+1);else return(dep2+1);6：主函数利用switch语句实现不同函数功能的显示。三：详细设计#includestdio.h#includestdlib.h#define N 100 /*二叉树结点的最大数目*/typedefstruct{int *data; /*数组首址指针*/intlenth; /*数组长度*/}BST;insert(BST T,inti,int key) /*插入函数*/{ if(i1||iN) printf(失败!); /*插入不成功*/ if(T.data[i]==0) T.data[i]=key; /*被插结点是新的根节点*/ else if(keyT.data[i]) insert(