二叉排序树的建立、插入、侵权和查找doc下载

范文：二叉排序树的建立、插入、侵权和查找完成日期：一、需求分析、运行环境：VC语言：C语言程序所实现的系统：给出一组关键值建立相应的二叉排序树完成：节点的侵权操作插入一个新节点的操作对给定的值在二叉排序树进行查找随时表明操作的结果。、流程的输入：n个关键字及要插入删除查找的关键字、流程的输出：操作后的二叉排序树的中序序列即递增序列、试验数据：）（n=））（n=）)(n=)二、概要设计、流程的主要流程图：、主要系统：）主函数模块Main(){建立n个关键字的二叉排序树并输出从二叉树排序树T中删除任意节点,其关键字为x在二叉树排序树T中插入一个结点t,其关键字为key在二叉排序树T中索引查找关键字等于key的数据元素查找成功则输出SUCCESS查找失败则输出NOSUCCESS}）创建二叉排序树模块BiTreeCreatBST(intn){建立n个关键字的二叉排序树从按键输入调建立n个关键字依次用InsertBST（插入数组）前往根节点T输出过程}）删除系统DeleteNode(BiTreeT二叉排序树查找,intx){从二叉树排序树T中删除任意节点,其关键字为x可以实现删除根节点、叶子结点以及其余任意节点的系统}）插入系统voidInsertBST(BiTreeT,BiTNode*s){在二叉树排序树T中插入一个结点s(递归算法)被CreatBST函数调用}）查找系统BiTreeSearchBST(BiTreeT,TElemTypekey){在根指针T所指二叉排序树中索引查找关键字等于key的数据元素若成功前往指向该数据元素节点的分针否则离开空指针}、抽象数据类型设计对于二叉树排序树而言每个结点都是由“数据域”、左右“时钟域”三部份组成的如果将二叉树抽象成一个指向根节点由“关键字左右妈妈”构成的二叉链表。

三、详实设计、二叉排序树数据类型定义typedefstructBiTNode{TElemTypedatastructBiTNode*lchild,*rchild左右妈妈指针}BiTNode,*BiTreeBiTreeT二叉树排序树T、主要变量表明：（伪代码及硬件设计思维）voidmain(){T=CreatBST(n)构建n个关键字的二叉排序树,前往根节点T从二叉树排序树T中删除任意节点,其关键字为xDeleteNode(T,x)Inorder(T)在二叉树排序树T中插入一个结点t,其关键字为keyt=(BiTree)malloc(sizeof(BiTNode))t>data=keyt>lchild=t>rchild=InsertBST(T,t)Inorder(T)在二叉排序树T中索引查找关键字等于key的数据元素s=SearchBST(T,key)if(s)printf("SUCESSn")查找成功elseprintf("NOSUCESSn")查找失败}BiTreeSearchBST(BiTreeT,TElemTypekey){在根指针T所指二叉排序树中索引查找关键字等于key的数据元素若成功前往指向该数据元素节点的分针否则离开空指针s为前往时钟if(T==)returnif(T>data==key)s=Telseif(T>data>key)key大于目前节点的关键字则查找左子树s=SearchBST(T>lchild,key)key小于目前节点的关键字则查找右子树Elses=SearchBST(T>rchild,key)returns}voidInorder(BiTreeT){中序输出二叉树排序树T(非空时)if(T!=){Inorder(T>lchild)中序输出左子树printf("d",T>data)访问结点Inorder(T>rchild)中序输出右子树}}voidInsertBST(BiTreeT,BiTNode*s){在二叉树排序树T中插入一个结点s的递归算法t=SearchBST(T,s>data)若s的关键字不在T中出现则插入if(!t){if(T==)T=s空树时也是根结点elseif(s>datadata)InsertBST(T>lchild,s)将s插入T的左子树elseInsertBST(T>rchild二叉排序树查找,s)将s插入T的右子树}}BiTreeCreatBST(intn){建立n个关键字的二叉排序树,从按键输入调建立n个关键字依次用InsertBST（插入数组）前往根节点TT=printf("建树过程：n")for(i=idata=keys>lchild=s>rchild=InsertBST(T,s)读取插入算法Inorder(T)中序输出}returnT}DeleteNode(BiTreeT,intx){从二叉树排序树T中删除任意节点,其关键字为xp=T从根节点开始查找pParent=T的双亲为直到查找关键字为x的节点p,及双亲pParentwhile(p){if(x==p>data)breakpParent=pp=x>p>datap>rchild:p>lchild}if(p==){printf("要删除的节点不存在n")returnfalse}至此已寻找目标节点ppChileNode=p存在的爸妈或,左右都存在时取左pChileNode=p>lchild!=p>lchild:p>rchildif(p>lchild==||p>lchild==){当只存在个妈妈或个妈妈(叶子结点)都为空时if(pParent==)或者要删除的是根则把根设为找出的孩或T=pChileNodeelse如果要删除的不是根判断一下要删除的节点是其双亲的左还是右孩子做对应处理{if(p==pParent>lchild)删除节点双亲相应的分针指向这个节点的爸妈pParent>lchild=pChileNodeelsepParent>rchild=pChileNode同上}free(p)释放空间}当个妈妈都存在时else{pChileNode已指向p>lchildq=pwhile(pChileNode>rchild){在p的左字树中查找中序p的前驱pChileNodeq为其双亲q=pChileNodepChileNode=pChileNode>rchild}p>data=pChileNode>datap的前驱pChileNodede的关键值赋给pif(q!=p)将删除p转化为删除pChileNodede(最多只有左字树)节点{q>rchild=pChileNode>lchild}p的左字树有右孩子else{q>lchild=pChileNode>lchild}p的左字树有右孩子free(pChileNode)}returntrue}四、领导结果及体会、实际完成状况：实现二叉排序树的建立、插入、侵权和查找系统支持的数据类型：二叉链表。

、流程的型号分析：假设n个节点的二叉排序树创建：T(n)=O(n)侵权：T(n)=O(n)插入：T(n)=O()查找：T(n)=O(logn)中序输出：T(n)=O(n)故流程:T(n)=O(nlogn)、源程序程序运行时的终值和运行结果（见附件）、流程的扩充和改进：关键字类型可改为其他类型、上机过程中出现的难题及其解决方案：）在编码删除节点DeleteNode函数的过程中遇见无法运行的难题经请教学生得到一定的提示：取值设计逻辑要理清）在删除根节点时出现不能执行删除节点左右子树都存在的现象魏近同学给出提示：节点转换的思维、收获及体会：通过此次的课时设计我认识到：仅仅掌握课文上的常识是不够的在实际操作时往往碰到一些难题自己看不懂更无法解决。不过经过自己不断的反思尝试着去更改代码中出现的难题。虽然直到很困难但在学生和班级的帮助下我逐渐的熟悉了许多操作为后继工作的顺利进行做了准备。个人的力量是薄弱的我学会了咨询别人不再胆怯不再保守。在过程中和班级互相讨论询问学生不断进步。也许我们可以说编一个程仅仅是直到调试和运行相比之下更难。实践中斩获的远比想象的多。看到自己完成了所要求的任务有一种无法用言行来形容的高兴之感这应该无法从学习书籍知识中得到的。五、参考文献数据结构（C语言版）严蔚敏吴伟民编著清华大学出版社C程序设计（第三版）谭浩强编著清华大学出版社

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-119283-1.html