内容简介：Java实现实现 LeetCode 783 二叉搜索树节点最小距离（遍历）二叉搜索树节点最小距离（遍历）783. 二叉搜索树节点最小距离二叉搜索树节点最小距离给定一个二叉搜索树的根节点 root，返回树中任意两节点的差的最小值。示例：输入: root = [4,2,6,1,3,null,null] 输出: 1解释:注意，root是树节点对象(TreeNode

本文没有介绍一些基础知识。对于常见查找算法，比如顺序查找、二分查找、插入查找、斐波那契查找还不清楚的，可以看这篇文章：。

假设查找的数据集是普通的顺序存储，那么插入操作就是将记录放在表的末端，给表记录数加一即可，删除操作可以是删除后，后面的记录向前移，也可以是要删除的元素与最后一个元素互换，表记录数减一，反正整个数据集也没有什么顺序，这样的效率也不错。应该说，插入和删除对于顺序存储结构来说，效率是可以接受的，但这样的表由于无序造成查找的效率很低。

如果查找的数据集是有序线性表，并且是顺序存储的，查找可以用折半、插值、斐波那契等查找算法来实现，可惜，因为有序，在插入和删除操作上，为了维持顺序，需要移动大量元素，就需要耗费大量的时间。

有没有一种即可以使得插入和删除效率不错，又可以比较高效率地实现查找的算法呢？这就是二叉排序树。

二叉排序树（Binary Sort Tree），又称为二叉查找树/二叉搜索树（binary search tree）。它是具有下列性质的二叉树：

• 若它的左子树不空，则左子树上所有节点的值均小于它的根结构的值；
• 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
• 它的左、右子树也分别为二叉排序树；
• 二叉排序树也可以是一个空树。

构造一棵二叉排序树的目的，其主要目的并不是为了排序，而是为了提高查找和插入删除关键字的速度，用以提升数据结构的综合能力。不管怎么说，在一个有序数据集上的查找，速度总是要快于无序的数据集的，而二叉排序树这种非线性的结构，也有利于插入和删除的实现。

* 保存遍历出来的节点数据 * 中序遍历,提供给外部使用的api //如果是空树,直接返回空 * 中序遍历 内部使用的递归遍历方法,借用了栈的结构 //如果左子节点不为null,则继续递归遍历该左子节点 //获取节点的右子节点 //如果右子节点不为null,则继续递归遍历该右子节点

• 若根节点的关键字值等于查找的关键字，成功，返回true；
• 否则，若小于根节点的关键字值，递归查左子树；
• 若大于根节点的关键字值，递归查右子树；
• 最终查找到叶子节点还是没有数据，那么查找失败，则返回false。

有了二叉排序树的查找函数，那么所谓的二叉排序树的插入，其实也就是将关键字放到树中的合适位置而已，插入操作就好像在调用查找的操作，如果找到了那么什么都不做，返回false，如果没找到，则将要插入的元素插入到遍历的路径的最后一点上：

• 若二叉树为空。则单独生成根节点，返回true。
• 执行查找算法，找出被插节点的父亲节点。
• 判断被插节点是其父亲节点的左、右儿子。将被插节点作为叶子节点插入，返回true。如果原节点存在那么什么都不做，返回false。注意：新插入的节点总是叶子节点。

现在我们想要构建如下一颗排序二叉树：

首先要插入根节点47，然后是第二层的节点16、73，然后是第三层的节点1、24、59、88，然后是第四层的节点20、35、62、77。每一层内部节点的顺序可以不一致，但是每一层之间的大顺序一定要保持一致，否则虽然中序遍历输出的时候能够正常输出，但是树的结构不能保证。

在System.out处打上断点，Debug，可以看到树结构和我们预想的一致，如果改变层间的大顺序，那么使用Debug会发现树结构不如预期。

2.4 查找最大值和最小值

很简单，最左边的节点一定是最小的，最右边的节点一定是最大的。因此查找最小的节点只需要向左递归查找，查找最大的节点只需要向右递归查找。

对于二叉排序树的删除，就不是那么容易，我们不能因为删除了节点，而让这棵树变得不满足二叉排序树的特性，所以删除需要考虑多种情况。一共有三种情况需要考虑：

如果查找到的将要被删除的节点没有子节点，那么很简单，直接删除父节点对于该节点的引用即可，如下图的红色节点：

如果查找到的将要被删除的节点具有一个子节点，那么也很简单，直接绕过该节点将原本父节点对于该节点的引用指向该节点的子节点即可，如下图的红色节点：

如果查找到的将要被删除的节点具有两个子节点，那么就比较麻烦了，如下图的红色节点：

比如我们需要删除73，那么我们就必须要找出一个已存在的能够替代73的节点，然后删除该节点。实际上该73节点的左子树的最大节点62和右子树的最小节点77都能够替代73节点，即它们正好是二叉排序树中比它小或比它大的最接近73的两个数。

一般我们选择一种方式即可，我们这次使用右子树的最小节点替代要删除的节点，使用77替代73之后的结构如下：

总之，二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后，仅需修改链接指针即可。

插入删除的时间性能比较好。而对于二叉排序树的查找，走的就是从根节点到要查找的节点的路径，其比较次数等于给定值的节点在二叉排序树的层数。极端情况，最少为1次，即根节点就是要找的节点，最多也不会超过树的深度。也就是说，二叉排序树的查找性能取决于二叉排序树的形状。可问题就在于，二叉排序树的形状是不确定的。

例如{47, 16, 73, 1, 24, 59, 88}这样的数组，我们可以构建下图左的二叉排序树。但如果数组元素的次序是从小到大有序，如{1, 16, 24, 47, 59, 73, 88}，则二叉排序树就成了极端的右斜树，注意它依然是一棵二叉排序树，如下图右。此时，同样是查找节点88，左图只需要3次比较，而右图就需要7次比较才可以得到结果，二者差异很大。

也就是说，我们希望二叉排序树是比较平衡的，即其深度与完全二叉树相同，均为|log2n+1|(|x|表示不大于x的最大整数)，那么查找的时间复杂也就为O(logn)，近似于折半查找，事实上，上图的左图也不够平衡，明显的左重右轻。而极端情况下的右图,则完全退化成为链表，查找的时间复杂度为O(n)，这等同于顺序查找。

因此，如果我们希望对一个集合按二叉排序树查找，最好是把它构建成一棵平衡的二叉排序树，防止极端情况的发生。这样我们就引申出另一个问题，如何让二叉排序树平衡的问题。关于这个问题，在后续的平衡二叉树（AVL树)的部分将会详细解释！

以上就是Java数据结构之二叉排序树的实现的详细内容，更多关于Java二叉排序树的资料请关注脚本之家其它相关文章！