java - 在二叉搜索树中寻找中序后继

标签 java algorithm binary-tree binary-search-tree

<分区>

我正在创建二叉搜索树类，我的所有函数都接受了 Successor。

我的树输入是 30 10 45 38 20 50 25 33 8 12

当我打印 Inorder traversal 时，它显示为

8 10 12 20 25 30 33 38 45 50

当我输入值 8 时，它表示其后继值是 12。输入 10 和 12 本身也是如此。

当我输入值 33 时，它说继任者是 50。其实不是。

我似乎无法修复它。任何建议的帮助将不胜感激。

我在 main 中这样调用它:

BinarySearchTree BST = new BinarySearchTree(array);

BST.getSeccessor(a); // where a is user input to find it successor

以下是我的代码...

 public TreeNode Successor(TreeNode node) {
        if (node == null) 
         return node; 
        if (node.right != null) {
            return leftMostNode(node.right);
        }
        TreeNode y = node.parent;
        while (null != y && (y.right).equals(node)) {
            node = y;
            y = y.parent;
        }
      return y;
    }

    public static TreeNode leftMostNode(TreeNode node) {
     if (null == node) { return null; }

     while (null != node.left) {
      node = node.left;
     }
     return node;
    }

    /** Search value in Tree need for Successor **/
    public TreeNode Search(int key) {
        TreeNode node = root;                           
        while (node != null) {
            if (key < node.value) {                     
                node = node.left;
            } else if (key  > node.value) {             
                node = node.right;
            } 
            return node;
        }
        return null;
    }

    /** Returns Successor of given value **/
    public int getSuccessor(int val) {
        TreeNode node = Successor(Search(val));
        return node.value; 
    }

最佳答案

我在 Niklas 答案中添加了基于伪代码的工作解决方案:

public TreeNode successor(TreeNode node) {
    if (node == null)
        return node;

    if (node.right != null) {
        return leftMostNode(node.right);
    }

    while (null != node.parent /*while we are not root*/ 
            && node.parent.right == node) /* and while we are "right" node */ {

        node = node.parent; // go one level up
    }

    return node.parent;
}

为此，您必须修复某些方法的实现(如下所示):

/** Search value in Tree need for Successor **/
public TreeNode search(int key) {
    TreeNode node = root;
    while (node != null 
            && key != node.value) {

        if(key < node.value) {
            node = node.left;
        } else if (key > node.value) {
            node = node.right;
        }
    }
    return node;
}

/** Returns Successor of given value **/
public int getSuccessor(int val) {
    TreeNode node; 
    if (null == (node = search(val))
            || (null == (node = successor(node))) {
        // either val is not in BST, or it is the last value-> no successor
        return ERROR_CODE; // -1, for instance;
    }

    return node.value;
}

关于java - 在二叉搜索树中寻找中序后继，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23302906/

上一篇：c++ - 对为什么我的算法运行速度比应有的速度慢感到困惑

下一篇：c - 如何计算单引号或双引号

相关文章：

java - 防止grails中的CSRF攻击？

java - Android 房间错误 : The columns returned by the query does not have the fields even though they are annotated as non-null or primitive

python - 生成 2 的平方根的数字

algorithm - 我们可以在 O(n^2) 中做 4 和算法吗？

C二叉搜索树实现——插入

java - 将完整的 Maven 远程存储库下载到本地存储库？

java - 我想在 View 寻呼机、选项卡式 Activity Android 中显示 3 个不同选项卡的 3 个不同 fragment

algorithm - 节点为 n 的二叉树和 BST 的数量

java - Weka 的 PCA 运行时间太长

c++ - 来自 testdome 的二叉搜索树