Implementare uno stack utilizzando un BST

Question

Voglio implementare uno stack (operazioni push e pop) utilizzando un BST.

Durante l'attraversamento dell'ordine postale in un BST, la radice viene posizionata in cima allo stack, mentre si attraversa in modo iterativo. Quindi, significa che devo inserire ed eliminare elementi dalla radice o qualcos'altro?

Answer 1

int num=1; 
    struct node 
{ 
    int flag; 
    int val; 
    node *left,*right,*parent; 
    }; 

node* tree::InorderTraversalusingInBuiltstack() 
{ 
     stack<node *> p; 
     node *current=root; 

    while(!p.empty()|| current!=NULL) 
    { 
      while(current!=NULL) 
      { 
       p.push(current); 
       current=current->left; 
      } 
      current=p.top(); 
      if(current->flag==num) 
      { 
       return current; 
      } 
      p.pop(); 
      current=current->right; 
     } 
    } 


    void tree::StackUsingBST() 
    { 
     node *q; 

     while(root!=NULL) 
     { 
       num--; 

       q=InorderTraversalusingInBuiltqueue(); 


       node *a=q->parent; 
       if(a!=NULL) 
       { 
        if(a->left==q) 
         a->left=NULL; 
        else 
         a->right=NULL; 

        q->parent=NULL; 
        delete q; 

        disp(); 
        cout<<endl; 
       } 

       else 
       { 

        delete q; 
        root=NULL; 
       } 



     } 
    } 

Ecco il mio approccio è che ho modificato la mia struttura dati un po ', utilizzando una variabile di flag come variabile globale;

supporti prima inserisco 8 quindi il suo valore bandiera corrispondente è 1 quindi inserire 12 suo valore flag = 2 quindi inserire 3 suo valore flag = 3

ora inorder di utilizzare BST come una pila devo eliminare l'elemento che è stato inserito per ultimo, e secondo il mio algo che ha il valore di bandiera più alto.

Si noti inoltre che l'ultimo elemento inserito non avrà alcun figlio quindi la sua eliminazione è abbastanza semplice.

Per trovare il valore di flag più alto disponibile con i nodi, ho fatto un inordertraversal usando stack che è migliore della sua traversal ricorsiva.

Dopo aver trovato quel nodo corrispondente al valore di flag più alto, elimino quel nodo. questo processo viene ripetuto fino a root = NULL.