1
Dies ist ein binärer Suchbaum mit Strings, ich möchte die Wurzel entfernen. This is my binary search tree visualization Wenn 'adam' meine Wurzel ist und ich sie entfernen möchte, dann sollte 'beta' meine neue Wurzel sein. Ich scheine eine NullPointerException in meinem deletemethod2 zu bekommen.Entfernen von Knoten in einem Binärbaum
if (nodeToDelete.parent.leftChild == nodeToDelete)
Shouldnt diese Methode diese Aussage, wenn überspringen und zum anderen bewegen, wenn da nichts kleiner als "Adam" in meinem Baum ist? Es sollte auf der rechten Seite des Baumes konzentrieren.
else if (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;
}
}