사례 2 (삭제 노드에는 하위 트리가 하나만 있음)를 제외하고 대부분의 경우가 작동한다고 생각합니다. 내 테스트 사례는 1,2,3,4 노드가없는 아래의 트리입니다 : BST에서 노드 삭제하기
이 프로그램은 트리에서 6이 삭제되었지만 트리를 인쇄하려고 시도 할 때 6이 있음을 나타냅니다. 나무.
public class RandomNode {
static int size;
public static class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
left = null;
right = null;
size++;
}
}
// delete node in right subtree
public Node delete(Node root, int data) {
// base case - if tree is empty
if (root == null)
return root;
// search for deletion node
else if (data < root.data)
root.left = delete(root.left, data);
else if (data > root.data) {
root.right = delete(root.right, data);
} else {
// case 1: deletion node has no subtrees
if (root.left == null && root.right == null) {
root = null;
size--;
System.out.println(data + " successfully deleted from tree (case1)");
// case 2: deletion node has only one subtree
} else if (root.left != null && root.right == null) {
root = root.left;
size--;
System.out.println(data + " successfully deleted from tree (case2a)");
} else if (root.left == null && root.right != null) {
root = root.left;
size--;
System.out.println(data + " successfully deleted from tree (case2b)");
// case 3: deletion node has two subtrees
// *find min value in right subtree
// *replace deletion node with min value
// *remove the min value from right subtree or else there'll be
// a duplicate
} else if (root.left != null && root.right != null) {
Node temp;
if (root.right.right == null && root.right.left == null)
temp = findMinNode(root.left);
else
temp = findMinNode(root.right);
System.out.println(root.data + " replaced with " + temp.data);
root.data = temp.data;
if (root.right.right == null || root.left.left == null)
root.left = delete(root.left, root.data);
else
root.right = delete(root.right, root.data);
size--;
System.out.println(temp.data + " succesfuly deleted from tree (case3)");
}
}
return root;
}
// find min value in tree
public Node findMinNode(Node root) {
while (root.left != null)
root = root.left;
System.out.println("min value: " + root.data);
return root;
}
public void preOrderTraversal(Node root) {
if (root == null)
return;
preOrderTraversal(root.left);
System.out.println(root.data);
preOrderTraversal(root.right);
}
public static void main(String[] args) {
RandomNode r = new RandomNode();
Node root = new Node(6);
//root.left = new Node(2);
root.right = new Node(9);
//root.left.left = new Node(1);
//root.left.right = new Node(5);
//root.left.right.left = new Node(4);
//root.left.right.left.left = new Node(3);
root.right.left = new Node(8);
root.right.right = new Node(13);
root.right.left.left = new Node(7);
root.right.right.left = new Node(11);
root.right.right.right = new Node(18);
r.delete(root, 6);
r.preOrderTraversal(root);
}
}
그게 효과가! 방금 삭제할 메소드에 root.left 또는 root.right를 사용하여 root 값을 설정했기 때문에 root = r.delete (root, someValue)를 설정할 필요가 없다고 생각했습니다. 그게 왜 작동하지 않는지 아십니까? –
자바는 값으로 전달됩니다. 그래서, 당신의 메인 루프에는'root'라는 이름의 변수가 있습니다. 그런 다음'Node.delete (root, 6)'를 호출한다. 그것을 호출함으로써,'Node' (객체의 데이터를 포함하는 메모리에 대한 참조 인)의 값을'Node.delete()'메쏘드의'root' 매개 변수의 값에 복사합니다. 그러므로 main.root와 node.root는 둘 다 노드를 값 6으로 참조하는 참조입니다. Delete는 작업을 수행하고 delete의 root 변수는 다른 노드 (node (7))를 참조하도록 수정됩니다. 그러나 주 노드의 루트는 여전히 노드 (6)을 가리키고 있습니다. 삭제 한 후 기본 방법은 루트 –
을 인쇄합니다. 결국 나에게 의미가 있습니다. Koos에 감사드립니다 !! –