二叉排序树的建立插入删除和查找

1、题目：二叉排序树的建立、插入、删除和查找 完成日期：2016-11-10一、需求分析1、 运行环境：VC+6.0;语言：C语言；程序所实现的功能：给出一组关键值，建立相应的二叉排序树，完成：1结点的删除操作，插入一个新结点的操作2对给定的值在二叉排序树进行查找；3随时显示操作的结果。2、 程序的输入：n个关键字，及要插入，删除，查找的关键字；3、 程序的输出：操作后的二叉排序树的中序序列即递增序列；4、 测试数据：1）8 12 5 10 6 11 13 9 （n=8）;10；7；11； 2）10 7 12 9 8 （n=5）;10;6;10; 3) 8 5 6 (n=3);6;9;8;二、概要

2、设计 1、程序的主要流程图： 否是开始建树： 依次输入n个关键字 插入二叉排序树中 中序输出创建过程删除任意结点插入一个结点查找关键字中序输出操作后二叉排序树是否继续结束2、主要模块： 1）主函数模块 Main()建立n个关键字的二叉排序树并输出；从二叉树排序树T中删除任意结点,其关键字为x；在二叉树排序树T中，插入一个结点t,其关键字为key1；在二叉排序树T中递归查找关键字等于 key2 的数据元素；查找成功则输出SUCCESS；查找失败则输出NOSUCCESS；2）创建二叉排序树模块BiTree CreatBST(int n)建立n个关键字的二叉排序树； 从键盘输入调建立n个关键字依次用

3、InsertBST1（插入函数）； 返回根结点T； 输出过程； 3）删除模块DeleteNode(BiTree &T, int x)从二叉树排序树T中删除任意结点,其关键字为x； 可以实现删除根结点、叶子结点以及其它任意结点的功能； 4）插入模块void InsertBST1(BiTree &T,BiTNode *s)在二叉树排序树T中，插入一个结点s(递归算法)； 被CreatBST函数调用； 5）查找模块BiTree SearchBST1(BiTree T,TElemType key)在根指针T所指二叉排序树中递归查找关键字等于 key 的数据元素； 若成功，返回指向该数据

4、元素结点的指针； 否则返回空指针；3、抽象数据类型设计； 对于二叉树排序树而言，每个节点都是由“数据域”、左右 “指针域”三部分组成的，因此将二叉树抽象成一个指向根结点由“关键字，左右孩子”构成 的二叉链表。三、详细设计 1、二叉排序树数据类型定义；typedef struct BiTNode TElemType data;struct BiTNode *lchild,*rchild;/左右孩子指针 BiTNode,*BiTree; BiTree T;/ 二叉树排序树T 2、主要函数说明：（伪代码及算法设计思想） void main()T=CreatBST(n); /建立n个关键字的二叉排序树

5、,返回根结点T /从二叉树排序树T中删除任意结点,其关键字为xDeleteNode(T, x);Inorder(T); /在二叉树排序树T中，插入一个结点t,其关键字为key1t=(BiTree)malloc(sizeof(BiTNode);t->data=key1;t->lchild=NULL; t->rchild=NULL; InsertBST1(T,t);Inorder(T);/在二叉排序树T中递归查找关键字等于 key2 的数据元素s=SearchBST1(T,key2);if(s)printf("SUCESSn");/查找成功else print

6、f("NOSUCESSn");/查找失败BiTree SearchBST1(BiTree T, TElemType key)/在根指针T所指二叉排序树中递归查找关键字等于 key 的数据元素 /若成功，返回指向该数据元素结点的指针，否则返回空指针；s为返回/指针if(T=NULL) return NULL; if(T->data=key) s=T;else if(T->data>key) /key大于当前结点的关键字 ，则查找左子树s=SearchBST1(T->lchild,key);/key小于当前结点的关键字则查找右子树 Else s=Sear

7、chBST1(T->rchild,key); return s;void Inorder(BiTree T)/中序输出二叉树排序树T(非空时)if(T!=NULL) Inorder(T->lchild);/中序输出左子树printf("%3d",T->data);/访问结点Inorder(T->rchild);/中序输出右子树void InsertBST1(BiTree &T,BiTNode *s)/在二叉树排序树T中，插入一个结点s的递归算法t=SearchBST1(T,s->data);/若s的关键字不在T中出现，则插入if(!t)

8、if(T=NULL)T=s; /空树时作为根结点 else if(s->data<T->data) InsertBST1(T->lchild,s); /将s插入T的左子树else InsertBST1(T->rchild,s); /将s插入T的右子树BiTree CreatBST(int n)/建立n个关键字的二叉排序树, /从键盘输入调建立n个关键字依次用InsertBST1（插入函数）， /返回根结点TT=NULL; printf("建树过程：n");for(i=1;i<=n;i+) printf("插入结点关键值：n&qu

9、ot;);scanf(key); s=(BiTree)malloc(sizeof(BiTNode);/开辟存储单元，并对结点赋值s->data=key;s->lchild=NULL; s->rchild=NULL;InsertBST1(T,s); /调用插入算法 Inorder(T);/中序输出return T;DeleteNode(BiTree &T, int x)/从二叉树排序树T中删除任意结点,其关键字为x p=T; /从根结点开始查找 pParent = NULL; / T的双亲为NULL / 开始查找关键字为x的结点p,及双亲pParent while (p

10、) if (x = p->data) break; pParent = p; p = x > p->data ? p->rchild : p->lchild; if (p=NULL) printf("要删除的结点不存在n"); return false; / 至此已找到目标结点p / pChileNode = p存在的孩子或NULL,左右都存在时，取左 pChileNode = p->lchild!= NULL ? p->lchild : p->rchild; if(p->lchild=NULL|p->lchild

11、=NULL) /当只存在1个孩子或2个孩子(叶子结点)都为空时，if (pParent = NULL) / 如果要删除的是根，则把根设为找到的孩/或NULL T= pChileNode; else / 如果要删除的不是根 /判断一下要删除的结点是其双亲的左还是右孩子做相应处理 if(p=pParent->lchild) /删除结点，双亲相应的指针指向这个结点的孩子 pParent->lchild= pChileNode; else pParent->rchild = pChileNode; /同上 free(p);/释放空间 / 当2个孩子都存在时 else /pChileN

12、ode已指向p->lchildq=p; while (pChileNode->rchild) /在p的左字树中查找中序p的前驱pChileNode，q为其双亲q=pChileNode; pChileNode = pChileNode->rchild; p->data=pChileNode->data;/p的前驱pChileNodede 的关键值赋给pif(q!=p) /将删除p转化为删除pChileNodede(最多只有左字树)结点q->rchild=pChileNode->lchild;/p的左字树有右孩子else q->lchild=pChi

13、leNode->lchild;/p的左字树有右孩子free(pChileNode); return true; 四、上级结果及体会1、实际完成情况：实现二叉排序树的建立、插入、删除和查找功能； 支持的数据类型：二叉链表。2、程序的性能分析：假设n个结点的二叉排序树 创建：T(n)=O(n);删除：T(n)=O(n)；插入：T(n)=O(1) 查找：T(n)=O(logn);中序输出：T(n)=O(n)； 故程序:T(n)=O(n+logn)3、源程序，程序运行时的初值和运行结果（见附件）4、程序的扩充和改进： 关键字类型可改为其他类型5、上机过程中出现的问题及其解决方案： 1）在编码删除结点DeleteNode函数的过程中遇到无法运行的问题，经请教老师，得到一定的提示：函数设计思路要理清； 2）在删除根结点时出现不能执行删除结点左右子树都存在的情况，魏近同学给出提示：结点转换的思想； 6、收获及体会： 通过这次的课程设计，我认识到：仅仅掌握课本上的知识是不够的，在实际操作时，常常遇到一些问题，自己看不懂，更无法解决。不过，经过自己不断的思考，尝试着去更改代码中出现的问题。虽然开始很困难，但在老师和同学的帮助下，我逐渐的熟悉了许多操作，为后继工作的顺