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

1题目：二叉排序树的建立、插入、删除和查找完成日期：2016-11-10一、需求分析1、运行环境：VC++6.0;语言：C语言；程序所实现的功能：给出一组关键值，建立相应的二叉排序树，完成：1结点的删除操作，插入一个新结点的操作2对给定的值在二叉排序树进行查找；3随时显示操作的结果。2、程序的输入：n个关键字，及要插入，删除，查找的关键字；3、程序的输出：操作后的二叉排序树的中序序列即递增序列；4、测试数据：1）812510611139（n=8）;10；7；11；2）1071298（n=5）;10;6;10;3)856(n=3);6;9;8;二、概要设计1、程序的主要流程图：否是开始建树：①依次输入n个关键字②插入二叉排序树中③中序输出创建过程删除任意结点插入一个结点查找关键字中序输出操作后二叉排序树是否继续结束22、主要模块：1）主函数模块Main(){建立n个关键字的二叉排序树并输出；从二叉树排序树T中删除任意结点,其关键字为x；在二叉树排序树T中，插入一个结点t,其关键字为key1；在二叉排序树T中递归查找关键字等于key2的数据元素；查找成功则输出SUCCESS；查找失败则输出NOSUCCESS；}2）创建二叉排序树模块BiTreeCreatBST(intn){建立n个关键字的二叉排序树；从键盘输入调建立n个关键字依次用InsertBST1（插入函数）；返回根结点T；输出过程；}3）删除模块DeleteNode(BiTree&T,intx){从二叉树排序树T中删除任意结点,其关键字为x；可以实现删除根结点、叶子结点以及其它任意结点的功能；}4）插入模块voidInsertBST1(BiTree&T,BiTNode*s){在二叉树排序树T中，插入一个结点s(递归算法)；被CreatBST函数调用；}5）查找模块BiTreeSearchBST1(BiTreeT,TElemTypekey){在根指针T所指二叉排序树中递归查找关键字等于key的数据元素；若成功，返回指向该数据元素结点的指针；否则返回空指针；}3、抽象数据类型设计；对于二叉树排序树而言，每个节点都是由“数据域”、左右“指针域”三部分组成的，因此将二叉树抽象成一个指向根结点由“关键字，左右孩子”构成的二叉链表。三、详细设计31、二叉排序树数据类型定义；typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;BiTreeT;//二叉树排序树T2、主要函数说明：（伪代码及算法设计思想）voidmain(){T=CreatBST(n);//建立n个关键字的二叉排序树,返回根结点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(SUCESS\n);//查找成功elseprintf(NOSUCESS\n);//查找失败}BiTreeSearchBST1(BiTreeT,TElemTypekey){//在根指针T所指二叉排序树中递归查找关键字等于key的数据元素//若成功，返回指向该数据元素结点的指针，否则返回空指针；s为返回//指针if(T==NULL)returnNULL;if(T-data==key)s=T;elseif(T-datakey)//key大于当前结点的关键字，则查找左子树s=SearchBST1(T-lchild,key);//key小于当前结点的关键字则查找右子树Elses=SearchBST1(T-rchild,key);returns;}voidInorder(BiTreeT){//中序输出二叉树排序树T(非空时)if(T!=NULL)4{Inorder(T-lchild);//中序输出左子树printf(%3d,T-data);//访问结点Inorder(T-rchild);//中序输出右子树}}voidInsertBST1(BiTree&T,BiTNode*s){//在二叉树排序树T中，插入一个结点s的递归算法t=SearchBST1(T,s-data);//若s的关键字不在T中出现，则插入if(!t){if(T==NULL)T=s;//空树时作为根结点elseif(s-dataT-data)InsertBST1(T-lchild,s);//将s插入T的左子树elseInsertBST1(T-rchild,s);//将s插入T的右子树}}BiTreeCreatBST(intn){//建立n个关键字的二叉排序树,//从键盘输入调建立n个关键字依次用InsertBST1（插入函数），//返回根结点TT=NULL;printf(建树过程：\n);for(i=1;i=n;i++){printf(插入结点关键值：\n);scanf(key);s=(BiTree)malloc(sizeof(BiTNode));//开辟存储单元，并对结点赋值s-data=key;s-lchild=NULL;s-rchild=NULL;InsertBST1(T,s);//调用插入算法Inorder(T);//中序输出}returnT;}DeleteNode(BiTree&T,intx){//从二叉树排序树T中删除任意结点,其关键字为xp=T;//从根结点开始查找5pParent=NULL;//T的双亲为NULL//开始查找关键字为x的结点p,及双亲pParentwhile(p){if(x==p-data)break;pParent=p;p=xp-data?p-rchild:p-lchild;}if(p==NULL){printf(要删除的结点不存在\n);returnfalse;}//至此已找到目标结点p//pChileNode=p存在的孩子或NULL,左右都存在时，取左pChileNode=p-lchild!=NULL?p-lchild:p-rchild;if(p-lchild==NULL||p-lchild==NULL){//当只存在1个孩子或2个孩子(叶子结点)都为空时，if(pParent==NULL)//如果要删除的是根，则把根设为找到的孩//或NULLT=pChileNode;else//如果要删除的不是根//判断一下要删除的结点是其双亲的左还是右孩子做相应处理{if(p==pParent-lchild)//删除结点，双亲相应的指针指向这个结点的孩子pParent-lchild=pChileNode;elsepParent-rchild=pChileNode;//同上}free(p);//释放空间}//当2个孩子都存在时else{//pChileNode已指向p-lchildq=p;while(pChileNode-rchild){//在p的左字树中查找中序p的前驱pChileNode，q为其双亲q=pChileNode;pChileNode=pChileNode-rchild;}6p-data=pChileNode-data;//p的前驱pChileNodede的关键值赋给pif(q!=p)//将删除p转化为删除pChileNodede(最多只有左字树)结点{q-rchild=pChileNode-lchild;}//p的左字树有右孩子else{q-lchild=pChileNode-lchild;}//p的左字树有右孩子free(pChileNode);}returntrue;}四、上级结果及体会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、收获及体会：通过这次的课程设计，我认识到：仅仅掌握课本上的知识是不够的，在实际操作时，常常遇到一些问题，自己看不懂，更无法解决。不过，经过自己不断的思考，尝试着去更改代码中出现的问题。虽然开始很困难，但在老师和同学的帮助下，我逐渐的熟悉了许多操作，为后继工作的顺利进行做了准备。个人的力量是薄弱的，我学会了咨询别人，不再胆怯，不再保守。在过程中和同学相互讨论，询问老师，不断进步。也许，我们可以说，编一个程仅仅是开始，调试和运行相比之下更难。实践中收获的远比想象的多。看到自己完成了所要求的任务，有一种无法用言语来形容的欣慰之感，这也是无法从学习书本知识中得到的。五、参考文献1.数据结构（C语言版）严蔚敏吴伟民编著清华大学出版社2.C程序设计（第三版）谭浩强编著清华大学出版社7