这是一个使用字符串的二叉搜索树，我想删除根。 This is my binary search tree visualization
如果“ adam”是我的根，而我想删除它，那么“ beta”应该是我的新根。我的deletemethod2中似乎收到了NullPointerException。
如果（nodeToDelete.parent.leftChild == nodeToDelete）
如果我的树中没有比“ adam”更小的内容，此方法是否应该跳过此if语句并移至else？
它应该集中在树的右侧。
否则如果（nodeToDelete.parent.rightChild == nodeToDelete）
----------
public void remove(String word) {
Node nodeToDelete = find(word);
if (nodeToDelete!=null) {
if (nodeToDelete.leftChild==null && nodeToDelete.rightChild== null) {
deletemethod1(nodeToDelete); // node had no children
}
else if(nodeToDelete.leftChild!=null && nodeToDelete.rightChild!= null){
deletemethod3(nodeToDelete); // both node has children
}
else if(nodeToDelete.leftChild!=null){
deletemethod2(nodeToDelete); // left child should be deleted
}
else if(nodeToDelete.rightChild!=null){
deletemethod2(nodeToDelete);// right child should be deleted
}
}
}
private void deletemethod3(Node nodeToDelete) {
// example
// 50
// 70 <-- delete
// 59 80
// 65 90
Node minNode= minlefttraversal(nodeToDelete.rightChild); // temporarily stores the node thats being deleted
if ((minNode.leftChild != null) || (minNode.rightChild != null)) {
deletemethod2(minNode); /// if minNode have right child connected to it
}
else {
deletemethod1(minNode);// if minNode does not have any child connected to it
}
minNode.parent=nodeToDelete.parent;
minNode.leftChild=nodeToDelete.leftChild;
minNode.rightChild=nodeToDelete.rightChild;
if(nodeToDelete.parent==null){
root= minNode;
}
else{
if (nodeToDelete.parent.leftChild.equals(nodeToDelete))
{
nodeToDelete.parent.leftChild = minNode;
}
else if (nodeToDelete.parent.rightChild.equals(nodeToDelete))
{
nodeToDelete.parent.rightChild = minNode;
}
}
}
/* Finds minimum element in subtree rooted on leftChild */
private Node minlefttraversal(Node node){
if(node.leftChild==null){
return node;
}
return minlefttraversal(node.leftChild);
}
private void deletemethod2(Node nodeToDelete) {
// example
// 50
//delete -> 20 70
// 19 59 80
if (nodeToDelete.parent.leftChild == nodeToDelete) {
if (nodeToDelete.leftChild != null) {
nodeToDelete.parent.leftChild = nodeToDelete.leftChild;
} else if (nodeToDelete.rightChild != null) {
nodeToDelete.parent.leftChild = nodeToDelete.rightChild;
}
} else if (nodeToDelete.parent.rightChild == nodeToDelete)
if (nodeToDelete.leftChild != null) {
nodeToDelete.parent.rightChild = nodeToDelete.leftChild;
} else if (nodeToDelete.rightChild != null) {
nodeToDelete.parent.rightChild = nodeToDelete.rightChild;
}
}
private void deletemethod1(Node nodeToDelete){
// check if the node that is being deleted is the left or right
// child of the parent of the node.
// example
// 5
// \
// delete -> 8
//
if (nodeToDelete.parent == null)
{
nodeToDelete =null;
}
if (nodeToDelete.parent.leftChild==nodeToDelete) {
nodeToDelete.parent.leftChild = null;
} else if (nodeToDelete.parent.rightChild.equals(nodeToDelete)) {
nodeToDelete.parent.rightChild = null;
}
}
最佳答案
您的问题是您正在尝试删除根，因此在这种情况下
if (nodeToDelete.parent.leftChild == nodeToDelete)
nodeToDelete是根，因此nodeToDelete.parent是null，并且nodeToDelete.parent.leftChild引发NullPointerException。当
nodeToDelete.parent == null时，必须添加对案件的特殊处理。关于java - 删除二叉树中的节点，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47657613/