构建一棵二叉排序树的C程序的设计方案.doc

《构建一棵二叉排序树的C程序的设计方案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、构建一棵二叉排序树的C程序的设计方案与目标一、目的数据结构课程设计是学习了数据结构课后的一个综合性实践环节，是对课程学习的综合和补充。通过课程设计培养学生运用已学过的理论和技能去分析和解决实际问题的能力、加强学生的实践动手能力和创新能力。二、目标1、结合c和数据结构的理论知识，按要求独立设计方案，培养独立分析和解决实际问题的能力。加强学生的实践动手能力和创新能力。2、学会查阅资料，熟悉常用算法的用途与技巧。3、认真撰写课程设计报告，培养严谨的作风和科学态度。2.问题分析本次程序需要完成如下要求：首先输入任一组数据，使之构造成二叉排序树，并对其作中序遍历，然后输出遍历后的数据序列；其

2、次，该二叉排序树能实现对数据（即二叉排序树的结点）的查找、插入和删除等基本操作。实现本程序需要解决以下几个问题：1、如何构造二叉排序树。2、如何通过中序遍历输出二叉排序树。3、如何实现多种查找。4、如何实现插入删除等操作。二叉排序树的定义：其左子树非空，则左子树上所有结点的值均小于根结点的值。若其右子树非空，则右子树上所有结点的值大于根结点的值。其左右子树也分别为二叉排序树。构建一棵二叉排序树的C程序的设计方案与目标一、目的数据结构课程设计是学习了数据结构课后的一个综合性实践环节，是对课程学习的综合和补充。通过课程设计培养学生运用已学过的理论和技能去分析和解决实际问题的能力、加强学

3、生的实践动手能力和创新能力。二、目标1、结合c和数据结构的理论知识，按要求独立设计方案，培养独立分析和解决实际问题的能力。加强学生的实践动手能力和创新能力。2、学会查阅资料，熟悉常用算法的用途与技巧。3、认真撰写课程设计报告，培养严谨的作风和科学态度。2.问题分析本次程序需要完成如下要求：首先输入任一组数据，使之构造成二叉排序树，并对其作中序遍历，然后输出遍历后的数据序列；其次，该二叉排序树能实现对数据（即二叉排序树的结点）的查找、插入和删除等基本操作。实现本程序需要解决以下几个问题：1、如何构造二叉排序树。2、如何通过中序遍历输出二叉排序树。3、如何实现多种查找。4、如何实现插入

4、删除等操作。二叉排序树的定义：其左子树非空，则左子树上所有结点的值均小于根结点的值。若其右子树非空，则右子树上所有结点的值大于根结点的值。其左右子树也分别为二叉排序树。本问题的关键在于对于二叉排序树的构造。根据上述二叉排序树二叉排序树的生成需要通过插入算法来实现：输入（插入）的第一个数据即为根结点；继续插入，当插入的新结点的关键值小于根结点的值时就作为左孩子，当插入的新结点的关键值大于根结点的值时就作为右孩子；在左右子树中插入方法与整个二叉排序树相同。当二叉排序树建立完成后，要插入新的数据时，要先判断已建立的二叉排序树序列中是否已有当前插入数据。因此，插入算法还要包括对数据的查找判

5、断过程。本问题的难点在于二叉排序树的删除算法的实现。删除前，首先要进行查找，判断给出的结点是否已存在于二叉排序树之中；在删除时，为了保证删除结点后的二叉树仍为二叉排序树，要考虑各种情况，选择正确的方法。删除操作要分几种情况讨论，在后面有介绍。3.总体设计用二叉链表作为二叉排序树的存储结构，其中key为结点关键值，*lchlid、*rchild分别为左右孩子指针。该程序的流程图所示：节点是否为0输入节点值开始N非递归查找J=22递归查找输入J=1显示删除插入查找退出I=2I=4I=3I=1I=0输入i进入主菜单Y总流程图4.具体设计首先定义二叉排序树的数据类型如下：typedefst

6、ructnode{intkey;//关键字项structnode*lchild,*rchild;//左右孩子指针}Bstnode;然后按一定顺序来编写算法程序：4.1递归查找算法具体思想如下：（1）若二叉树为空，则查找失败。（2）否则，将根结点的关键值与待查关键字进行比较，若相等，则查找成功；若根结点关键值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤；若在查找过程的中遇到二叉排序树的叶子结点时，还没有找到待查结点，则查找不成功。if(t==NULL)returnNULL;else{if(t->data==x)returnt;if(xdata)return(

7、Bsearch(t->lchild,x));elsereturn(Bsearch(t->rchild,x));}二叉排序树归查找算法流程图4.2非递归查找算法查找过程是从根结点开始逐层向下进行的。并定义一个标记量记录是否找到结点。Bstnode*searchBST(Bstnode*t,intx){Bstnode*p;intflag=0;p=t;//定义*p结点用于逐层查找，丛根结点开始查找while(p!=NULL)//二叉排序树不为空{if(p->key==x)//