Habe ein Problem mit der delete-Methode eines Binärbaumes. Es Klappt alles ganz gut nur die 3. Bedingung (Knoten mit 2 Kindern) macht mir noch Probleme kann mir da jemand helfen? Das Problem liegt darin, dass wenn der Successor selbst im Unterbaum liegt der an den Successor dran gehängt wird.
Code:
public void delete(T data)
{
BNode<T> dNode = find(data);
if (dNode == root)
{
if (root.getChildCount() > 0)
{
getSuccessor(root).setLeftChild(root.getLeftChild());
root = getSuccessor(root);
} else
{
root = null;
}
} else
{
BNode<T> parent = getParent(dNode);
if (dNode.isLeaf())
{
if (parent.getLeftChild() == dNode)
{
parent.setLeftChild(null);
} else if (parent.getRightChild() == dNode)
{
parent.setRightChild(null);
}
} else if (dNode.getChildCount() == 1)
{
if (dNode.getLeftChild() != null)
{
if (getParent(dNode).getRightChild() == dNode)
{
getParent(dNode).setRightChild(dNode.getLeftChild());
} else if (getParent(dNode).getLeftChild() == dNode)
{
getParent(dNode).setLeftChild(dNode.getLeftChild());
}
} else if (dNode.getRightChild() != null)
{
if (getParent(dNode).getRightChild() == dNode)
{
getParent(dNode).setRightChild(dNode.getRightChild());
} else if (getParent(dNode).getLeftChild() == dNode)
{
getParent(dNode).setLeftChild(dNode.getRightChild());
}
}
} else if (dNode.getChildCount() == 2)
{
BNode<T> successor = getSuccessor(dNode);
if (successor != null)
{
if (getParent(dNode).getRightChild() == dNode)
{
successor.setLeftChild(dNode.getLeftChild());
successor.setRightChild(dNode.getRightChild());
getParent(dNode).setRightChild(successor);
} else if (getParent(dNode).getLeftChild() == dNode)
{
successor.setRightChild(dNode.getRightChild());
successor.setLeftChild(dNode.getLeftChild());
getParent(dNode).setLeftChild(successor);
}
}
}
}
}
Zuletzt bearbeitet: