Thực hiện ngăn xếp bằng cách sử dụng BST

Question

Tôi muốn triển khai ngăn xếp (thao tác đẩy và bật) bằng BST.

Trong quá trình truyền tải thứ tự bài đăng trong BST, gốc được đặt ở trên cùng trong ngăn xếp, trong khi duyệt ngang theo vòng lặp. Vì vậy, điều đó có nghĩa là tôi phải chèn và xóa các phần tử từ thư mục gốc hoặc cái gì khác?

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



     } 
    } 

Đây là cách tôi sửa đổi cấu trúc dữ liệu của mình một chút, bằng cách sử dụng biến cờ làm biến toàn cầu;

giả sử đầu tiên tôi chèn 8 sau đó giá trị cờ tương ứng của nó là 1 sau đó chèn 12 giá trị lá cờ của nó = 2 sau đó chèn 3 của nó giá trị cờ = 3

tại inorder sử dụng BST như một chồng tôi phải xóa phần tử đã được chèn vào cuối cùng và theo bản ngã của tôi có giá trị cờ cao nhất.

Cũng lưu ý rằng phần tử cuối cùng được chèn sẽ không có bất kỳ phần tử con nào để việc xóa của nó khá dễ dàng.

Để tìm giá trị cờ cao nhất có sẵn với các nút, tôi đã thực hiện ngăn xếp inordertraversal bằng cách sử dụng ngăn xếp tốt hơn so với truyền tải đệ quy của nó.

Sau khi tìm thấy nút đó tương ứng với giá trị cờ cao nhất, tôi xóa nút đó. quá trình này được lặp lại cho đến khi root = NULL.