二叉树层序遍历与递归
二叉树层序遍历用队列实现,可同递归算法一同实现怎么弄,此代码有问题,希望高手指教#include<iostream>
using namespace std;
const int MaxSize=50;
template<class T>
struct Node
{
T data;
Node<T> *lchild,*rchild;
};
template<class T>
class BiTree
{
public:
BiTree(){root=Creat(root);}//通过递归返回最后一个节点,每次返回栈顶的元素,最后返回根节点
~BiTree(){Release(root);}
void PreOrder(){PreOrder(root);}
void InOrder(){InOrder(root);}
void PostOrder(){PostOrder(root);}
void LeverOrder();
private:
Node<T> Q[MaxSize];
Node<T>*root;
Node<T>*Creat(Node<T>*bt);
void Release(Node<T>*bt);
void PreOrder(Node<T>*bt);
void InOrder(Node<T>*bt);
void PostOrder(Node<T>*bt);
//void LeverOrder(Node<T>*bt);
};
template<class T>
Node<T>*BiTree<T>::Creat(Node<T>*bt)//递归是通过堆栈而实现的
{
T ch;
cin>>ch;
if(ch=='#') bt=NULL;
else
{
bt=new Node<T>;
bt->data=ch;
bt->lchild=Creat(bt->lchild);//先生成左子树
bt->rchild=Creat(bt->rchild);//再生成右子树
}
return bt;
}
template<class T>
void BiTree<T>::Release(Node<T>*bt)
{
if(bt!=NULL)
{
Release(bt->lchild);
Release(bt->rchild);
delete bt;
}
}
template<class T>
void BiTree<T>::PreOrder(Node<T>*bt)
{
if(bt)
{
cout<<bt->data;
PreOrder(bt->lchild);
PreOrder(bt->rchild);
}
}
template<class T>
void BiTree<T>::InOrder(Node<T>*bt)
{
if(bt)
{
InOrder(bt->lchild);
cout<<bt->data;
InOrder(bt->rchild);
}
}
template<class T>
void BiTree<T>::PostOrder(Node<T>*bt)
{
if(bt)
{
PostOrder(bt->lchild);
PostOrder(bt->rchild);
cout<<bt->data;
}
}
template<class T>
void BiTree<T>::LeverOrder()
{
//Node<T> Q[MaxSize];
int front=-1;
int rear=-1;
if(root==NULL)throw "error";
Q[++rear]=root;
if(front!=rear)
{
Node<T>* q=Q[++front];
cout<<q->data;
if(q->lchild!=NULL) Q[++rear]=q->lchild;
if(q->rchild!=NULL) Q[++rear]=q->rchild;
}
}
int main()
{
try
{
BiTree<char> b;
cout<<"二叉树的前序遍历:";
b.PostOrder();
cout<<endl;
cout<<"二叉树的中序遍历:";
b.InOrder();
cout<<endl;
cout<<"二叉树的后序遍历:";
b.PostOrder();
cout<<"二叉树的层次遍历:";
b.LeverOrder();
}catch(const char *e)
{
cout<<e<<endl;
}
}