数据结构-二叉排序树

《数据结构-二叉排序树》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、二叉排序树操作一、设计步骤1）分析课程设计题目的要求2）写出详细设计说明3）编写程序代码，调试程序使其能正确运行4）设计完成的软件要便于操作和使用5）设计完成后提交课程设计报告（一）程序功能：1）创建二叉排序树2）输出二叉排序树3）在二叉排序树中插入新结点4）在二叉排序树中删除给定的值5）在二叉排序树中查找所给定的值（二）函数功能：1）structBiTnode定义二叉链表结点类型包含结点的信息2）classBT二叉排序树类，以实现二叉排序树的相关操作3）InitBitree()构造函数，使根节点指向空4)~BT()析构函数，释放结点空间5)voidIn

2、sertBST(&t,key)实现二叉排序树的插入功能6)intSearchBST(t,key)实现二叉排序树的查找功能7)intDelBST(&t,key)实现二叉排序树的删除功能8)voidInorderBiTree(t)实现二叉排序树的排序（输出功能）9)intmain()主函数，用来完成对二叉排序树类中各个函数的测试18一、设计理论分析方法（一）二叉排序树定义首先，我们应该明确所谓二叉排序树是指满足下列条件的二叉树：（1）左子树上的所有结点值均小于根结点值；（2）右子数上的所有结点值均不小于根结点值；（3）左、右子数也满足上述两个条件。根据对上述

3、的理解和分析，我们就可以先创建出一个二叉链表结点的结构体类型（structBiTNode）和一个二叉排序树类（classBT），以及类中的构造函数、析构函数和其他实现相关功能的函数。（二）插入函数（voidInsertBST(&t,key)）首先定义一个与BiTNode*BT同一类型的结点p，并为其申请空间，使p->data=key,p->lchild和p->rchild=NULL。然后通过对intSearchBST(t,key)的返回值，来判断插入的结点是否已存在，若不存在则从根节点开始，按照二叉排序树的定义来寻找存放新结点的位置，已实现插入操作

4、。（三）查找函数（intSearchBST(t,key)）同样，根据二叉排序树的定义，若所查找的数小于当前结点，则使当前结点等于该结点所指向的左孩子。反之，指向其右孩子。直到找到与所查找的数值相等时，输出该值；或当查找到的结点已经指向空时，则说明该二叉排序树中没有所查找的值。（四）删除函数（intDelBST(&t,key)）首先要找到被删除元素所在的结点p与他的父结点f。然后分一下3种情况进行处理：(1)p为叶子结点，此时直接删除该结点，再修改其父结点的指针。(2)p只存在一个孩子，若p是f的左孩子，则将p的单支子树链接到f的左指针上；否则将p的单支子

5、树链接到f的右指针上。18(3)p的左子树与右子树均不空。此时，若p的左孩子的右子树为空，则将p的左孩子赋值给p，左孩子的左子树链接到结点p的左指针上；否则，从结点p的左孩子开始沿右链进行搜索，直到发现某结点s的右指针空为止，将结点s的值赋给结点p，将结点s的左子树链接到s父结点的右指针上。若在二叉排序树中找不到这个元素，则重新返回到选择删除这一步。（一）输出函数（voidInorderBiTree(t)）即中序遍历，因为通过中序遍历我们可以是二叉排序树得到一个有序的序列。其实现方法是从根结点开始，通过调用函数InorderBiTree(t)并在此函数中

6、的递归调用来实现中序遍历。18一、设计结论及其分析（一）输入正确数据时输出结果与分析：1.输出结果：2.分析：程序开始对二叉排序树进行初始化并将二叉排序树的头结点置为空；接着逐个输入你所想建立此二叉排序树结点的关键字的值，然后中序遍历之并输出其序列；输入你想插入的关键字的值，同样继续中序遍历之并输出其插入数据后的序列；输入已存在的数据中你想删除的关键字的值，输入前确定你所输入的关键字的值存在于此二叉排序树中，继续中序遍历之且输出删除数据后的序列；输入已存在数据中你想查找的关键字的值，输出查找到该节点，并输出查找到的结点的值。这是一套符合常理的数据输入输出

7、结果。（二）输入非正确数据时输出结果与分析：1.输出结果：182.分析：程序开始对二叉排序树进行初始化18并将二叉排序树的头结点置为空；接着逐个输入你所想建立此二叉排序树结点的关键字的值，然后中序遍历之并输出其序列；输入你想插入的关键字的值，同样继续中序遍历之并输出其插入数据后的序列；输入你想删除的关键字的值，若你输入的值不存在于此二叉排序树中，返回没有你要删除的信息，继续输入你要删除的关键字的值，直到你输入的关键字的值在二叉排序树中能找到时，中序遍历之且输出删除数据后的序列；输入你想查找的关键字的值，若输入的数据不存在于此二叉排序树，返回没有查找到该结

8、点的信息。18一、课程设计感想通过这次的课程设计，让我收获很大，使我较为深刻的了