二叉排序树思想及C语言实现摘 要：本文主word免费下载

全国最大的共享资料库c++二叉排序树，等您下载。本资料为二叉排序树论文.doc文档c++二叉排序树，由爱问共享资料用户提供，以下为正文内容。

二叉排序树思想及C语言实现摘要：本文主要是对二叉排序树的观念进行分析文章先从二叉排序树的定义来进行探讨之后预测其主要的性质。通过对其性质的剖析让他们知道二叉排序树的观念。从理论上探讨二叉排序树的构建、删除、插入或者遍历。最后在理论探讨的基础上采用C语言递归算法编程实现证实理论观念的正确性。关键字：二叉排序树C语言递归算法．引言通过对数据结构的不断学习对二叉排序树有了必定的知道。但在许多教材中也是从理论上阐述了一下二叉排序树的定义以及观念并没有用准确算法的在计算机上推动。比如吴严敏版的数据结构教材就是这样没有具体的实现。这针对这些的初学者来说要看懂学会是很困难的。就此问题本文在其理论的基础上给出了详细的算法进而未来的学习者能够更方便的学习。为了更具体的表述二叉排序树的算法文章运用C语言来编程实现。该算法主要叙述二叉排序树的构建删除插入或者遍历等操作。此文是对即将出版了的关于数据结构知识的课本的补充。．正文二叉排序树的定义以及性质二叉排序树(BinarySortTree)又称二叉查找(搜索)树(BinarySearchTree)。其定义为：二叉排序树或者是空树以及是满足如下性质的二叉树：①若它的左子树非空则左子树上所有节点的值均高于根节点的值②若它的右子树非空则右子树上所有节点的值均高于根结点的值③左、右子树本身又各是一棵二叉排序树。

上述性质简称二叉排序树性质(BST性质)故二叉排序树实际上是满足BST性质的二叉树。例如图就是两棵二叉排序树。图二叉排序树示例从上图可以看出一棵二叉排序树是由若干个不同的节点构成并且每一个结点具有一个固定的值用data来保存。每个节点拥有一棵左子树和一棵右子树叶子结点的左子树与右子树为空分别用两个指针lchild、rchild来指向它。因此可以定义二叉排序树中的节点结构如下：typedefstructshu定义二叉排序树结点结构{intdata结点值structshu*lchild,*rchild定义节点的左孩子域与右孩子域}shu二叉排序树的构建一棵二叉排序树的建立是从空树起初的经过多次的查找、比较和插入操作以后就能得到一棵二叉排序树。假设要创建的序列为（）则二叉排序树的生成过程如图所示：（）（）（）（）（）（）（）图二叉排序树的重构过程其中（）空树（）插入结点（）插入结点()插入结点（）插入结点（）插入结点（）插入结点图（）即为序列为（）所生成的二叉排序树。下面用代码来实现二叉排序树的构建用createshu,函数来构建二叉排序树具体代码如下：shu*createshu(intb,intaMAX)创建二叉排序树{shu*linti=shu*sfor(i=i<bi){if(i==){l=(shu*)malloc(sizeof(shu))l>data=ail>lchild=l>rchild=}else{s=(shu*)malloc(sizeof(shu))s>data=ais>lchild=s>rchild=if(s>data>l>data)l>rchild=lianjie(l>rchild,s)调用连接函数elsel>lchild=lianjie(l>lchild,s)}}returnl返回一棵二叉排序树}lianjie函数如下：shu*lianjie(shu*l,shu*h)用来连结一棵二叉排序树和一个结点{if(l==)l=helseif(l>data<h>data)l>rchild=lianjie(l>rchild,h)elsel>lchild=lianjie(l>lchild,h)returnl}二叉排序树的插入在二叉排序树中插入新节点要确保插入后的二叉树仍依照二叉排序树的定义。

插入过程如下：（）若二叉排序树为空则待插入节点*S作为根结点插入到空树中（）当非空时将待插结点关键字S>data和树根关键字t>data进行比较若s>data=t>data,则无须插入若s>data<t>data,则插入到根的左子树中若s>data>t>data,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程同样这么进行下来直至把结点*s作为一个新的树叶插入到二叉排序树中甚至等到看到树已有同样关键字的节点为止。用insert函数来实现这个过程代码如下：shu*insert(shu*l,inta)在一棵二叉排序树中插入一个结点a{shu*ss=(shu*)malloc(sizeof(shu))s>data=as>lchild=s>rchild=if(l==){l=s}elseif(a>l>data)l>rchild=insert(l>rchild,a)elsel>lchild=insert(l>lchild,a)returnl返回插入节点a后的二叉排序树}二叉排序树的删掉假设被删结点是*p其双亲是*f不失一般性设*p是*f的左孩子后面分三种状况讨论：⑴若节点*p是叶子结点则只需修改其双亲节点*f的指针即可。

⑵若结点*p只有左子树PL或者只有右子树PR则即使使PL或PR成为其双亲节点的左子树即可。⑶若结点*p的左、右子树均非空先找到*p的中序前趋(或后继)结点*s（注意*s是*p的左子树中的最右下的节点它的右链域为空）然后有两种做法：①令*p的左子树直接链到*p的双亲节点*f的左链上,而*p的右子树链到*p的中序前趋结点*s的右链上。②以*p的中序前趋结点*s代替*p（即把*s的数据复制到*p中）将*s的左子树链到*s的双亲节点*q的右链上。用del函数来推动这个过程详细的代码如下：shu*del(shu*l,inta)删除二叉排序树{shu*h,*s,*m,*nn=lif(l>data==a){h=l>lchilds=l>rchildif(h!=){m=hebing(h,s)调用连接两棵树的合并数组l=m}elsel=s}else{if(a>l>data){n=l>rchildl>rchild=del(n,a)}else{n=l>lchildl>lchild=del(n,a)}}returnl返回删除a节点后的二叉排序树}合并两棵二叉排序树的hebing函数如下：shu*hebing(shu*h,shu*s)合并两棵二叉排序树{if(h>rchild==)h>rchild=selseh>rchild=hebing(h>rchild,s)returnh返回合并后的二叉排序树}二叉排序树的查找假定二叉排序树的根节点指针为root给定的关键字值为K则查找算法可表述为：①置初值：q＝root②如果K＝q－＞data则查找失败算法结束③否则一旦K＜q－＞data而且q的左子树非空则将q的左子树根送q转方法②否则查找成功结束算法④否则一旦K＞q－＞data而且q的右子树非空则将q的右子树根送q转方法②否则查找成功算法结束。用find函数来实现这个过程详细的代码如下：intfind(shu*l,inta)在二叉排序树中查找节点a{intk标记所查找结果if(l!=)if(l>data==a){k=}else{if(a>l>data)k=find(l>rchild,a)elsek=find(l>lchild,a)

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