二叉排序树论文

《二叉排序树论文》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、二叉排序树思想及C语言实现摘要：本文主要是对二叉排序树的思想进行探讨，文章先从二叉排序树的定义来进行分析，然后分析其主要的性质。通过对其性质的分析，让人们了解二叉排序树的思想。从理论上分析二叉排序树的创建、删除、插入以及遍历。最后，在理论分析的基础上，运用C语言递归算法编程实现，证实理论思想的正确性。关键字：二叉排序树C语言递归算法1．引言通过对数据结构的不断学习，对二叉排序树有了一定的了解。但在许多教材中，只是从理论上浅谈了一下二叉排序树的定义及其思想，并没有用具体算法的在计算机上实现。比如吴严敏版的数据结构教材就是这样，没有具体的实现。这对于很多的初学者来说，要看懂学会是很困难的

2、。就此问题，本文在其理论的基础上给出了具体的算法，以便今后的学习者能够更方便的学习。为了更详细的描述二叉排序树的算法，文章采用C语言来编程实现。该算法主要描述二叉排序树的建立，删除，插入以及遍历等操作。此文是对已经出版了的关于数据结构知识的教材的补充。2．正文2.1二叉排序树的定义及其性质二叉排序树(BinarySortTree)又称二叉查找(搜索)树(BinarySearchTree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；③左、右子树本身又

3、各是一棵二叉排序树。上述性质简称二叉排序树性质(BST性质)，故二叉排序树实际上是满足BST性质的二叉树。例如图1就是两棵二叉排序树。56546598551278122445533793图1二叉排序树示例从上图可以看出，一棵二叉排序树是由若干个不同的结点组成，而且每一个结点带有一个固定的值，用data来存放。每个结点拥有一棵左子树和一棵右子树，叶子结点的左子树与右子树为空，分别用两个指针lchild、rchild来指向它。因此可以定义二叉排序树中的结点结构如下：typedefstructshu//定义二叉排序树结点结构{intdata;//结点值structshu*lchild,*r

4、child;//定义结点的左孩子域与右孩子域}shu;2.2二叉排序树的创建一棵二叉排序树的创建，是从空树开始的，经过多次的查找、比较和插入操作之后，即可得到一棵二叉排序树。假设要建立的序列为（45，24，12，37，53，93），则二叉排序树的生成过程如图2所示：24124545455524（1）（2）（3）（4）372412453724124553372412455393（5）（6）（7）图2二叉排序树的构建过程其中（1）空树，（2）插入45结点，（3）插入24结点，(4)插入12结点（5）插入37结点（6）插入53结点（7）插入24结点图（7）即为序列为（45，24，12，37

5、，53，93）所生成的二叉排序树。下面用代码来实现二叉排序树的建立，用createshu,函数来创建二叉排序树，具体代码如下：shu*createshu(intb,inta[MAX])//创建二叉排序树{shu*l;inti=0;shu*s;for(i=0;idata=a[i];l->lchild=null;l->rchild=null;}else{s=(shu*)malloc(sizeof(shu));s->data=a[i];s->lchild=null;s->rchild=null;

6、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==null)l=h;elseif(l->datadata)l->rchild=lianjie(l->rchild,h);elsel->lchild=lianjie(l->lchild,h);returnl;}2.3二叉排序树的插入在

7、二叉排序树中插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义。　　插入过程如下：（1）若二叉排序树为空，则待插入结点*S作为根结点插入到空树中；　　（2）当非空时，将待插结点关键字S->data和树根关键字t->data进行比较，若s->data=t->data,则无须插入，若s->datadata,则插入到根的左子树中，若s->data>t->data,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同，如此进行下去，直到把结点