迹忆客 专注技术分享

在这篇深入的文章中，我们将在实现递归搜索程序以确定 Java 程序中树的高度之前学习二叉搜索树的基础知识。 要理解本文，我们建议大家对树的数据结构概念有基本的了解。

二叉搜索树

让我们保持简单。 我们不会用冗长的理论概念让您感到厌烦。 但是，以下是您应该熟悉的核心概念：

1. 对分层数据结构的根节点的单个引用。
2. 每个节点最多存在两个子节点（左子节点和右子节点）。
3. 二分查找功能组织节点：

• 每个节点根据关键数据字段排序。
• 树中每个节点的键都大于其左子节点的键，并且必须小于其右子节点的键。
• 图：二叉搜索树：

二叉搜索树的应用

让我们保持简单。 我们不会用冗长的理论概念让您感到厌烦。

但是，以下是您应该熟悉的核心概念：

1. 您还可以使用 BST，其中数据流和结构不断进入或离开，例如大多数编程语言（包括 Java）中的 map 和 set 方法。
2. 我们还可以在三维视频游戏中使用 BST 来确定物体的位置和渲染过程。 阅读有关使用 BST 进行空间分区的更多信息：二进制空间分区。
3. 如果我们主要讨论网络，我们几乎可以在每个高带宽路由器中使用这些树来存储路由器表；
4. 如果您对种子和图像签名的独特生成感兴趣。 假设您要验证哈希需求，但整个文件不可用。

这也是您可以利用 BST 的地方。

简而言之，我们可以在各种应用程序中使用二叉搜索树，因为它们能够帮助排列我们想要的数据。 我们可以使用二叉搜索树进行多级索引。

此外，我们还可以使用它们来实现不同的搜索算法。 因为 BST 可以帮助保持数据流的排序。

确定二叉搜索树的高度

如果您遵循以下简单步骤，确定二叉搜索树的高度并不是一件困难的任务：

从根到叶节点的最长路径的长度决定了二叉树的高度。 它也称为二叉树的深度。

根的高度等于树的高度。

节点的深度是到其根的路径的长度。

要计算树的高度，我们必须计算根和最远叶子之间的边数。

正如您在上图中看到的，根和最远叶子之间的边数为 3。因此，树的高度也是 3。

在二叉搜索树中搜索特定键

您可以递归或迭代地在二叉搜索树中搜索特定键。 这两种方法都是各种数据结构操作的流行选择。

如果我们谈论递归搜索方法，搜索过程从检查根节点开始。 就此而言，假设树为零，那么所寻找的键在树中不存在。

如果搜索成功，则返回key与根匹配的节点。 然而，假设键小于根，则程序搜索移动到左子树。

查找二叉搜索树高度的递归步骤

需要注意的是，如果树是空的，那么它的高度就是0。相反，你需要从顶部节点开始向下。

假设我们想递归地确定左子树的最大深度。 这两者的最大深度就是二叉树（左右子树）的高度。

查看以下伪代码。

BinarySearchTree(a, k)
   if a = NIL or k = a.key then
     return a
   if k < a.key then
     return Tree-Search(a.L, k)
   else
     return Tree-Search(a.R, k)
   end if

让我们递归地实现我们的程序来搜索 BST 内的高度。

例子：

package heightofbinarysearchBSTree.jiyil;
//Java program to find the height of BSTree
//A binary BSTree BSTreeNode
public class DetHeight
{
    int BSTreedata;
    DetHeight BSTreeNodeLeft, BSTreeNoderight;
    DetHeight(int i)
    {
        BSTreedata = i;
        BSTreeNodeLeft = BSTreeNoderight = null;
    }
}
class BST
{
    DetHeight BSTreeroot;
    /* Compute the "MaximumHeight" of a BSTree -- the number of
    BSTreeNodes along the longest path from the BSTreeroot BSTreeNode
    down to the farthest leaf BSTreeNode.*/
    int MaximumHeight(DetHeight BSTreeNode)
    {
        if (BSTreeNode == null)
            return -1;
        else
        {
            /* compute the depth of each subBSTree */
            int LeftHeight = MaximumHeight(BSTreeNode.BSTreeNodeLeft);
            int Rightheight = MaximumHeight(BSTreeNode.BSTreeNoderight);

            /* use the larger one */
            if (LeftHeight > Rightheight)
                return (LeftHeight + 1);
            else
                return (Rightheight + 1);
        }
    }
    /* Driver program to test above functions */
    public static void main(String[] args)
    {
        BST BSTree = new BST();
        BSTree.BSTreeroot = new DetHeight(12);
        BSTree.BSTreeroot.BSTreeNodeLeft = new DetHeight(25);
        BSTree.BSTreeroot.BSTreeNoderight = new DetHeight(35);
        BSTree.BSTreeroot.BSTreeNodeLeft.BSTreeNodeLeft = new DetHeight(47);
        BSTree.BSTreeroot.BSTreeNodeLeft.BSTreeNoderight = new DetHeight(26);
        BSTree.BSTreeroot.BSTreeNoderight.BSTreeNodeLeft = new DetHeight(29);
        BSTree.BSTreeroot.BSTreeNoderight.BSTreeNoderight = new DetHeight(53);
        BSTree.BSTreeroot.BSTreeNoderight.BSTreeNodeLeft.BSTreeNoderight = new DetHeight(31);
        System.out.println("Height of BSTree is : " +
                                    BSTree.MaximumHeight(BSTree.BSTreeroot));
    }
}

输出:

The height of this tree : 3

搜索程序的复杂性

在这种特殊情况下，它是线性的，因为我们在保持高度的同时递归地遍历二叉树的所有节点。 因此，时间复杂度为O(N)，其中N是树中的节点数。