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 用作堆栈，我必须删除最后插入的元素，并根据我的算法具有最高标志值。

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

为了找到节点可用的最高标志值，我使用堆栈进行了一个 inordertraversal，它比它的递归遍历更好。

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