二叉排序树课程设计报告.doc

计算机科学与技术系课程设计报告20082009学年第 二 学期课程 数据结构与算法课程设计名称二叉排序树运算学生姓名学号专业班级指导教师2009 年 6月一、问题分析和任务定义题目：二叉排序树运算任务定义：对一组数据构造二叉排序树，并在二叉排序树中实现多种方式的查找。基本任务：（1）选择合适的存储结构构造二叉排序树；（2）对二叉排序树T作中序遍历，输出结果；（3）在二叉排序树中实现多种方式的查找，并给出二叉排序树中插入和删除的操作。（4）尽量给出“顺序和链式”两种不同结构下的操作，并比较。若要完成题目的要求，需要解决以下几个问题：1、选择一种数据结构存储二叉树的信息。2、建立一个新的二叉排序树3、在二叉排序树中插入，删除，查找相关节点二、数据结构的选择和概要设计1、数据结构的选择：题目要求选择合适的存储结构构造二叉排序树，我选择链式结构存储。用链表的方式构造节点，存储二叉排序树中的节点！节点类型和指针类型如下！typedef struct nodeint key;int other ;struct node *lchild,*rchild;Bstnode;2、概要设计：为了完成所需的功能，需要的函数及其功能如下：main()：主函数模块Bsearch()：查找相应的节点InsertBST ()：插入一个新节点CreateBST ()：创建一棵二叉排序树Inorder ()：对二叉排序树进行中序遍历menu()：主函数显示菜单模块DeleteBST ()：删除节点主函数流程图：开始结束调用menu函数输入二叉排序树中的元素输入k=1k=2k=4显示菜单调用子函数DeleteBST ()Inorder ()调用子函数Bsearch()调用子函数InsertBST ()Inorder ()zNk=3 图（a）主函数流程图子函数流程图：插入子函数InsertBST ()的流程图：开始x=p-keyNYp=p-lchildp=p-rchildxkeyYN 图（b）子函数InsertBST ()的流程图 子函数Bsearch(p)的流程图开始结束输入需要查找的值调用查找函数并返回flag=0找不到值为%d的节点已找到该节点YN 图（c）子函数Bsearch(p)的流程图三、详细设计和编码二叉排序树的基本操作1、 二叉排序树的查找算法（1） 若二叉排序树为空，则查找失败。（2） 否则，将根结点的关键字与待查关键字进行比较，若相等，则查找成功；若根节点关键字大于待查值，则进入左子树重复次步骤，否则，进入右子树进行此步骤；若在查找过程中遇到二叉排序树的叶子节点时，还没有找到待查节点，则查找不成功。算法如下：Bstnode *Bsearch(Bstnode *t,int x)/查找Bstnode *p;int flag=0;p=t;while(p!=NULL) if(p-key=x) printf(已找到该节点！);flag=1;return(p);break; if (xkey) p=p-lchild; else p=p-rchild; if(flag=0) printf(找不到值为%d的节点！,x); return NULL; 2、 二叉排序树的节点插入算法在二叉排序树中插入一个新节点，首先要查找该节点在二叉排序树中是否已经存在。若二叉排序树中不存在关键字等于x的节点，则插入。将一个关键字值为x的节点s插入到二叉排序树中，可以用下面的方法：（1） 若二叉排序树为空，则关键字为x的节点s成为二叉排序树的根（2） 若二叉排序树非空，则将x与二叉排序树根进行比较，如果x的值等于根节点关键值，则停止插入；如果x的根节点值小于根节点关键值，则将x插入左子树；如果x的值大于根节点关键字的值，则将x插入右子树。在左右两个子树的插入方法与整个二叉排序树相同。算法如下：Bstnode *InsertBST(Bstnode *t,int x)/插入Bstnode *s,*p,*f;p=t;while (p!=NULL) f=p; /查找过程中，f指向*p的父节点if(x=p-key) return t; /二叉排序树中已有关键字为x的元素，无序插入if(xkey) p=p-lchild; else p=p-rchild;s=(Bstnode *)malloc(sizeof(Bstnode);s-key=x;s-lchild=NULL;s-rchild=NULL;if(t=NULL) return s; /原树为空，新节点成为二叉排序树的根if(xkey) f-lchild=s; /新节点作为*f的左孩子else f-rchild=s; /新节点作为*f的右孩子return t;3、 二叉排序树的节点删除算法在二叉排序树中删除节点，首先要进行查找操作，以确定被删除的节点是否在二叉排序树中若不在，则不做任何操作；否则，假设要删除的节点为*p，节点*p的父节点为*f，并假设*p是*f的左孩子。根据被删除节点*p有无孩子，删除部分可做以下3中情况讨论：（1）若*p为叶子节点，则可令其父节点*f的左孩子指针域为空，直接将其删除。（2）若*p节点只有右子树或左子树，则可以将p的左子树或右子树直接改为其双亲节点f的左子树。（3）若*p既有左子树又有右子树；将节点*s为*p的中序前驱。首先找到*p的中序前驱节点*s，然后用节点*s的值代替节点*p的值，再将节点*s删除，节点*s的原左子树改为*s的双亲节点*q的右子树；算法如下：Bstnode *DeleteBST(Bstnode *t,int k)/删除Bstnode *p,*f,*s,*q;p=t;f=NULL;while(p) /查找关键字为k的待删节点*pif(p-key=k) break; /找到，则退出循环f=p; /节点*f为节点*p的父节点if(p-keyk) p=p-lchild;else p=p-rchild;if (p=NULL) return t; /若找不到，则返回原二叉排序树的根指针if (p-lchild=NULL)|(p-rchild=NULL) /若*p无左孩子或右孩子if(f=NULL) /若*p是原二叉排序树的根 if(p-lchild=NULL) t=p-rchild;else t=p-lchild;else if (p-lchild=NULL) /若*p无左孩子if(f-lchild=p) f-lchild=p-rchild; /p是*f的左孩子else f-rchild=p-rchild; else if(f-lchild=p) /若*p无右孩子f-lchild=p-lchild; /p是*f的左孩子else f-lchild=p-lchild; /p是*f的右孩子free(p);else q=p;s=p-lchild; /若p有左右子树while(s-rchild)q=s;s=s-rchild; /在*p的左子树中查找最右下节点if(q=p) q-lchild=s-lchild;p-key=s-key; /将*s的值赋给*pfree(s);return t;四、上机调试1、 我所写的程序和课本上的二叉排序树基本相同！但是在调试过程中遇到了一些问题。我采用的是非递归思想进行遍历，所以存在的基本的语法错误，问题主要在于函数和变量的定义。关键字和函数名的书写。2、 时间，空间性能分析：二叉排序树的的查找与二分查找类似，是一个逐一缩小查找范围的过程。具有n个节点的排序二叉树是一棵深度为n的单枝树，平均查找长度与顺序查找相同，为（n+1）/2；即平均查找长度的数量级为O（n）。五测试结果及其分析1、输入节点信息： 图（1）输入节点信息图2、显示菜单后，根据提示选择操作选择插入一个新节点 图（2）插入新节点图3、继续选择操作，查找一个已有的节点 图（3）查找一个已有节点图4、查找一个没有的节点。 图（4）查找一个没有的节点图5、删除一个节点 图（5）删除一个节点图6、若操作已完成，则退出程序。 图（6）退出图六、用户使用说明1、用户更具提示输入二叉排序树的节点信息并且以0结束输入2、根据菜单提示选择相应的操作3、输出的结果是中序遍历后的结果七、参考文献1王昆仑,李红等编著. 数据结构与算法. 北京:中国铁道出版社,2007.2李业丽，郑良斌编著。数据结构（c）实验教程。北京理工大学出版社 2005八、附录（源代码）#include stdio.h#include malloc.h#define NULL 0typedef struct nodeint key;int other ;struct node *lchild,*rchild;Bstnode;Bstnode *Bsearch(Bstnode *t,int x)/查找Bstnode *p;int flag=0;p=t;while(p!=NULL) if(p-key=x) printf(已找到该节点！);flag=1;return(p);break; if (xkey) p=p-lchild; else p=p-rchild; if(flag=0) printf(找不到值为%d的节点！,x); return NULL; Bstnode *InsertBST(Bstnode *t,int x)/插入Bstnode *s,*p,*f;p=t;while (p!=NULL) f=p; /查找过程中，f指向*p的父节点if(x=p-key) return t; /二叉排序树中已有关键字为x的元素，无序插入if(xkey) p=p-lchild; else p=p-rchild;s=(Bstnode *)malloc(sizeof(Bstnode);s-key=x;s-lchild=NULL;s-rchild=NULL;if(t=NULL) return s; /原树为空，新节点成为二叉排序树的根if(xkey) f-lchild=s; /新节点作为*f的左孩子else f-rchild=s; /新节点作为*f的右孩子return t; Bstnode *CreateBST()/创建一个新的二叉树Bstnode *t;int key; t=NULL; /设置二叉排序树的初态为空scanf(%d,&key); /读入第一个节点的关键字while(key!=0)t=InsertBST(t,key);scanf(%d,&key);return t;void Inorder(Bstnode *T)/中序遍历if(T) /若二叉树不空Inorder(T-lchild); /中序遍历左子树printf(%4d,T-key); /访问根节点Inorder(T-rchild); /中序遍历右子树Bstnode *DeleteBST(Bstnode *t,int k)/删除Bstnode *p,*f,*s,*q;p=t;f=NULL;while(p) /查找关键字为k的待删节点*pif(p-key=k) break; /找到，则退出循环f=p; /节点*f为节点*p的父节点if(p-keyk) p=p-lchild;else p=p-rchild;if (p=NULL) return t; /若找不到，则返回原二叉排序树的根指针if (p-lchild=NULL)|(p-rchild=NULL) /若*p无左孩子或右孩子if(f=NULL) /若*p是原二叉排序树的根 if(p-lchild=NULL) t=p-rchild;else t=p-lchild;else if (p-lchild=NULL) /若*p无左孩子if(f-lchild=p) f-lchild=p-rchild; /p是*f的左孩子else f-rchild=p-rchild; else if(f-lchild=p) /若*p无右孩子f-lchild=p-lchild; /p是*f的左孩子else f-lchild=p-lchild; /p是*f的右孩子free(p);else q=p;s=p-lchild; /若p有左右子树while(s-rchild)q=s;s=s-rchild; /在*p的左子树中查找最右下节点if(q=p) q-lchild=s-lchild;p-key=s-key; /将*s的值赋给*pfree(s);return t;void menu() printf(n); printf(1-插入节点-n); printf(n); printf(2-查找节点-n); printf(n); printf(3-删除节点-n); printf(n); printf(4-退出-n); printf(n);void main()Bstnode *tree,*p;int seai,deli,x;int k,flag=1;printf(请输入节点信息，并以0结束:n);tree=CreateBST();printf(中序遍历所得序列为:n);Inorder(tree); printf(n);menu();while(flag) printf(请选择操作:); scanf(%d,&k); switch(k) case 1:printf(插入一个新的节点:);scanf(%d,&x);InsertBST(tr