使用二叉搜索树实现堆栈

Question

我想使用二叉搜索树实现一个栈（push和pop操作）。

在BST的后序遍历中，当以迭代方式进行遍历时，根节点被放置在栈顶。

那么这是否意味着我必须从根节点插入和删除元素，或者需要执行其他操作？

- Sumit Kumar Saha

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。

- Sumit Kumar Saha