C++ 实现求二叉树的深度及遍利

#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);
? 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)
???? {
????? 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();
?cout<<"树的深度为:"<<bst.BSTDepth(bst.GetRoot())<<endl;
?bst.Depth();
?//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;
}