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

fatherNote字段就负责存储当前查到节点的父节点，如果该节点为空，那么当前查到的节点就为根节点。如果查找失败，那么我们的结点将要挂到fatherNote节点上。

isFound字段负责存储查找的结果，如果二叉排序树中有要查找的节点，那么该字段为true, 如果没有，该字段就为false。

实现完查找结果的存储类后，接下来我们就该实现我们的查找方法了。下方这个searchBST()方法就是我们二叉排序树的查找方法，该方法有三个参数，第一个参数currentRoot是当前二叉排序树的根节点，当然在每次递归遍历时该参数就是每轮递归时子树的根节点。第二个参数是fatherNote，也就是第一个参数currentRoot的父节点，如果currentRoot是整个二叉排序树的根节点的话，那么fatherNote就为空。而第三个参数就是我们要匹配的关键字key。该方法的返回值就是上面SearchResult的对象，该对象中存储的就是查找的相关结果。

下方代码主要分为下方几步：

首先创建存储查找结果的对象searchResult，以备下方查找时使用。

然后判断currentRoot是否为空，如果为nil说明没有找到key相应的结点。根据此结果设置searchResult的值，并返回searchResult。

紧接着在判断key是否等于currentRoot.data, 如果等于就说明我们找到了相应的结点，根据此结果设置searchResult的值，并返回searchResult对象。

如果没有查找失败，也没有查找成功，我们就比较key是否小于currentRoot.data，如果小于的话，说明我们的key有可能位于左子树上，然后递归查找左子树。

如果key大于currentRoot.data, 那么说明我们的key有可能位于右子树上，递归查找右子树。

(3)、二叉排序树节点的插入操作

二叉排序树的插入操作就显得比较简单了，因为再查找的返回结果中，如果查找失败，那么返回结果中也会有fatherNote。二叉排序树的查找这个FatherNote就是我们将要插入节点的父节点。不过二叉排序树为空树时，查找结果的fatherNote为空，所以我们先判断fatherNote节点是否为空，如果为nil的话，我们就把当前关键字key对应的结点作为二叉排序树的根结点。如果fatherNote不为nil, 那么我们就判断key是否大于fatherNote.data, 如果大于的话，我们就把key作为fatherNote的右结点，否则作为fatherNote的左结点。具体代码如下所示。

(4)、二叉排序树的创建

上面我们实现了二叉排序树的搜索和插入的代码，上面我们不止一次的提到过，二叉排序树的创建就是不断查找和插入的过程。也就是先对要插入的结点key进行查找，如果二叉排序树上没有该key的话，就需要根据查找结果将key插入的二叉排序树中相应的位置上。下方代码就是二叉排序树的创建，就是先查找，如果没找到就插入，具体代码如下所示：

3、创建二叉排序树测试用例

下方就是我们创建二叉排序树的测试用例，会将searchTable数组中的线性元素转换成二叉排序树。BinarySearchTree的参数就是一个线性表，该类中的构造器会调用上面的createBinarySearchTree()的方法来构建二叉排序树。构建完二叉排序树后，对二叉排序树进行中序遍历，下方输出的就是中序遍历的结果，从结果中我们不难看出中序遍历的结果是从小到大有序的，由此可见我们的二叉排序树已正确创建了。如果你不放心，你可以将其先序遍历的结果也输出，进行检查。

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