0

私はそれを理解しようと何時間も費やしました。チェックしたところ、削除機能はノードを見つけましたが、それをnullまたは子ノードと同じに設定して削除しようとすると、2回目の出力時にツリーがまったく変更されません。誰かが私が間違ったことを理解するのを手伝ってくれますか、または少なくともそれを修正するために何をする必要があるかを教えてくれますか? 

  class BST {
      Node root; 

      void BST () {
        root = new Node("B");
        insert (root, "A");
        insert (root, "D");
        insert (root, "C"); 
        inOrder (root);

        System.out.println (" ");
        delete (root, "D");
        //root.LEFT = null;
        inOrder (root);
      }

      void insert (Node n, String newKEY) {
        if (n.KEY.compareTo(newKEY) > 0) {

          if (n.LEFT == null) n.LEFT = new Node(newKEY);
          else if (n.LEFT != null && n.LEFT.KEY.compareTo(newKEY) < 0) n.LEFT = new Node(n.LEFT, newKEY, null);
          else insert (n.LEFT, newKEY);
        }

        if (n.KEY.compareTo(newKEY) < 0) {

          if (n.RIGHT == null) n.RIGHT = new Node(newKEY);
          else if (n.RIGHT != null && n.RIGHT.KEY.compareTo(newKEY) > 0) n.RIGHT = new Node(null, newKEY, n.RIGHT);
          else insert (n.RIGHT, newKEY);
        }

        else if (n.KEY.compareTo(newKEY) == 0) n.C++;    
      }

      void delete (Node n, String s) {
        // Visit, check if proper node, if so then delete
        if (n.KEY.compareTo(s) == 0) {
          System.out.println (n.KEY);
          // Deleting a node with no children
          if (n.LEFT == null && n.RIGHT == null) n = null; 

          //  Deleting a node with only left child
          else if (n.RIGHT == null) n = n.LEFT;

          //  Deleting a node with only right child
          else if (n.LEFT == null) n = n.RIGHT; 

          //  Deleting a node with two children
          else deleteNode_Two_Children (n, s);  
        } 
        // Left
        else if (n.KEY.compareTo(s) > 0) delete (n.LEFT, s);
        // Right 
        else if (n.KEY.compareTo(s) < 0) delete (n.RIGHT, s);  

      }

      boolean find (Node n, String s) {
        if (n.KEY.compareTo(s) > 0) {

          if (n.LEFT == null) return false;
          else if (n.LEFT != null && n.LEFT.KEY.compareTo(s) < 0) return false;
          else find (n.LEFT, s);
        }

        if (n.KEY.compareTo(s) < 0) {

          if (n.RIGHT == null) return false;
          else if (n.RIGHT != null && n.RIGHT.KEY.compareTo(s) > 0) return false;
          else find (n.RIGHT, s);
        }

        else if (n.KEY.compareTo(s) == 0) return true;   

        return false;
      }

      void deleteNode_Two_Children (Node n, String st) {
        Node s = getSuccessor(n);
        n = new Node (n.LEFT, s.KEY, s.C, n.RIGHT);
        delete (s, st);

      }

      Node getSuccessor (Node n) {
        Node temp = new Node(); 
        while (n.LEFT != null) {
          temp = n.LEFT; 
          n    = temp;
        }
        return temp; 
      }

      void inOrder (Node n) {   
        // Left
        if (n.LEFT != null) inOrder (n.LEFT);

        // Visit
        System.out.print (n.KEY + " - " + n.C + ", "); 

        // Right 
        if (n.RIGHT != null) inOrder (n.RIGHT);     
      }

      public static void main(String args[]){ 
        BST t = new BST();
        t.BST();
      }  
    }



    class Node {
      String       KEY;
      int          C;  
      Node         LEFT;
      Node         RIGHT;

      Node (String key) {
        KEY     =    key;  
        C       =    1;
        LEFT    =     null;
        RIGHT   =     null;   
      }

      Node (Node L, String key, Node R) {
        LEFT    =     L;
        RIGHT   =     R;
        KEY     =     key;  
        C       =     1;
      }

      Node (Node L, String key, int c, Node R) {
        LEFT    =     L;
        RIGHT   =     R;
        KEY     =     key;  
        C       =     c;
      }

      Node () {
        KEY     =    null;  
        C       =    0;
        LEFT    =     null;
        RIGHT   =     null;   
      }



      // If 'this' is less than 'other', a negative number will be returned, 
      // 0 if equal
      // Positive number if 'this' is greater. 
      int compare (Node other) {
        return this.KEY.compareTo(other.KEY);
      }

      boolean equals (Node other) {
        return this.KEY.equals(other.KEY);
      }
    }
4

1 に答える 1

0

n問題は、に設定するnullとノードが削除されるという仮定です。次の点を考慮してください。

Object x = new Object();

public void someMethod(Object o) {
    o = null;
}

これは変更されませんx。Java は値渡しです。ここで、oは some への参照Objectです。othroughoのメソッドの内部を確実に変更できます。

o.setValue(1);

の値はo、変更されていないヒープ上の実際のアドレスであるため、これは機能します。それ自体を上書きすることはできませんo(たとえば、null または a に設定することはできませんnew Object())。ノードを削除するには、ノードの親を見つけて、その左または右の子 (削除する方) を設定し、それを null に設定する必要があります。また、そのノードに子がある場合、親が削除されたという理由だけでそれらが削除されないようにする必要があります。

于 2013-10-18T23:07:35.327 に答える