Java-Implementierung für binären Suchbaum entfernen Baumknoten nicht

Question

funktioniert ich meine treeNode Einstellung wie diese:

public class BTreeNode { 
    private int data; 
    private BTreeNode left; 
    private BTreeNode right; 

    public BTreeNode(){} 
    public BTreeNode(int dataValue){ 
    this(dataValue, null, null); 
    } 
    public BTreeNode(int dataValue, BTreeNode leftValue, BTreeNode rightValue){ 
    data = dataValue; 
    left = leftValue; 
    right = rightValue; 
    } 
    public void setData(int dataValue){ 
    data = dataValue; 
    } 
    public int getData(){ 
    return data; 
    } 
    public void setLeft(BTreeNode leftValue){ 
    left = leftValue; 
    } 
    public BTreeNode getLeft(){ 
    return left; 
    } 
    public void setRight(BTreeNode rightValue){ 
    right = rightValue; 
    } 
    public BTreeNode getRight(){ 
    return right; 
    } 
    public String toString(){ 
    return Integer.toString(getData()); 
    } 
} 

und meinen binären Suchbaum-Code ist:

public class BinarySearchTree { 

private BTreeNode root; 

public BinarySearchTree(){} 

public void add(int n){ 
    if (root == null) { 
     root = new BTreeNode(n); 
     return; 
    }else{ 
     BTreeNode current = root; 
     while(current != null){ 
      if(n <= current.getData()){ 
       if (current.getLeft() == null) { 
        current.setLeft(new BTreeNode(n)); 
        return; 
       } 
       current = current.getLeft(); 
      }else{ 
       if (current.getRight() == null) { 
        current.setRight(new BTreeNode(n)); 
        return; 
       } 
       current = current.getRight(); 
      } 
     } 
    } 
} 

public void remove(int n){ 
    remove(root, n); 
} 

private BTreeNode remove(BTreeNode root, int n){ 
    if(root == null) return root; 
    int value = root.getData(); 
    BTreeNode left = root.getLeft(); 
    BTreeNode right = root.getRight(); 
    if(n > value) root.setRight(remove(right, n)); 
    else if(n < value) root.setLeft(remove(left, n)); 
    else { 
     //case 1: no children at all 
     if (left == null && right == null) { 
      return null; 
     } 
     //case 2: one child 
     else if (left == null && right != null) { 
      return right; 


     } else if (right == null && left != null) { 
      return left; 
     } 
     //case 3: two child 
     else { 
      int min = findRightMin(right); 
      root.setData(min); 
      remove(right, min); 
      return root; 
     } 
    } 
    return root; 
} 



private int findRightMin(BTreeNode root){ 
    if (root.getLeft() == null) return root.getData(); 
    else return findRightMin(root.getLeft()); 
} 


public int getHeight(){ 
    return getHeight(root); 
} 

private int getHeight(BTreeNode root){ 
    if(root == null) return 0; 
    return 1 + Math.max(getHeight(root.getLeft()), getHeight(root.getRight())); 
} 

public String toString(){ 
    return "{" + toString(root) + "}"; 
} 

private String toString(BTreeNode root){ 

    if(root == null){ 
     return ""; 
    }else{ 

     String left = toString(root.getLeft()); 
     String rootNode = Integer.toString(root.getData()) + ", "; 
     String right = toString(root.getRight()); 

     return left + rootNode + right; 
    } 

} 

public static void main(String[] args){ 

    BinarySearchTree tree = new BinarySearchTree(); 
    tree.add(10); 
    tree.add(8); 
    tree.add(9); 
    tree.add(12); 
    tree.add(15); 
    tree.add(1); 
    tree.add(5); 
    tree.add(7); 
    tree.add(6); 

    System.out.println(tree.toString()); 
    System.out.println(tree.getHeight()); 
    tree.remove(8); 
    System.out.println(tree.toString()); 
} 

} 

, wenn ich diesen Code ausführen die Konsole aus ist

{1, 5, 6, 7, 8, 9, 10, 12, 15, } 
6 
{1, 5, 6, 7, 9, 9, 10, 12, 15, } 

der Code der min des rechten Kind des Knotens, den ich will gefunden löschen und replac Ed es, aber löschte den Knoten nicht. Ich kann nicht herausfinden, welcher Teil hier falsch ist. Bitte helfen Sie!

Answer 1

Sie vergessen, die right für die root für Fall einstellen 3:

 // case 3: two child 
      else { 
       int min = findRightMin(right); 
       root.setData(min); 
       root.setRight(remove(right, min)); //this one 
       return root; 
      } 
     } 

Ausgang:

{1, 5, 6, 7, 8, 9, 10, 12, 15, } 
6 
{1, 5, 6, 7, 9, 10, 12, 15, } 

Bitte testen erneut. Ich habe andere Fälle nicht getestet.

Answer 2

Sie verfehlten root.setRight

//case 3: two child 
else { 
    int min = findRightMin(right); 
    root.setData(min); 
    root.setRight(remove(right, min)); 
    return root; 
}