二叉树的建立和遍历c++语言非递归实现

#include<iostream> using namespace std; const int maxsize=30; template <class T> struct binode //树结点 { T data; binode<T>*lchilde,*rchilde; }; template <class T> class bitree { public: bitree(); ~bitree(); void preOrder(); //前序遍历 void inOrder(); //中序遍历 void postOrder(); //后序遍历 void levelOrder(); //层次遍历 private: binode<T>*root; //树的根结点 void creat(binode<T>*&root); //创建二叉树函数 void relese(binode<T>*root); //删除二叉树 }; void main() { bitree<char> tree,tree1,tree2,tree3; cout<<"按前序遍历输出:\n"; tree.preOrder(); cout<<"按中序遍历输出:\n"; tree1.inOrder(); cout<<"按后序遍历输出:\n"; tree2.postOrder(); cout<<"按层次遍历输出:\n"; tree3.levelOrder(); } template <class T> bitree<T>::bitree() { cout<<"按前序遍历输入:\n"; creat(root); } template <class T> void bitree<T>:: creat(binode<T>*&root) { char ch; cin>>ch; if(ch=='#') root=NULL; else { root=new binode<T>; root->data=ch; creat(root->lchilde); creat(root->rchilde); } } template <class T> bitree<T>::~bitree() { relese(root); } template <class T> void bitree<T>::relese(binode<T>*root) { if(root!=NULL) { relese(root->lchilde); relese(root->rchilde); delete root; } } template <class T> void bitree<T>::preOrder() { binode<T>* Data[maxsize]; int top=-1; while(root!=NULL||top!=-1) { while(root!=NULL) { cout<<root->data; Data[++top]=root; root=root->lchilde; } if(top!=-1) { root=Data[top--]; root=root->rchilde; } } cout<<"\n"; } template <class T> void bitree<T>::inOrder() { binode<T>* Data[maxsize]; int top=-1; while(root!=NULL||top!=-1) { while(root!=NULL) { Data[++top]=root; root=root->lchilde; } if(top!=-1) { root=Data[top--]; cout<<root->data; root=root->rchilde; } } cout<<"\n"; } template <class T> void bitree<T>::postOrder() { int top=-1; binode<T>*p; binode<T>* Data[maxsize]; do { while(root) { top++; if(top==maxsize) cout<<"上溢"; else { Data[top]=root; root=root->lchilde; } } p=NULL; int flag=true; while(top!=-1 && flag) { root=Data[top]; if(root->rchilde==p) { cout<<root->data; top--; p=root; } else { root=root->rchilde; flag=false; } } }while(top!=-1); cout<<"\n"; } template <class T> void bitree<T>::levelOrder() { int front; int rear; front=rear=0; binode<T>* Q[maxsize]; if(root==NULL) return; Q[++rear]=root; do { root=Q[++front]; cout<<root->data; if(root->lchilde!=NULL) Q[++rear]=root->lchilde; if(root->rchilde!=NULL) Q[++rear]=root->rchilde; }while(front!=rear); cout<<"\n"; }