Java 中查找二叉搜索树中的中序后继

2025 年 5 月 12 日 | 阅读 4 分钟

节点在二叉搜索树 (BST) 中的有序后继是在有序遍历中遇到的下一个节点，其中节点按升序访问：先左子树，然后是根，最后是右子树。

要确定有序后继

如果节点有右子节点，则后继是其右子树中的最左边的节点。
如果没有右子节点，则后继位于其祖先中——节点位于左子树中的最近祖先。

示例 1：有右子节点的节点

考虑以下 BST

对于节点10，它有一个右子节点 (15)，所以它的有序后继是15，这是 10 的右子树中最左边的节点。

示例 2：没有右子节点的节点

考虑以下 BST

对于节点15，它没有右子节点。15 的有序后继是20，这是 15 位于其左子树中的最近祖先。

示例 3：节点是最大节点

考虑以下 BST

对于节点30，它的右子树中没有节点，并且它是树中最大的节点，所以它没有有序后继。对于30 的有序后继，函数将返回null。

算法

步骤 1：如果树为空（即根节点为 null），则返回 null，因为不存在有序后继。

步骤 2：如果目标节点有右子节点，则通过向左移动直到不再有左子节点来找到其右子树中最左边的节点，然后返回该节点。

步骤 3：如果没有右子节点，则从根开始遍历以找到后继，在向左移动时更新它。最后记录的大于目标值的节点就是有序后继。

步骤 4：比较目标值与当前节点的值

如果目标值较小，则将当前节点标记为潜在后继并向左移动。
如果目标值较大，则向右移动。

步骤 5：找到后继后，返回它。如果未找到后继，则返回 null。

实施

// Class to represent a node in the Binary Search Tree
class TreeNode {
    int value; // Value of the node
    TreeNode left, right; // Left and right child nodes
    // Constructor to initialize a new node with a given value
    TreeNode(int val) {
        value = val; // Set the node's value
        left = null; // Initialize left child as null
        right = null; // Initialize right child as null
    }
}
class BinarySearchTree {
    // Function to find the leftmost node in a given subtree
    static TreeNode findLeftmost(TreeNode node) {
        TreeNode current = node; // Start from the given node
        // Traverse to the leftmost node in the subtree
        while (current.left != null)
            current = current.left; // Move to the left child
        return current; // Return the leftmost node
    }
    static TreeNode findInorderSuccessor(TreeNode root, int targetValue) {
        // If the root is null, return null (no successor exists)
        if (root == null)
            return null;
        // If the current node's value matches the target and it has a right child
        if (root.value == targetValue && root.right != null)
            return findLeftmost(root.right); // Successor is the leftmost node in the right subtree
        TreeNode successor = null; // Variable to store the successor node
        TreeNode current = root; // Start searching from the root node
        // Traverse the tree to find the successor
        while (current != null) {
            // If the target value is smaller than the current node's value,
            //Then the current node may be the successor
            if (targetValue < current.value) {
                successor = current; // Update successor to the current node
                current = current.left; // Move to the left child
            } else if (targetValue >= current.value) 
                current = current.right; // If the target value is greater, move to the right child
        }
        return successor; 
    }
    public static void main(String[] args) {
        // Construct a sample Binary Search Tree
        TreeNode root = new TreeNode(50); 
        root.left = new TreeNode(30);
        root.right = new TreeNode(70);
        root.left.left = new TreeNode(20); 
        root.left.right = new TreeNode(40); 
        root.right.left = new TreeNode(60); 
        root.right.right = new TreeNode(80);
        int targetValue = 40; // Set target value for which we want to find the inorder successor
        TreeNode successor = findInorderSuccessor(root, targetValue); // Call function to find successor
        // If a successor is found, print its value; otherwise, print a message indicating no successor
        if (successor != null)
            System.out.println("Inorder Successor of " + targetValue + " is: " + successor.value);
        else
            System.out.println("Inorder Successor of " + targetValue + " does not exist.");
    }
}   

输出

 
Inorder Successor of 40 is: 50

时间复杂度：O(H)，其中 H 是树的高度（在最坏情况下，对于不平衡树，可能高达 O(N)）。

辅助空间复杂度：O(1)，因为只使用了几个额外的变量。

解释

该 Java 程序查找二叉搜索树 (BST) 中节点的有序后继。TreeNode 类表示一个带有值和左右子节点的节点。findLeftmost() 函数通过向左移动直到 null 来查找子树中最左边的节点。

findInorderSuccessor() 函数查找给定节点的后继。如果节点有右子节点，则后继是其右子树中最左边的节点；否则，该函数从根遍历，在向左移动时更新后继。main() 函数构建一个 BST，查找目标节点的后继，并打印结果。

下一个主题Java 中的等距数

Java 中查找二叉搜索树中的中序后继

算法

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中查找二叉搜索树中的中序后继

算法

实施

相关帖子

Abstract Method in Java

Real-Time Example for Immutable Class in Java

Java 中查找包含 K 个不同元音的最长子字符串

Java 中的异常类

Java 中链表的中间节点

Bouncy Castle Java

How Multithreading Works in Java?

Java 中的图像处理：获取和设置像素

Java 中将文件从一个位置复制到另一个位置

Lexicographical Order Java

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器