#include <iostream>
#include <deque>
#include <stack>
using namespace std;

struct BSTNode
{
 int  data;
 BSTNode * LChild,* RChild;
};
class BST
{
private:
 BSTNode *T;
public:
 ~BST();
 BSTNode * GetRoot();
 void BSTCreate();
 void BSTInsert(BSTNode *);
 int  BSTDepth(BSTNode *);//求树的深度 递归
 void Depth();//树的深度   非递归
 void BSTBFS();//广度优先遍历
 void PreOrder(BSTNode *);//递归 前序遍历
 void BSTPre();//前序遍历 非递归
 void InOrder(BSTNode *);//递归  中序遍历
 void BSTIn();//中序遍历 非递归
 void PostOrder(BSTNode *);// 递归 后续遍历
 void BSTPost();//后续遍历 双栈法
    void Post();//后序遍历  单栈
 void  BSTSearch();//查找 递归算法
 BSTNode * Search(BSTNode *,int);

};
BST::~BST()
{
 deque<BSTNode *> de;
 BSTNode *p=T;
 if (p)
 {
  if(p->LChild)
   de.push_back(p->LChild);
  if(p->RChild)
   de.push_back(p->RChild);
  delete p;
  while (!de.empty())
  {
   
   p=de.front();
   de.pop_front();
   if(p->LChild)
    de.push_back(p->LChild);
   if(p->RChild)
    de.push_back(p->RChild);
   delete p;
  }
   
 }

}
BSTNode * BST::GetRoot()
{
 return T;
}
void BST::BSTInsert(BSTNode *s )
{
 BSTNode *f=T;
    BSTNode *p=T;
 while (p)
 {
  f=p;
  if(s->data<p->data)
   p=p->LChild;
  else
   p=p->RChild;
 }
 if(T==NULL)
  T=s;
 else
  if(s->data<f->data)
   f->LChild=s;
  else
   f->RChild=s;
}
void BST::BSTCreate()
{
 T=NULL;
 int data;
 BSTNode *s;
 cout<<"请输入节点值并以0作为结束标志,创建一个二叉排序树"<<endl;
 cin>>data;
 while(data)
 {
  s=new BSTNode;
  s->LChild=s->RChild=NULL;
  s->data=data;
  BSTInsert(s);
  cout<<"请输入下一个节点的值："<<endl;
        cin>>data;
 }
 

}
int BST::BSTDepth(BSTNode *p)
{
 if(p)
 {
  int left=BSTDepth(p->LChild);
  int right=BSTDepth(p->RChild);
  if(left>right)
   return left+1;
  else
   return right+1;

 }
 return 0;

}
void BST::Depth()
{
 BSTNode * store[50];
 memset(store,0,50);
 int length=0;
 int depth=0;
 stack<BSTNode *> st;
 if (T)
 {
  
  st.push(T);
 
  while (!st.empty())
  {
   depth++;
   length=0;
   while (!st.empty())
   {
     
    BSTNode * p=st.top();
    st.pop();
    if (p->LChild)
     store[length++]=p->LChild;
    if (p->RChild)
    store[length++]=p->RChild;
    
   }
   for (int i=0;i<length;i++)
    st.push(store[i]);
  }
  cout<<"树的深度为："<<depth<<endl;

 
 }
 else
  
  cout<<"还未创建树！！"<<endl;
}
void BST::BSTBFS()
{
 cout<<"广度优先遍历"<<endl;
 deque<BSTNode *> de;
    BSTNode *p=T;
 de.push_back(p);
 while (!de.empty())
 {
   p=de.front();
   cout<<p->data<<"--->";
   de.pop_front();
   if (p->LChild)
    de.push_back(p->LChild);
   if(p->RChild)
    de.push_back(p->RChild);
 }
 cout<<endl;

}
void BST::PreOrder(BSTNode * p)
{
 if(p)
 {
  cout<<p->data<<"--->";
  PreOrder(p->LChild);
  PreOrder(p->RChild);
 }
}
void BST::BSTPre()
{
 cout<<"前序遍历 非递归"<<endl;
 stack<BSTNode *> st;
 st.push(T);
 while(!st.empty())
 {
  BSTNode *P=st.top();
  st.pop();
  cout<<P->data<<"--->";
  if (P->RChild)
   st.push(P->RChild);
  if(P->LChild)
   st.push(P->LChild);
 }
 cout<<endl;
}
void BST::InOrder(BSTNode * p)
{
 if(p)
 {
  
  InOrder(p->LChild);
  cout<<p->data<<"--->";
  InOrder(p->RChild);
 }
}
void BST::BSTIn()
{
 cout<<"中序遍历 非递归"<<endl;
 stack<BSTNode *>st;
 st.push(T);
 while (!st.empty())
 {
  BSTNode *p=st.top();
  while (p->LChild)
  {
   p=p->LChild;
   st.push(p);

  }
  while (!st.empty())
  {
   BSTNode *q=st.top();
   st.pop();
   cout<<q->data<<"--->";
   if(q->RChild)
   {
    q=q->RChild;
    st.push(q);
    break;

   }

  }
 }
 cout<<endl;

}
void BST::PostOrder(BSTNode * p)
{
 if(p)
 {
  
  PostOrder(p->LChild);
     PostOrder(p->RChild);
  cout<<p->data<<"--->";
 }

}
void BST::BSTPost()
{
 cout<<"后序遍历 非递归"<<endl;
 stack<BSTNode*> st2;
 stack<BSTNode *> st;
 st.push(T);
 while(!st.empty())
 {
  BSTNode *P=st.top();
  st.pop();
  st2.push(P);
  //cout<<P->data<<"--->";
  if(P->LChild)
   st.push(P->LChild);
  if (P->RChild)
   st.push(P->RChild);
 
 }
 while (!st2.empty())
 {
  BSTNode *q=st2.top();
  st2.pop();
  cout<<q->data<<"---->";

 }
 cout<<endl;
 

}
void BST::Post()
{
 cout<<"后续遍历 非递归"<<endl;
 stack<BSTNode *>st;
 st.push(T);
 while (!st.empty())
 {
  BSTNode *p=st.top();
  while (p->LChild||p->RChild)
  {
   if (p->LChild)
    p=p->LChild;
   else
    p=p->RChild;
   
   st.push(p);
   
  }
  while (!st.empty())
  {
   BSTNode *q=st.top();
   st.pop();
   if(!st.empty())
   {
    BSTNode *f=st.top();
    cout<<q->data<<"--->";

     if (q==f->LChild)
     {
      //cout<<q->data<<"---->";
      if (f->RChild)
      {
       st.push(f->RChild);
           break;

      }
     
     }
     
   

   }
   
   else
   cout<<q->data<<endl;

  
  }
 }
 

}
BSTNode * BST::Search(BSTNode *p,int x)
{
 if(p==NULL||p->data==x)
  return p;
 else if(x<p->data)
  return Search(p->LChild,x);
 else
  return Search(p->RChild,x);

}
void BST::BSTSearch()
{

 int key;
 cout<<"请输入所要查找结点的关键字："<<endl;
 cin>>key;
 BSTNode * p=Search(T,key);
 if (p)
 {
  cout<<"查找结点的数据为："<<p->data;

 }
 else
  cout<<"所查找的节点不存在！"<<endl;
}

int main()
{
 BST  bst;
 bst.BSTCreate();
 bst.Depth();
 //cout<<"树的深度为:"<<bst.BSTDepth(bst.GetRoot())<<endl;
    //bst.PreOrder(bst.GetRoot());
 //bst.InOrder(bst.GetRoot());
 //bst.PostOrder(bst.GetRoot());
 //bst.BSTBFS();
 //bst.BSTPre();
 //bst.BSTIn();
 //bst.BSTPost();
 //bst.Post();
 //bst.BSTSearch();
 return 0;
}