バイナリ検索ツリーが正しいinorderの後継語を返さない

Question

Javaを使用して、次の質問をgeeksforgeeks.com http://www.geeksforgeeks.org/inorder-predecessor-successor-given-key-bst/から解決しようとしています。私は木の中にすでにあるキーを探している間、正しい後継者を得ていますが、ツリーにない値については、私はkeyの正しい後継者を得ることができません。

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); 
    }  
} 
} 

Answer 1

recursiveInOrderSuccessor()で変更する必要があります。

• 横断されている現在のノードの値、すなわち、あなたが(root2.data < i)の場合の後継としてノードを捕捉すべきではない、大きいのみ後継をキャプチャ。
• nullとに達した場合は、返信nullはそれ以上の価値はありません。

以下は、変更されたコードです。 Find 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); 
     } 
    }