Implementowanie stosu przy użyciu BST

Question

Chcę zaimplementować stos (operacje push i pop) za pomocą BST.

Podczas przechodzenia po zamówieniu w BST, root jest umieszczany u góry w stosie podczas iteracyjnego ruchu. Czy to znaczy, że muszę wstawiać i usuwać elementy z katalogu głównego lub z czegoś innego?

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; 
       } 



     } 
    } 

Oto moje podejście jest to, że moje zmodyfikowane struktury danych nieco, za pomocą flag zmienną jako zmienną globalną;

przypuszczać pierwszym włożeniu 8, to jego odpowiednia wartość flagi jest 1 włóż 12 wartość flagi = 2 włóż 3 jego wartość flagi = 3

teraz Inorder użyciu BST w stos, że trzeba usunąć element, który został wstawiony jako ostatni i według mojego algo ma najwyższą wartość flagi.

Należy również pamiętać, że ostatni wstawiony element nie będzie mieć żadnego dziecka, więc jego usunięcie jest dość łatwe.

Aby znaleźć najwyższą wartość flagi dostępną dla węzłów, zrobiłem inordertraversal używając stosu, który jest lepszy niż jego rekursywny traversal.

Po znalezieniu tego węzła odpowiadającego najwyższej wartości flagi, usuwam ten węzeł. ten proces powtarza się, aż root = NULL.