I am having trouble deleting a node from Binary search tree. I guess I have not understood the fundamentals of how Java objects work

huangapple
go评论101阅读模式
英文:

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类：-

  1. public class Node {
  2.     int data;
  3.     Node left;
  4.     Node right;
  6.     Node(int data){
  7.         this.data = data;
  8.         left = null;
  9.         right = null;
  10.     }
  11. }

BST类：-

  1. public class BST {
  2.     Node root;
  4.     BST(){
  5.         root = null;
  6.     }
  8.     void insertNode(int data){
  9.         root = insertRecursive(data, root);
  10.     }
  12.     private Node insertRecursive(int data, Node root){
  13.         if(root == null) return new Node(data);
  14.         if(data < root.data) root.left = insertRecursive(data, root.left);
  15.         if(data > root.data) root.right = insertRecursive(data, root.right);
  16.         return root;
  17.     }
  19.     Node find(int data, Node root){
  20.         return findRecursive(data, root);
  21.     }
  23.     private Node findRecursive(int data, Node root){
  24.         if(data == root.data) return root;
  25.         if(data < root.data) return findRecursive(data, root.left);
  26.         if(data > root.data) return findRecursive(data, root.right);
  27.         else return null;
  28.     }
  30.     Node delete(int data, Node root){
  31.         Node toBeDeleted = find(data, root); 
  32.         Node parent = parent(data, root);
  33.         if(toBeDeleted.left == null && toBeDeleted.right == null) {
  34.             toBeDeleted = null;
  35.             return root;
  36.         }
  38.         else if(toBeDeleted.left == null || toBeDeleted.right == null){
  39.             if(toBeDeleted.left == null){
  40.                 if(parent.left == toBeDeleted) parent.left = toBeDeleted.right;
  41.                 if(parent.right == toBeDeleted) parent.right = toBeDeleted.right;
  42.             }
  43.             else if(toBeDeleted.right == null ){
  44.                     if(parent.left == toBeDeleted) parent.left = toBeDeleted.left;
  45.                     if(parent.right == toBeDeleted) parent.right = toBeDeleted.left;
  46.             }
  47.             return root;
  48.         }
  50.         else {
  51.             Node min = findMin(toBeDeleted.right);
  52.             toBeDeleted = min;
  53.             delete(min.data, min);
  54.             return root;
  55.         }
  56.     }
  58.     Node parent(int dataToBeFound, Node root){
  59.         return parentHelper(find(dataToBeFound, root), root);
  60.     }
  62.     private Node parentHelper(Node nodeToBeFound, Node root){
  63.         if(root == null ) return null;
  64.         else {
  65.             if(root.left == nodeToBeFound || root.right == nodeToBeFound) return root;
  66.             else{
  67.                 if(nodeToBeFound.data < root.data) return parentHelper(nodeToBeFound, root.left);
  68.                 else return parentHelper(nodeToBeFound, root.right);
  69.             }
  70.         }
  71.     }
  73.     void levelOrder(Node root){
  74.         Queue<Node> q = new LinkedList<>();
  75.         q.add(root);
  76.         while(!q.isEmpty()){
  77.             Node node = q.poll();
  78.             System.out.println(node.data);
  79.             if(node.left != null ) q.add(node.left);
  80.             if(node.right != null ) q.add(node.right);
  81.         }
  82.     }
  84.     Node findMin(Node node){
  85.         if(node.left == null) {
  86.             return node;
  87.         }
  88.         else{
  89.             return findMin(node.left);
  90.         }
  91.     }
  92. }

Main函数：-

  1. public class Runner {
  3.     public static void main(String[] args) {
  4.         BST bst = new BST();
  5.         bst.insertNode(15);
  6.         bst.insertNode(10);
  7.         bst.insertNode(9);
  8.         bst.insertNode(11);
  9.         bst.insertNode(20);
  10.         bst.insertNode(18);
  11.         bst.insertNode(25);
  12.         bst.levelOrder(bst.root);
  13.         System.out.println("After deletion");
  14.         bst.levelOrder(bst.delete(9, bst.root));
  15.     }
  16. }

删除后我得到了与输入相同的BST。我知道我缺少一些关于对象如何工作或对象如何引用的基础知识。我的问题是我不确定如何解决这个问题。我该怎么做？我应该创建一个新对象吗？还是其他什么？我不知道。

英文:

Node Class:-

  1. public class Node {
  2. int data;
  3. Node left;
  4. Node right;
  5. Node(int data){
  6. this.data = data;
  7. left = null;
  8. right = null;
  9. }
  10. }

BST Class:-

  1. public class BST {
  2. Node root;
  3. BST(){
  4. root = null;
  5. }
  6. void insertNode(int data){
  7. root = insertRecursive(data, root);
  8. }
  9. private Node insertRecursive(int data , Node root){
  10. if(root == null) return new Node(data);
  11. if(data &lt; root.data) root.left = insertRecursive(data,root.left);
  12. if(data &gt; root.data) root.right = insertRecursive(data,root.right);
  13. return root;
  14. }
  15. Node find(int data,Node root){
  16. return findRecursive(data,root);
  17. }
  18. private Node findRecursive(int data, Node root){
  19. if(data == root.data) return root;
  20. if(data &lt; root.data) return findRecursive(data,root.left);
  21. if(data &gt; root.data) return findRecursive(data, root.right);
  22. else return null;
  23. }
  24. Node delete(int data, Node root){
  25. Node toBeDeleted = find(data,root); 
  26. Node parent = parent(data,root);
  27. if(toBeDeleted.left == null &amp;&amp; toBeDeleted.right == null) {
  28. toBeDeleted = null;
  29. return root;
  30. }
  31. else if(toBeDeleted.left == null || toBeDeleted.right == null){
  32. if(toBeDeleted.left == null){
  33. if(parent.left == toBeDeleted) parent.left = toBeDeleted.right;
  34. if(parent.right == toBeDeleted) parent.right = toBeDeleted.right;
  35. }
  36. else if(toBeDeleted.right == null ){
  37. if(parent.left == toBeDeleted) parent.left = toBeDeleted.left;
  38. if(parent.right == toBeDeleted) parent.right = toBeDeleted.left;
  39. }
  40. return root;
  41. }
  42. else {
  43. Node min = findMin(toBeDeleted.right);
  44. toBeDeleted = min;
  45. delete(min.data,min);
  46. return root;
  47. }
  48. }
  49. Node parent(int dataToBeFound,Node root){
  50. return parentHelper(find(dataToBeFound,root),root);
  51. }
  52. private Node parentHelper(Node nodeToBeFound, Node root){
  53. if(root == null ) return null;
  54. else {
  55. if(root.left == nodeToBeFound || root.right == nodeToBeFound) return root;
  56. else{
  57. if(nodeToBeFound.data &lt; root.data) return parentHelper(nodeToBeFound,root.left);
  58. else return parentHelper(nodeToBeFound,root.right);
  59. }
  60. }
  61. }
  62. void levelOrder(Node root){
  63. Queue&lt;Node&gt; q = new LinkedList&lt;&gt;();
  64. q.add(root);
  65. while(!q.isEmpty()){
  66. Node node = q.poll();
  67. System.out.println(node.data);
  68. if(node.left != null ) q.add(node.left);
  69. if(node.right != null ) q.add(node.right);
  70. }
  71. }
  72. Node findMin(Node node){
  73. if(node.left == null) {
  74. return node;
  75. }
  76. else{
  77. return findMin(node.left);
  78. }
  79. }
  80. }

Main Function:-

  1. public class Runner {
  2. public static void main(String[] args) {
  3. BST bst = new BST();
  4. bst.insertNode(15);
  5. bst.insertNode(10);
  6. bst.insertNode(9);
  7. bst.insertNode(11);
  8. bst.insertNode(20);
  9. bst.insertNode(18);
  10. bst.insertNode(25);
  11. bst.levelOrder(bst.root);
  12. System.out.println(&quot;After deletion&quot;);
  13. bst.levelOrder(bst.delete(9,bst.root));
  14. }
  15. }

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

这部分似乎有问题：

  1. if(toBeDeleted.left == null && toBeDeleted.right == null) {
  2.     toBeDeleted = null;
  3.     return root;
  4. }

因为你没有处理父节点。

英文:

I think there is something wrong in this part:

  1. if(toBeDeleted.left == null &amp;&amp; toBeDeleted.right == null) {
  2. toBeDeleted = null;
  3. return root;
  4. }

Because you do nothing with parent.

huangapple
  • 本文由 发表于 2020年10月7日 17:00:38
  • 转载请务必保留本文链接：https://go.coder-hub.com/64240697.html
  • binary-search-tree
  • data-structures
  • java
  • object
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定