二叉排序树的查找_二叉排序树的查找长度_二叉排序树的查找方法

在本篇博客的开头，我们先聊聊什么是二叉排序树。说的直白一些，具有左子树上的值<根节点的值<右子树上的值的二叉树，我们称之为二叉排序树。基于二叉排序树的特点，有结合着中序遍历的特点（中序遍历是先遍历左子树，再遍历根节点，然后遍历右子树），我们不难发现，二叉排序树的中序遍历的结果是从小到大有序的。下方我们会先给出二叉排序树的创建，然后给出二叉排序树的节点删除的代码。废话少说，进入今天博客的主题。

一、二叉排序树的创建

上面也简单的提了一下，二叉排序树的创建无非就是不断查找和插入的过程，当我们查找某个值没有找到时，我们就会将该值插入到二叉排序树中。因为再查找的过程中可以确定该结点要插入的合适位置，所以插入就显得比较简单了。下方我们会先给出二叉排序树查找与插入的，然后再给出相应的代码实现。最后给出中序遍历的结果，观察我们创建的二叉排序树的中序遍历是否是有序的。二叉排序树的查找

1、二叉排序树的查找与插入的

我们要将集合{62, 88, 58, 47, 35, 73, 51, 99, 37, 93}中的元素放入到我们的二叉排序树中去存储，如果对我们创建好的二叉排序树进行中序搜索的话，输出的结果就是上面集合的有序序列。下方就是我们二叉排序树从无到有的完整创建过程。

（1）、在初始化状态下我们二叉排序树的根节点为空，我们依次将集合中的元素通过搜索插入到二叉排序树中合适的位置。

（2）、首先在二叉排序中进行搜索62的位置，树为空，所以将62存入到二叉排序树的根节点中，及root=(62)。

（3）、从集合中取出88，然后查找我们的二叉排序树，发现88大于我们的根节点62，所以将88插入到62节点的右子树中，即(62)->rightChild=(88)。

（4）、从集合中取出58，然后从根节点开始查找我们现有的二叉排序树，发现55<62，将55作为62的左结点，即(62)->leftChild=(55)。

（5）、从集合中取出47，然后对二叉排序树进行搜索，发现47<55, 所以(55)->leftChild=(47)。

（6）、从集合中取出35，再次对二叉排序树进行搜索，发现35又小于47，所以(47)->leftChild=(35)。

（7）、从集合中取出73，再次对二叉排序树进行搜索，发现62<73<88, 所以有(88)->leftChild=(73)。

以此类推，要做的事情就是不断从集合中取值，然后对二叉排序树进行查找，找到合适的插入点，然后将相应的节点进行插入，具体步骤就不做过多赘述了。

2.二叉排序树创建的代码实现

接下来我们就来实现二叉排序树创建的代码实现的阶段了，二叉排序树创建分为几个步骤，第一步创建二叉树的结点，第二步二叉排序树的搜索，第三步则是结点的插入。接下来我们将要慢慢的来实现这几个过程。

(1)、二叉排序树的结点类

下方这段代码就是二叉排序树的结点类，该类的结构与之前我们聊二叉树时的结构没什么区别。因为二叉排序树的物理存储结构也是通过二叉链表的形式来组织的，所以下方的BinaryTreeNote中data字段用于存储结点数据，leftChild用来指向左孩子，rightChild用来指向右孩子。二叉树更详细的特性请参考之前发布的博客吧《二叉树的遍历及其线索化》，在此就不做过多赘述了。

(2)、查找二叉排序树代码实现

首先我们先创建一个类，也就是下方的SearchResult类，该类中存储的就是每次查找返回的结果。下方就是对每个结点的介绍：

searchNote字段存储的就是查找到的节点，如果未查找到，那么该结点就为空。

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