binary-search-tree - 使用 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;
                }



      } 
   }

这里我的方法是我通过使用标志变量稍微修改了我的数据结构
作为全局变量；

假设首先我插入 8 然后它对应的标志值为 1
然后插入 12 其标志值 = 2
然后插入 3 其标志值 = 3

现在为了使用 BST 作为堆栈，我必须删除最后插入的元素，并根据我的算法具有最高标志值。

另请注意，插入的最后一个元素不会有任何子元素，因此删除它非常容易。

为了找到节点可用的最高标志值，我使用堆栈进行了中序遍历，这比递归遍历要好。

找到与最高标志值对应的节点后，我删除该节点。
重复这个过程直到 root=NULL。