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 である、私は削除する必要がスタックとしてBSTを使用するINORDER今= 3

3のフラグの値を挿入し= 2 12のフラグ値を挿入最後に挿入された要素、およびフラグ値が最も高い私のアルゴに従ってください。

挿入された最後の要素には子がないため、削除は非常に簡単です。

ノードで利用可能な最高のフラグ値を見つけるために、私は反復的なトラバーサルよりも優れたスタックを使ってinordertraversalを行いました。

最高のフラグ値に対応するノードを見つけたら、そのノードを削除します。 このプロセスは、root = NULLになるまで繰り返されます。