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

二叉排序树操作一、 设计步骤1） 分析课程设计题目的要求2） 写出详细设计说明3） 编写程序代码，调试程序使其能正确运行4） 设计完成的软件要便于操作和使用5） 设计完成后提交课程设计报告（一）程序功能：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)）首先定义一个与bitnode *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.分析：程序开始对二叉排序树进行初始化并将二叉排序树的头结点置为空；接着逐个输入你所想建立此二叉排序树结点的关键字的值，然后中序遍历之并输出其序列；输入你想插入的关键字的值，同样继续中序遍历之并输出其插入数据后的序列；输入你想删除的关键字的值，若你输入的值不存在于此二叉排序树中，返回没有你要删除的信息，继续输入你要删除的关键字的值，直到你输入的关键字的值在二叉排序树中能找到时，中序遍历之且输出删除数据后的序列；输入你想查找的关键字的值，若输入的数据不存在于此二叉排序树，返回没有查找到该结点的信息。 四、 课程设计感想通过这次的课程设计，让我收获很大，使我较为深刻的了解了二叉排序树的基本功能和操作。一开始我的程序使用c语言写的，整个过程相对来讲进行的比较顺利，并没有遇到太大的困难。后来可能是因为上学期没有c+的课程设计，没有对c+语言的知识点做整体的考虑，所以导致了在用c+语言来写时，无形中遇到了很多的困难。后来在经过查询资料，又对c+做了一个大致的复习。终于在同学及老师的帮助下完成了这个c+版本的二叉排序树相关操作的程序。课程设计即将结束，然而在这些天里所收获的知识却对自己造成了可观的价值。使自己在程序设计方面的能力有了进一步的提高。我很喜欢这样的课程设计，因为我们在设计的过程中不仅可以将所学知识做一个系统的整合，还能提升自己的能力，所以，我很珍惜这次的课程设计，更加期待我们专业今后其他课程的课程设计！附录#includeusing namespace std;class btpublic :bt(void)/构造函数void initbitree(bitree *t);coutlchild);coutkeyrchild); /查找数据bitree searchbst(bitree t, int k) bitree p;p=t;while(p!=null)&(p-key!=k)if(kkey) p=p-lchild;else p=p-rchild;return(p);/插入数据void insertbst(bitree *t,int k)bitnode *f,*p=*t;while(p)if(p-key=k) return;f=p;p=(kkey)?p-lchild:p-rchild; p=(bitree)malloc(sizeof(bitnode);p-key=k;p-lchild=p-rchild=null;if(*t=null) *t=p;else if (kkey)f-lchild=p;else f-rchild=p;/在二叉排序树*t中删除关键字为k的结点int delbst(bitree *t,int k)bitree p,f,q,s,root;root=*t;p=*t; f=null;while(p)if(p-key=k)break; /找到关键字为k的结点f=p;p=(kkey)?p-lchild:p-rchild; / 分别在*p的左、右子树中查找if(!p)cout没有你要删除的数据lchild=null&p-rchild=null)if(p=*t) *t=null;else if(p=f-lchild) f-lchild=null;else f-rchild=null;free(p);elseif(p-lchild=null&p-rchild!=null) / *p无左子树 if(f-lchild=p)f-lchild=p-rchild; /将*p的右子树链接到其父结点的左链上elsef-rchild=p-rchild; /将*p的右子树链接到其父结点的右链上free(p);else if(p-rchild=null&p-lchild!=null) /*p有左子树if (f-lchild=p) /用*p的左子树代替*pf-lchild=p-lchild;elsef-rchild=p-lchild;free(p);else if(p-lchild!=null&p-rchild!=null)q=p;s=p-lchild;while(s-rchild)q=s;s=s-rchild; p-key=s-key; if(q!=p) q-rchild=s-lchild; else q-lchild=s-lchild; free(s); bt()cout调用析构函数释放!endl;/ 析构private:;/class btint main()bt bt;/class bt创建对象btbt:bitree t=null,p;int key,q=1;bt.initbitree(&t);cout请输入关键字的值,以0结束:key; while(key)bt.insertbst(&t,key); cinkey; cout中序遍历建立的二叉排序树的序列为:; bt.inorderbitree(t); coutendl; cout请输入要插入的结点的关键字的值:key; bt.insertbst(&t,key); cout插入后的二叉排序树的中序序列为:endl; bt.inorderbitree(t); coutendl;for(q=1;)cout请输入要删除的结点的关键字的值:key;q=bt.delbst(&t,key);if(q!=0)break; cout删除后的二叉排序树的中序序列为:endl;bt.inorderbitree(t);couten