2016-07-09 11 views
0

Ich arbeite an einer Methode zum Löschen eines Knotens aus einem BST. In derselben Methode suche ich rekursiv nach dem Knoten, der gelöscht werden soll, und speichere den Elternknoten dieses Knotens. Das einzige Problem ist jedoch, dass ich nicht sicher bin, wie der Stammknoten in case2 dem Elternknoten gleichgestellt wird (da die Löschung im Elternknoten erfolgt).Löschen von Knoten in BST

public Node delete(Node root, int data) 
{ 

    // base case - if tree is empty 
    if (root == null) 
     return root; 

    // find the node to be deleted and keep track of parent 
    if (data < root.data) 
    { 
     parent = root; 
     System.out.println("parent node: " + parent.data); 
     root.left = delete(root.left, data); 
    } 
    else if (data > root.data) 
    { 
     parent = root; 
     System.out.println("parent node: " + parent.data); 
     root.right = delete(root.right, data); 


    // delete node 
    } 
    else 
    { 
     // case 1: deletion node has no subtrees 
     if (root.left == null && root.right == null) 
     { 
      System.out.println(data + " successfully deleted from tree (case1)"); 
      root = null; 
     } 

     // case 2: deletion node has only one subtree 
     else if (root.left != null && root.right == null) 
     { 
      Node temp = root.left; 
      if(parent.left.data == root.left.data) 
      { 
       parent.left = null; 
       System.out.println(data + " successfully deleted from tree (case2)"); 
       parent.left = temp; 
       root = parent; // parent was sent when searching for the node 

      } 
      else if(parent.right.data == root.data) 
      { 
       parent.right = null; 
       System.out.println(data + " successfully deleted from tree (case2)"); 
       parent.left = temp; 
       root = parent; // parent was sent when searching for the node 
      } 

     } 
     else if (root.left == null && root.right != null) 
     { 
      // same logic 
     } 
    } 

    return root; 

} 

Antwort

1

sollten Sie eine andere Funktion fügen Sie Ihre Löschfunktion für diesen Dieser

class BST{ 
     private Node root=null; 

     private Node parent=null;// just for use by the deletion function 
     public void delete(int data){ 
      Node dummy_node=new Node(0);//can be initialized to anything. 
      dummy_node.setLeft(root); //right is null; 
      parent=dummy_node; 
      root=your_delete(this.root,data); 
      dymmy_node=null; 
     } 
     public Node your_delete(Node root, int data) { 
      //your code here 
     } 
    } 

nennen wird funktionieren, aber dre der bessere Weg Löschung zu tun. hier: http://www.algolist.net/Data_structures/Binary_search_tree/Removal

+0

Danke für das Teilen. Ich schaue mir den Link an! –