java - 二进制搜索树未返回正确的顺序后继

我正在尝试使用Java从geeksforgeeks.com http://www.geeksforgeeks.org/inorder-predecessor-successor-given-key-bst/解决以下问题。我在搜索树中已有的密钥时得到了正确的后继者，但是对于不在树中的值，我无法获得该密钥的正确后继者。有人可以告诉我我要去哪里了。

package com.geeksforgeeks.binarysearchtree;

public class BinarySearchTree {
public Node root;
static class Node
{
    int data;
    Node right;
    Node left;

    public Node(int data)
    {
        this.data=data;
        this.right=null;
        this.left=null;
    }
}

public void insert(int data)
{
    root=treeInsert(root,data);
}

public Node treeInsert(Node root,int data)
{
    if(root==null)
        {
        root=new Node(data);
        return root;
        }

    if(data >= root.data)
        root.right= treeInsert(root.right,data);
    else
        root.left= treeInsert(root.left,data);

    return root;
}

public void delete(int data)
{
    root=recDelete(root,data);
}

public Node recDelete(Node root,int data)
{
    //Base Case
    if(root==null)return root;

    //Recurring down the tree
    if(root.data>data)
        root.left=recDelete(root.left,data);
    else if(root.data<data)
        root.right=recDelete(root.right,data);

    else
    {
        if(root.left==null)return root.right;
        else if(root.right==null)return root.left;

        root.data= min(root.right);
        root.right=recDelete(root.right,root.data);
    }

    return root;
}
private int min(Node root) {
    // TODO Auto-generated method stub
    int minv=root.data;

    while(root.left!=null)
    {
        minv=root.left.data;
        root=root.left;
    }

    return minv;
}

public static void main(String[] args) {
    // TODO Auto-generated method stub

    BinarySearchTree tree = new BinarySearchTree();

    /* Let us create following BST
          50
       /     \
      30      70
     /  \    /  \
   20   40  60   80 */
    tree.insert(50);
    tree.insert(30);
    tree.insert(20);
    tree.insert(40);
    tree.insert(70);
    tree.insert(60);
    tree.insert(80);
    System.out.println("successor :"+tree.inOrderSuccessor(50));

    tree.delete(20);
    tree.inOrder();

    tree.delete(30);
    tree.inOrder();

    tree.delete(50);
    tree.inOrder();
}

private int inOrderSuccessor(int i) {

    Node successor=recursiveInOrderSuccessor(root,i);
    if(successor!=null)
    return successor.data;
    else
        return -1;
}

private Node recursiveInOrderSuccessor(Node root2,int i) {

    Node successor=null;
    //if tree is empty

    if(root2==null)return null;

    //if root is the key
    if(root2.data==i)
    {
        successor=root2.right;
        if(root2.right!=null)
        {
            while(successor.left!=null)
                successor=successor.left;
        }

        return successor;
    }

    Node newSuccessor = null;
    if(root2.data>i)
    {
        successor=root2;
        newSuccessor=recursiveInOrderSuccessor(root2.left,i);
    }
    else
    {
        successor=root2;
        newSuccessor=recursiveInOrderSuccessor(root2.right,i);
    }

    if(newSuccessor==null)
    return successor;
    else
        return newSuccessor;
}

private void inOrder() {
    // TODO Auto-generated method stub
    inOrderRecursion(root);
}

private void inOrderRecursion(Node root) {
    // TODO Auto-generated method stub
    if(root!=null)
    {
        inOrderRecursion(root.left);
        System.out.println(root.data);
        inOrderRecursion(root.right);
    }
}
}

最佳答案

您需要在recursiveInOrderSuccessor()中进行更改。


仅当遍历的当前节点的值更大时才捕获后继节点，即，在(root2.data < i)的情况下，不应将节点捕获为后继节点。
如果达到null并且找不到更大的值，则返回null。


下面给出的是更改后的代码。查找Demo here

    private Node recursiveInOrderSuccessor(Node root2,int i) {
        if(root2 == null) return null;
        Node successor = null, succ2 = null;
        if(root2.data == i) {
            successor = root2.right;
            while(successor.left != null){
                successor = successor.left;
            }
            return successor;
        }

        if(root2.data > i){
            successor = root2;
            succ2 = recursiveInOrderSuccessor(root2.left, i);
            if(succ2 != null && succ2.data < successor.data)
                return succ2;
            else
                return successor;
        }
        else{
            return recursiveInOrderSuccessor(root2.right, i);
        }
    }