Удаление узла из BST без использования генераторов

Question

Я не могу найти правильную логику для удаления узла из двоичного дерева поиска.  

public void delete(int key){ 
    node current=root; 
    int flag=0; 
    if(current.data==key){ 
     System.out.println(key+" is deleted"); 
     current.rightchild=null; 
     current.leftchild=null; 
     current=null; 
    } 
    else{ 
     while(true){ 
     if(current.data>key){ 
      current=current.leftchild; 
      if(current==null){ 
       flag=1; 
       break;   
      } 
      if(current.data==key){ 
       System.out.println(key+" is deleted"); 
       current.leftchild=null; 
       current.rightchild=null; 
       current=null; 

       break; 
      } 
     } 
     else{ 
      current=current.rightchild; 
      if(current==null){ 
       flag=1; 
       break; 
      } 
      if(current.data==key){ 
       System.out.println(key+" is deleted"); 
       current.leftchild=null; 
       current.rightchild=null; 
       current=null; 
       break; 
      } 
     } 
     } 
    } 
    if(flag==1){`enter code here` 
     System.out.println(key+" Not Found"); 
    } 
} 

Answer 1

Я использую эти функции для удаления узла в BST, попробуйте ... обратите внимание, что мои функции шаблонные 3 элементов, 1 для ID и 2 для данных .....

template <class T, class U,class V> class Node 
{ 
public: 
    T ID; 
    U data1; 
    V data2; 
    Node *left; 
    Node *right; 
    Node() { left = right = NULL; } 
    Node(T ID, U data1, V data2) 
    { 
     this->ID = ID; 
     this->data1 = data1; 
     this->data2 = data2; 
     left = right = NULL; 
    } 
    V getActors() 
    { 
     return data2; 
    } 
    ~Node() 
    { 
     delete left; 
     delete right; 
    } 
}; 

    void Delete(T ID) 
      { 
       root = delete_helper(root, ID); 
      } 
    Node<T, U,V>* delete_helper(Node<T, U,V>* N, T ID) 
    { 
       if (ID < N->ID) 
       { 
        N->left = delete_helper(N->left, ID); 
        return N; 
       } 
       else if (ID > N->ID) 
       { 
        N->right = delete_helper(N->right, ID); 
        return N; 
       } 

       return Separate(N, ID); 
      } 



     Node<T, U,V>* Separate(Node<T, U,V>* N, T ID) 
      { 
       Node<T, U,V>* NewNode = NULL; 

       if ((N->left == NULL) && (N->right == NULL)) 
       { 
        delete N; 
       } 
       else if (N->right == NULL) 
       { 
        NewNode = N->left; 
        delete N; 
       } 
       else if (N->left == NULL) 
       { 
        NewNode = N->right; 
        delete N; 
       } 
       else 
       { 
        NewNode = N; 
        Node<T, U,V>* R = getRightOf(N->left); 
        Node<T, U,V>* parent = Parent(R->ID); 

        N->ID = R->ID; 

        if (parent != N) { 
         parent->right = R->left; 
        } 
        else { 
         N->left = R->left; 
        } 
        delete R; 
       } 
       return NewNode; 
      }