英文:
I am having trouble deleting a node from Binary search tree. I guess I have not understood the fundamentals of how Java objects work
问题
Node类：-
public class Node {
int data;
Node left;
Node right;
Node(int data){
this.data = data;
left = null;
right = null;
}
}
BST类：-
public class BST {
Node root;
BST(){
root = null;
}
void insertNode(int data){
root = insertRecursive(data, root);
}
private Node insertRecursive(int data, Node root){
if(root == null) return new Node(data);
if(data < root.data) root.left = insertRecursive(data, root.left);
if(data > root.data) root.right = insertRecursive(data, root.right);
return root;
}
Node find(int data, Node root){
return findRecursive(data, root);
}
private Node findRecursive(int data, Node root){
if(data == root.data) return root;
if(data < root.data) return findRecursive(data, root.left);
if(data > root.data) return findRecursive(data, root.right);
else return null;
}
Node delete(int data, Node root){
Node toBeDeleted = find(data, root);
Node parent = parent(data, root);
if(toBeDeleted.left == null && toBeDeleted.right == null) {
toBeDeleted = null;
return root;
}
else if(toBeDeleted.left == null || toBeDeleted.right == null){
if(toBeDeleted.left == null){
if(parent.left == toBeDeleted) parent.left = toBeDeleted.right;
if(parent.right == toBeDeleted) parent.right = toBeDeleted.right;
}
else if(toBeDeleted.right == null ){
if(parent.left == toBeDeleted) parent.left = toBeDeleted.left;
if(parent.right == toBeDeleted) parent.right = toBeDeleted.left;
}
return root;
}
else {
Node min = findMin(toBeDeleted.right);
toBeDeleted = min;
delete(min.data, min);
return root;
}
}
Node parent(int dataToBeFound, Node root){
return parentHelper(find(dataToBeFound, root), root);
}
private Node parentHelper(Node nodeToBeFound, Node root){
if(root == null ) return null;
else {
if(root.left == nodeToBeFound || root.right == nodeToBeFound) return root;
else{
if(nodeToBeFound.data < root.data) return parentHelper(nodeToBeFound, root.left);
else return parentHelper(nodeToBeFound, root.right);
}
}
}
void levelOrder(Node root){
Queue<Node> q = new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
Node node = q.poll();
System.out.println(node.data);
if(node.left != null ) q.add(node.left);
if(node.right != null ) q.add(node.right);
}
}
Node findMin(Node node){
if(node.left == null) {
return node;
}
else{
return findMin(node.left);
}
}
}
Main函数：-
public class Runner {
public static void main(String[] args) {
BST bst = new BST();
bst.insertNode(15);
bst.insertNode(10);
bst.insertNode(9);
bst.insertNode(11);
bst.insertNode(20);
bst.insertNode(18);
bst.insertNode(25);
bst.levelOrder(bst.root);
System.out.println("After deletion");
bst.levelOrder(bst.delete(9, bst.root));
}
}
删除后我得到了与输入相同的BST。我知道我缺少一些关于对象如何工作或对象如何引用的基础知识。我的问题是我不确定如何解决这个问题。我该怎么做？我应该创建一个新对象吗？还是其他什么？我不知道。
英文:
Node Class:-
public class Node {
int data;
Node left;
Node right;
Node(int data){
this.data = data;
left = null;
right = null;
}
}
BST Class:-
public class BST {
Node root;
BST(){
root = null;
}
void insertNode(int data){
root = insertRecursive(data, root);
}
private Node insertRecursive(int data , Node root){
if(root == null) return new Node(data);
if(data < root.data) root.left = insertRecursive(data,root.left);
if(data > root.data) root.right = insertRecursive(data,root.right);
return root;
}
Node find(int data,Node root){
return findRecursive(data,root);
}
private Node findRecursive(int data, Node root){
if(data == root.data) return root;
if(data < root.data) return findRecursive(data,root.left);
if(data > root.data) return findRecursive(data, root.right);
else return null;
}
Node delete(int data, Node root){
Node toBeDeleted = find(data,root);
Node parent = parent(data,root);
if(toBeDeleted.left == null && toBeDeleted.right == null) {
toBeDeleted = null;
return root;
}
else if(toBeDeleted.left == null || toBeDeleted.right == null){
if(toBeDeleted.left == null){
if(parent.left == toBeDeleted) parent.left = toBeDeleted.right;
if(parent.right == toBeDeleted) parent.right = toBeDeleted.right;
}
else if(toBeDeleted.right == null ){
if(parent.left == toBeDeleted) parent.left = toBeDeleted.left;
if(parent.right == toBeDeleted) parent.right = toBeDeleted.left;
}
return root;
}
else {
Node min = findMin(toBeDeleted.right);
toBeDeleted = min;
delete(min.data,min);
return root;
}
}
Node parent(int dataToBeFound,Node root){
return parentHelper(find(dataToBeFound,root),root);
}
private Node parentHelper(Node nodeToBeFound, Node root){
if(root == null ) return null;
else {
if(root.left == nodeToBeFound || root.right == nodeToBeFound) return root;
else{
if(nodeToBeFound.data < root.data) return parentHelper(nodeToBeFound,root.left);
else return parentHelper(nodeToBeFound,root.right);
}
}
}
void levelOrder(Node root){
Queue<Node> q = new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
Node node = q.poll();
System.out.println(node.data);
if(node.left != null ) q.add(node.left);
if(node.right != null ) q.add(node.right);
}
}
Node findMin(Node node){
if(node.left == null) {
return node;
}
else{
return findMin(node.left);
}
}
}
Main Function:-
public class Runner {
public static void main(String[] args) {
BST bst = new BST();
bst.insertNode(15);
bst.insertNode(10);
bst.insertNode(9);
bst.insertNode(11);
bst.insertNode(20);
bst.insertNode(18);
bst.insertNode(25);
bst.levelOrder(bst.root);
System.out.println("After deletion");
bst.levelOrder(bst.delete(9,bst.root));
}
}
After Deletion I am getting back the same BST as output. I know I missing some fundamentals of how objects work or how objects are referenced. My issue is I am not sure how to tackle this problem. What must I do? should I create a new object? or what? I don't know.
答案1
得分: 0
这部分似乎有问题：
if(toBeDeleted.left == null && toBeDeleted.right == null) {
toBeDeleted = null;
return root;
}
因为你没有处理父节点。
英文:
I think there is something wrong in this part:
if(toBeDeleted.left == null && toBeDeleted.right == null) {
toBeDeleted = null;
return root;
}
Because you do nothing with parent.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论