二叉排序树与平衡二叉树的实现

1/18课程设计报告设计题目：二叉排序树与平衡二叉树的实现专业班级学生学号指导教师起止时间年学期2/18目录1.需求分析：........................................31.1课程设计题目、任务及要求：.........31.2课程设计思想：.................................32.概要设计：........................................52.1二叉排序树的定义：.........................52.2二叉排序的存储结构：.....................52.3模块划分：.........................................52.4主函数流程图：.................................63.详细设计和代码：..............................83.1二叉链表：.........................................83.2顺序表：...........................................144.心得与体会：...................................183/181.需求分析：1.1课程设计题目、任务及要求：用二叉链表作存储结构：(1)以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；(2)对二叉排序树T作中序遍历，输出结果；(3)计算二叉排序树T查找成功的平均查找长度,输出结果；(4)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；用顺序表(一维数组)作存储结构：(1)以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；(2)对二叉排序树T作中序遍历,输出结果；(3)计算二叉排序树T查找成功的平均查找长度,输出结果；(4)输入元素x,查找二叉排序树T:若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；1.2课程设计思想：生成二叉排序树：建立二叉排序树采用的是边查找边插入的方式。查找函数采用递归的方式进行查找。查找是按照二叉排序树的性质进行的，通过比较4/18要插入元素的关键字与当前结点关键字的大小来决定我们是遍历当前结点的哪个子树。如果小于当前结点关键字，则遍历它的左子树；大于当前结点关键字，则遍历它的右子树；等于当前关键字，则此元素不插入原树。我们按照这样的规律，一直向下遍历，知道它的子树为空，则返回当前结点的上一个结点。然后利用插入函数将该元素插入原树。中序遍历：对二叉排序树进行中序遍历采用递归函数的方式。在根节点不为空的情况下，先访问左子树，在访问根结点，最后访问右子树。平均查找长度：计算二叉排序树的平均查找长度，仍采用类似中序遍历的递归方式，用s记录总查找长度，j记录每个结点的查找长度，s置初值为0，采用累加的方式最终得到总查找长度s，平均查找长度就等于s/j（i为树中结点的总个数）。删除结点：删除结点函数，采用边查找变删除的方式。如果没有查找到，则不对树做任何的修改：如果查找到结点，则分四种情况分别进行讨论：（1）该结点左右子树均为空；（2）该结点仅左子树为空；（3）该结点仅右子树为空；（4）该结点左右子树都不为空；5/182.概要设计：2.1二叉排序树的定义：二叉排序树是一种动态树表。二叉排序树的定义：二叉排序树或者是一棵空树，或者是一棵具有如下性质的二叉树：（1）每个结点都有一个作为搜索依据的关键字（key），所有结点的关键字互不相同。（2）若它的左子树非空，则左子树上所有结点的值均小于根节点的值；（3）若它的右子树非空，则右子树上所有结点的值均大于根节点的值；（4）左、右子树本身又各是一棵二叉排序树。2.2二叉排序的存储结构：二叉链表：建二叉树的结点应该包含三个域，分别存放结点的数据域data。左孩子结点指针leftChild和右孩子结点指针rightChild。顺序表：顺序表中应该包含一个数组指针（动态申请空间）和一个记录数组长度的size。2.3模块划分：二叉链表：6/18mian():主函数模块。在主函数模块中调用一下函数：（1）intInsert(BiTreeNode**root,intitem):插入函数；（2）intSearch(BiTreeNode*root,intitem)：查找函数；（3）voidInorderTraverse(BiTreeNode*root)：中序遍历输出函数；（4）BiTreeNode*Delete(BiTreeNode*root,intx)：删除函数；顺序表：main()：主函数模块。在主函数模块中调用以下函数：（1）voidInsert(BSTT,inti,intkey)：插入函数；（2）BSTCreate(int*data,intnum)：生成顺序表BST；（3）voidInorderTraverse(BSTT,inti)：中序遍历显示函数；（4）intSearch(BSTT,intkey,inti)：查找函数；（5）BSTDelete(BSTT,intkey)：删除函数；（6）computeASL(BSTT,inti,int*s,intj)：计算平均查找长度函数。2.4主函数流程图：7/18回车（’\\n’）为输入结束标志生成二叉排序树T，调用Insert（）；开始调用menu函数显示菜单输入choice=1实现中序遍历，输入输入choice=2计算二叉排序树的平均长度输入choice=3输入你要删除的元素x8/183.详细设计和代码：3.1二叉链表：源程序：intInsert(BiTreeNode**root,intitem)//插入{BiTreeNode*current,*parent=NULL,*p;current=*root;while(current!=NULL){if(current-data==item)return0;parent=current;if(current-dataitem)current=current-rightChild;elsecurrent=current-leftChild;}元素是否存在删除此元素，然后再输出中序遍历的结果输入choice=0结束输入此二叉排序树无元素xNY9/18p=(BiTreeNode*)malloc(sizeof(BiTreeNode));if(p==NULL){printf(空间不够！);exit(1);}p-data=item;p-leftChild=NULL;p-rightChild=NULL;if(parent==NULL)*root=p;elseif(itemparent-data)parent-leftChild=p;elseparent-rightChild=p;return1;}intSearch(BiTreeNode*root,intitem){BiTreeNode*p;if(root!=NULL){p=root;while(p!=NULL){if(p-data==item)return1;if(itemp-data)p=p-rightChild;elsep=p-leftChild;}}return0;}voidInorderTraverse(BiTreeNode*root)//中序遍历显示{if(root==NULL)return;10/18if(root-leftChild!=NULL)InorderTraverse(root-leftChild);printf(%d,root-data);if(root-rightChild!=NULL)InorderTraverse(root-rightChild);}BiTreeNode*Delete(BiTreeNode*root,intx)//删除操作{BiTreeNode*s,*curr,*f,*q;intflag=0;curr=root;while((curr!=NULL)&&(!flag))//找到要删除的结点{if(curr-data==x)flag=1;elseif(xcurr-data){f=curr;//记住双亲的指针curr=curr-leftChild;}else{f=curr;curr=curr-rightChild;}}if(flag){if(curr-leftChild==NULL&&curr-rightChild==NULL)//左右子树都为空{if(curr==root){free(curr);root=NULL;}else{11/18if(curr==f-leftChild){free(curr);f-leftChild=NULL;}else{free(curr);f-rightChild=NULL;}}}elseif(curr-leftChild==NULL&&curr-rightChild!=NULL)//左子树为空{if(curr==root){root=curr-rightChild;free(curr);}else{s=curr-rightChild;if(curr==f-leftChild)//判断要删除结点是双亲结点的左子树还是右子树f-leftChild=s;elsef-rightChild=s;free(curr);}}elseif(curr-rightChild==NULL&&curr-leftChild!=NULL)//右子树为空{if(curr==root){root=curr-leftChild;free(curr);}else{s=curr-leftChild;if(curr==f-leftChild)//判断要删除结点是12/18双亲结点的左子树还是右子树f-leftChild=s;elsef-rightChild=s;free(curr);}}else//左，右子树都有{q=curr;s=curr-rightChild;while(s-leftChild!=NULL){q=s;s=s-leftChild;}curr-data=s-data;if(curr=q){if(s-rightChild==NULL){free(s);q-rightChild=NULL;}else{q-rightChild=s-rightChild;free(s);}}else{if(s-rightChild==NULL){free(s);q-leftChild=NULL;}else{q-leftChild=s-rightChild;free(s);}}13/18}}elseprintf(此二叉排序树为空);returnroot;}主函数：#includestdio.h#includestdlib.h#includemath.h#defineMaxSize100typedefstructnode{intdata;structnode*leftChild;structnode*rightChild;}BiTreeNode;#includeBiTree.hvoidmain(){intT[MaxSize],x,choice;inti=0,n;doubleASL;BiTreeNode*root=NULL;printf(请先输入一个空格符，再输入所要测试的序列T:\n);//getchar()函数的要求while((getchar())!='\n')//以\n作为输入结束的标志{scanf(%d,&T[i]);i++;}n=i;for(intj=0;jn;j++)Insert(&root,T[j]);14/18printf(指令菜单如下：);printf(\n0:e