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

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

1、数据结构课程设计系别电子信息系专业计算机科学与技术班级学号姓名指导教师成绩年月日一、需求分析程序设计要求对一学生成绩管理程序构造二叉排序树，并在二叉排序树中实现多种方式的查找。基本任务：（1）以回车('')为输入结束标志,输入数列L，生成一棵二叉排序树T；（2）对二叉排序树T作中序遍历，输出结果；（3）输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历（执行操作2）；否则输出信息“无x”；若要完成题目的要求，需要解决以下几个问题：1、选择一种数据结构存储二叉树的信息2、建立一个新的二叉排序树3、在二叉排序树中实现插入、删除、查找相关节点的操作二、

2、概要设计1、数据结构的选择：题目要求选择合适的存储结构构造二叉排序树，我选择链式结构存储。用链表的方式构造节点，存储二叉排序树中的节点。节点类型和指针类型如下：typedefstructnode{intkey;intother;structnode*lchild,*rchild;}Bstnode;2、概要设计：为了完成所需的功能，需要的函数及其功能如下：main()：主函数模块Bsearch()：查找相应的节点InsertBST()：插入一个新节点CreateBST()：创建一棵二叉排序树Inorder()：对二叉排序树进行中序遍历menu()：主函数显示菜单模块Delet

3、eBST()：删除节点主函数流程图：开始结束调用menu函数输入二叉排序树中的元素输入k=1k=2k=4显示菜单调用子函数DeleteBST()Inorder()调用子函数Bsearch()调用子函数InsertBST()Inorder()zNk=3图主函数流程图子函数流程图：A.插入子函数InsertBST()的流程图：开始x=p->keyNYp=p->lchildp=p->rchildxkeyYN图子函数InsertBST()的流程图B.子函数Bsearch(p)的流程图开始结束输入需要查找的值调用查找函数并返回flag=0找不到值为%d的节点已找到该节点YN图

4、子函数Bsearch(p)的流程图三、详细设计二叉排序树的基本操作1、二叉排序树的查找算法（1）若二叉排序树为空，则查找失败。（2）否则，将根结点的关键字与待查关键字进行比较，若相等，则查找成功；若根节点关键字大于待查值，则进入左子树重复次步骤，否则，进入右子树进行此步骤；若在查找过程中遇到二叉排序树的叶子节点时，还没有找到待查节点，则查找不成功。算法如下：Bstnode*Bsearch(Bstnode*t,intx)//查找{Bstnode*p;intflag=0;p=t;while(p!=NULL){if(p->key==x){printf("已找到该节点！");fla

5、g=1;return(p);break;}if(xkey)p=p->lchild;elsep=p->rchild;}if(flag==0){printf("找不到值为%d的节点！",x);returnNULL;}}1、二叉排序树的节点插入算法在二叉排序树中插入一个新节点，首先要查找该节点在二叉排序树中是否已经存在。若二叉排序树中不存在关键字等于x的节点，则插入。将一个关键字值为x的节点s插入到二叉排序树中，可以用下面的方法：（1）若二叉排序树为空，则关键字为x的节点s成为二叉排序树的根‘（2）若二叉排序树非空，则将x与二叉排序树根进行比较，如果x的值等于根节点关键值

6、，则停止插入；如果x的根节点值小于根节点关键值，则将x插入左子树；如果x的值大于根节点关键字的值，则将x插入右子树。在左右两个子树的插入方法与整个二叉排序树相同。算法如下：Bstnode*InsertBST(Bstnode*t,intx)//插入{Bstnode*s,*p,*f;p=t;while(p!=NULL){f=p;//查找过程中，f指向*p的父节点if(x==p->key)returnt;//二叉排序树中已有关键字为x的元素，无序插入if(xkey)p=p->lchild;elsep=p->rchild;}s=(Bstnode*)malloc(sizeof

7、(Bstnode));s->key=x;s->lchild=NULL;s->rchild=NULL;if(t==NULL)returns;//原树为空，新节点成为二叉排序树的根if(xkey)f->lchild=s;//新节点作为*f的左孩子elsef->rchild=s;//新节点作为*f的右孩子returnt;}2、二叉排序树的节点删除算法在二叉排序树中删除节点，首先要进行查找操作，以确定被删除的节点是否在二叉排序树中若不在，则不做任何操作；否则，假设要删除的节点为*p，节点*p的父节点为*f，并假设*