数据结构-二叉排序树.docVIP

二叉排序树操作 设计步骤 分析课程设计题目的要求 写出详细设计说明 编写程序代码，调试程序使其能正确运行 设计完成的软件要便于操作和使用 设计完成后提交课程设计报告 （一）程序功能： 1）创建二叉排序树 2）输出二叉排序树 3）在二叉排序树中插入新结点 4）在二叉排序树中删除给定的值 5）在二叉排序树中查找所给定的值 （二）函数功能： 1） struct BiTnode 定义二叉链表结点类型包含结点的信息 2） class BT 二叉排序树类，以实现二叉排序树的相关操作 3） InitBitree() 构造函数，使根节点指向空 4) ~BT () 析构函数，释放结点空间 5) void InsertBST(t,key) 实现二叉排序树的插入功能 6) int SearchBST(t,key) 实现二叉排序树的查找功能 7) int DelBST(t,key) 实现二叉排序树的删除功能 8) void InorderBiTree (t) 实现二叉排序树的排序（输出功能） 9) int main() 主函数，用来完成对二叉排序树类中各个函数的测试 设计理论分析方法 二叉排序树定义 首先，我们应该明确所谓二叉排序树是指满足下列条件的二叉树： （1）左子树上的所有结点值均小于根结点值； （2）右子数上的所有结点值均不小于根结点值； （3）左、右子数也满足上述两个条件。 根据对上述的理解和分析，我们就可以先创建出一个二叉链表结点的结构体类型（struct BiTNode）和一个二叉排序树类（class BT），以及类中的构造函数、析构函数和其他实现相关功能的函数。 插入函数（void InsertBST(t,key)） 首先定义一个与BiTNodek *BT同一类型的结点p， 并为其申请空间，使p-data=key,p-lchild和p-rchild=NULL。然后通过对int SearchBST(t,key)的返回值，来判断插入的结点是否已存在，若不存在则从根节点开始，按照二叉排序树的定义来寻找存放新结点的位置，已实现插入操作。 查找函数（int SearchBST(t,key)） 同样，根据二叉排序树的定义，若所查找的数小于当前结点，则使当前结点等于该结点所指向的左孩子。反之，指向其右孩子。 直到找到与所查找的数值相等时，输出该值；或当查找到的结点已经指向空时，则说明该二叉排序树中没有所查找的值。 删除函数（int DelBST(t,key)） 首先要找到被删除元素所在的结点p与他的父结点f。然后分一下3种情况进行处理： (1)p为叶子结点，此时直接删除该结点，再修改其父结点的指针。 (2)p只存在一个孩子，若p是f的左孩子，则将p的单支子树链接到f的左指针上；否则将p的单支子树链接到f的右指针上。 (3)p的左子树与右子树均不空。此时，若p的左孩子的右子树为空，则将p的左孩子赋值给p，左孩子的左子树链接到结点p的左指针上；否则，从结点p的左孩子开始沿右链进行有哪些信誉好的足球投注网站，直到发现某结点s的右指针空为止，将结点s的值赋给结点p，将结点s的左子树链接到s父结点的右指针上。若在二叉排序树中找不到这个元素，则重新返回到选择删除这一步。 输出函数（void InorderBiTree (t)） 即中序遍历，因为通过中序遍历我们可以是二叉排序树得到一个有序的序列。其实现方法是从根结点开始，通过调用函数InorderBiTree (t)并在此函数中的递归调用来实现中序遍历。 设计结论及其分析 输入正确数据时输出结果与分析： 1.输出结果： 2.分析： 程序开始对二叉排序树进行初始化并将二叉排序树的头结点置为空；接着逐个输入你所想建立此二叉排序树结点的关键字的值，然后中序遍历之并输出其序列；输入你想插入的关键字的值，同样继续中序遍历之并输出其插入数据后的序列；输入已存在的数据中你想删除的关键字的值，输入前确定你所输入的关键字的值存在于此二叉排序树中，继续中序遍历之且输出删除数据后的序列；输入已存在数据中你想查找的关键字的值，输出查找到该节点，并输出查找到的结点的值。这是一套符合常理的数据输入输出结果。 （二）输入非正确数据时输出结果与分析： 1.输出结果： 2.分析： 程序开始对二叉排序树进行初始化并将二叉排序树的头结点置为空；接着逐个输入你所想建立此二叉排序树结点的关键字的值，然后中序遍历之并输出其序列；输入你想插入的关键字的值，同样继续中序遍历之并输出其插入数据后的序列；输入你想删除的关键字的值，若你输入的值不存在于此二叉排序树中，返回没有你要删除的信息，继续输入你要删除的关键字的值，直到你输入的关键字的值在二叉排序树中能找到时，中序遍历之且输出删除数据后的序列；输入你想查找的关键字的值，若输入的数据不存在于此二叉排序树，返回没有查找到