关于二叉排序树的实现

《关于二叉排序树的实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、课程设计报告关于二叉排序树的实现一：需求分析1：基本要求a)以回车('')为输入结束标志,输入数列L，生成一棵二叉排序树T；b)对二叉排序树T作中序遍历，输出结果；c)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；2：设计要求：(1)符合课题要求，实现相应功能；(2)要求界面友好美观，操作方便易行；(3)注意程序的实用性、安全性。3:设计所采用的数据结构1:利用数组思想,通过改变数组指针来表示数组的左右子树,左子树的下标为2*i,右子树的下标为2*i

2、+1.2：树的存储结构如下：#defineN100/*二叉树结点的最大数目*/typedefstruct{int*data;/*数组首址指针*/intlenth;/*数组长度*/}BST;4：每个模块的功能要求:初始化一个数组，开辟一块内存空间，先建立一个插入函数。创建一棵二叉树，中序遍历该树在二叉排序树中查找其关键字等于给定值的结点是否存在删除所给结点，并对新树中序遍历最后，可以判断所给树是否为平衡树二：概要设计1:使用树的动态顺序存储结构，先初始化一个数组。2：建立一个插入函数，通过调用该函数边查找边插入建立二叉排

3、序树3：通过递归调用，中序遍历树，以及判断其是否为平衡树4：q.data=(int*)malloc(N*sizeof(int));/*重新初始化一个数组Q*/新的数组储存删除给定结点的新树5：要实现二叉排序树，要先创建二叉排序树，在以下程序中利用边查找边插入来建立二叉排序树。BSTcreate(int*crew,intnum)/*创建二叉排序树的函数*/{BSTT;inti,j;T.data=(int*)malloc(N*sizeof(int));/*数组初始化*/for(j=0;j

4、;T.lenth=0;for(i=0;i

5、T,intkey)/*删除函数*/{BSTq;inti;q.data=(int*)malloc(N*sizeof(int));/*重新初始化一个链表Q*/for(i=0;i0;i++)/*T中不为要删结点的元素全部复制到Q*/{if(T.data[i]==0

6、

7、T.data[i]==key)continue;insert(q,1,T.data[i]);--T.lenth;++q.lenth;}return(q);}5：判

8、断一棵树是否为平衡二叉树，看其左右子树的高度之差的绝对值是否小于等于1。dep1=balanceBST(T,T.data[2*i],k);dep2=balanceBST(T,T.data[2*i+1],k);}if((dep1-dep2)>1

9、

10、(dep1-dep2)<-1)*k=dep1-dep2;/*用k值记录是否存在不平衡现象*/if(dep1>dep2)return(dep1+1);elsereturn(dep2+1);6：主函数利用switch语句实现不同函数功能的显示。三：详细设计#include

11、o.h>#include#defineN100/*二叉树结点的最大数目*/typedefstruct{int*data;/*数组首址指针*/intlenth;/*数组长度*/}BST;insert(BSTT,inti,intkey)/*插入函数*/{if(i<1

12、

13、i>N)printf("失败!");/*插入不成功*/if(T.data[i]==0)T.data[i]=key;/*被插结点是新的根节点*/elseif(key

14、查找相应位置*/elseif(key>T.data[i])insert(T,2*i+1,key);/*在右子树中继续查找*/}BSTcreate(int*crew,intnum)/*创建二插排序树的函数*/{BSTT;inti,j;T.data=(int*)malloc(N*sizeof(int));/*数组初始化*/for(j=