使用BST實現堆棧

Question

我想使用BST實現堆棧（推送和彈出操作）。

在BST中的順序遍歷期間，根被放置在堆棧的頂部，而迭代地遍歷。 那麼，這是否意味着我必須從根或其他東西插入和刪除元素？

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



     } 
    } 

這裏我的方法是，我修改了數據結構的位，通過使用標誌變量 作爲全局變量;

假設第i個插入8則其相應的標誌值是1 然後插入12其標記值= 2 然後插入3其標記值= 3

現在序使用BST作爲堆棧我必須刪除最後插入的元素，根據我的算法具有最高的標誌值。

另請注意，插入的最後一個元素不會有任何子元素，因此它的刪除非常容易。

爲了找到可用於節點的最高標誌值，我使用了比其遞歸遍歷更好的棧來進行反轉。

找到與最高標誌值對應的節點後，刪除該節點。 重複此過程直到root = NULL。