二叉搜索树的删除方法？

Question

好了，我想写的任何“删除情况”的二叉搜索树，这是我努力工作的删除方法：

public void delete(int key) { 
if (root.value == key) { 
    root = root.right; 
    root.left = root.right.left; 
    return; 
} 
else { 
    deleteRecursive(key, root); ***LINE 58*** 
} 

} 

public void deleteRecursive(int key, BinaryNode node) { 
if (node == null) { 
    System.out.println("ERROR"); 
    return; 
} 
else { 
    if (key < node.value) { 
    // continue search on left 
    if (node.left.value == key) { 
     if (node.left.left == null && node.left.right == null) { 
     node.left = null;  
     } 
     else if (node.left.left == null){ 
     node.left = node.left.right; 
     } 
     else if (node.left.right == null){ 
     node.left = node.left.left; 
     } 
     else{ 
     node.left = node.left.right; 
     node.left.left = node.left.right.left; ***LINE 83*** 
     } 
    } 
    else { 
     deleteRecursive (key, node.left); 
    } 
    } 
    else if (key > node.value){ 
    // continue search on right 
    if (node.right.value == key) { 
     if (node.right.left == null && node.right.right == null) { 
     node.right = null; 
     } 
     else if (node.right.left == null){ 
     node.right = node.right.right; 
     } 
     else if (node.right.right == null){ 
     } 
     else if (node.left.left != null && node.left.right != null){ 
     node.right = node.right.right; 
     node.right.left = node.right.right.left; 
     } 
    } 
    else { 
     deleteRecursive (key, node.right); 
    } 
    } 
} 
} 

但是当我真正在主要使用delete方法及其给出一个NullPointerException。

错误消息读取：

Exception in thread "main" java.lang.NullPointerException 
     at BinaryTree.deleteRecursive(BinaryTree.java:83) 
     at BinaryTree.delete(BinaryTree.java:58) 
     at Main.main(Main.java:14) 

所以我假定它是在线路83和58（标记为代码）。

我一直坐在这里了一个小时试图弄明白，似乎无法得到它。

我不是最好的Java所以我想我可以在这里寻找一些帮助！ :)

这里是所有运行的程序文件（一切除了删除方法已经给出）：https://www.dropbox.com/sh/r1bt2880hnn6tjm/AADsRsOOzuiNKHp-ZC-IrvVta?dl=0

Answer 1

既然你正试图从二叉搜索树删除，最好让它完全递归的，而不是部分。

private BinaryNode deleteRecursive(int data,BinaryNode node) { 
    if(node==null){ 
     return null; 
    } 
    if(data==node.value) 
    { 
     if(node.left!=null && node.right!=null){ 
      BinaryNode minNode = getHighestNodeFromRight(node.right); 
      node.value = minNode.value; 
      node.right = deleteRecursive(minNode.value, node.right); 

      //System.out.println(minNode); 
     } 
     else if(node.left==null){ 
     return node.right; 
     } 
     else{ 
     return node.left; 
     } 
    } 
    else if(data>node.value){ 
    node.right = deleteRecursive(data,node.right); 
    } 
    else{ 
     node.left = deleteRecursive(data, node.left); 
    } 
    return node; 
} 


public BinaryNode getHighestNodeFromRight(BinaryNode node){ 
     if(node.left==null){ 
      return node; 
     } 
     else{ 
      BinaryNode n = getHighestNodeFromRight(node.left); 
      return n; 
     } 
}