1
이것은 문자열을 사용하는 이진 검색 트리입니다. 루트를 제거하고 싶습니다. This is my binary search tree visualization 'adam'이 내 루트이고 제거하고 싶다면 'beta'가 내 새로운 루트 여야합니다. 내 deletemethod2에서 NullPointerException을 얻는 것 같습니다.이진 트리의 노드 제거
(nodeToDelete.parent.leftChild == nodeToDelete)
야해이 방법은 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;
}
}