C++二叉树:链表描述方法；遍历方法

#include<iostream> using namespace std; template<class T> class BinaryTree; template<class T> class BinaryTreeNode{ friend BinaryTree<T>; public: BinaryTreeNode() {LeftChild =RightChild=0;} BinaryTreeNode(const T& e) {data=e; LeftChild = RightChild =0; } BinaryTreeNode(const T& e,BinaryTreeNode<T> *l, BinaryTreeNode<T> *r) {data =e; LeftChild =l; RightChild=r; } public: T data; BinaryTreeNode<T> *LeftChild;//左子树 BinaryTreeNode<T> *RightChild;//右子树 }; template <class T> class LinkedQueue; template <class T> class Node{ friend LinkedQueue<T>; private: T data; Node<T> *link; }; template <class T> class LinkedQueue{//逐层遍历时需要使用队列 public: LinkedQueue(){front=rear=0;} ~LinkedQueue(); bool IsEmpty()const {return (front)?false:true;} LinkedQueue<T>& Add(const T& X); LinkedQueue<T>& Delete(T& X); private: Node<T> *front; Node<T> *rear; }; int _count=0; template<class T> class BinaryTree{ public://二叉树的类定义 BinaryTree(){ root=0; } //~BinaryTree(); bool IsEmpty(){ return ((root)?false:true);} bool Root(T &x)const; void PreOrder(void (*Visit)(BinaryTreeNode<T> *u)) { PreOrder(Visit,root); } void InOrder(void (*Visit)(BinaryTreeNode<T> *u)) { InOrder(Visit,root); } void PostOrder(void (*Visit)(BinaryTreeNode<T> *u)) { PostOrder(Visit,root); } void PreOutput() { PreOrder(Output,root); } void InOutput() { InOrder(Output,root); } void PostOutput() { PostOrder(Output,root); } void LevelOrder(void (*Visit)(BinaryTreeNode<T> *u)); void LevelOutput() { LevelOrder(Output,root); } void MakeTree(const T& element,BinaryTree<T>& left,BinaryTree<T>& right); BinaryTreeNode<T>* Creat( int i1,int i2, int len,char pre[],char pin[],int n); int Post(char x,char pin[],int start,int N); int Height(BinaryTreeNode<T> *t); int Size(); BinaryTreeNode<T> *root; void PreOrder(void (*Visit)(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t); void InOrder(void (*Visit)(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t); void PostOrder(void (*Visit)(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t); void LevelOrder(void (*Visit)(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t); static void Add1(BinaryTreeNode<T> *t){_count++; } static void Output(BinaryTreeNode<T> *t){cout<<t->data<<" " ;} } ; template<class T> void BinaryTree<T>::PreOrder(void (*Visit) (BinaryTreeNode<T> *u), BinaryTreeNode<T> *t){ if(t){ Visit(t); PreOrder(Visit,t->LeftChild); PreOrder(Visit,t->RightChild); } } template<class T> void BinaryTree<T>::InOrder(void (*Visit)(BinaryTreeNode<T> *u),BinaryTreeNode<T> *t){ if(t){ InOrder(Visit,t->LeftChild); Visit(t); InOrder(Visit,t->RightChild); } } template<class T> void BinaryTree<T>::PostOrder(void (*Visit)(BinaryTreeNode<T> *u),BinaryTreeNode<T> *t){ if(t){ PostOrder(Visit,t->LeftChild); PostOrder(Visit,t->RightChild); Visit(t); } } template<class T> void BinaryTree<T>::LevelOrder(void (*Visit)(BinaryTreeNode<T> *u),BinaryTreeNode<T> *t){ LinkedQueue<BinaryTreeNode<T>*> Q; while(t){ Visit(t); if(t->LeftChild) Q.Add(t->LeftChild); if(t->RightChild) Q.Add(t->RightChild); if(!Q.IsEmpty()){Q.Delete(t); } else{ return; } } } template<class T> void BinaryTree<T>::MakeTree(const T& element,BinaryTree<T>& left,BinaryTree<T>& right){//合并树 root = new BinaryTreeNode<T>(element,left.root,right.root); left.root=right.root=0; } template<class T> int BinaryTree<T>::Post(char x, char pin[], int start,int N){ int i; for(i=start;i<N;i++) if(x==pin[i]) return i; } template<class T> BinaryTreeNode<T>* BinaryTree<T>::Creat( int i1,int i2, int len,char pre[],char pin[],int n){//创建树 int m,leftlen,rightlen; BinaryTreeNode<T> *t =new BinaryTreeNode<T>; if(len<=0){ t=0; }else{ t->data=pre[i1]; m=Post(pre[i1],pin,i2,n); leftlen=m-i2 ; rightlen=len-(leftlen+1); t->RightChild=Creat(i1+leftlen+1,m+1,rightlen,pre,pin,n); t->LeftChild= Creat(i1+1,i2,leftlen,pre,pin,n); } return t; } template<class T> int BinaryTree<T>::Height(BinaryTreeNode<T> *t){ if(!t) return 0; int hl=Height(t->LeftChild); int hr=Height(t->RightChild); if(hl>hr) return ++hl; else return ++hr; } template<class T> int BinaryTree<T>::Size(){ PreOrder(Add1,root); int temp=_count; return temp; } template<class T> LinkedQueue<T>:: ~LinkedQueue(){ Node<T> *next; while(front){ next=front->link; delete front; front =next; } } template<class T> LinkedQueue<T>& LinkedQueue<T>:: Add(const T& x){ Node<T> *p = new Node<T>; p->data=x; p->link =0; if(front) {rear->link=p;rear=p;} else {front=p; rear =p;} return *this; } template<class T> LinkedQueue<T>& LinkedQueue<T>:: Delete(T& x){ x= front->data; Node<T> *p=front; front=front->link; delete p; return *this; } int main(){ BinaryTree<char> a,b,x,y,z,e,f;//创建这些树 int n; y.MakeTree('a',a,a);//将a作为y的左右子树 z.MakeTree('d',a,a); e.MakeTree('e',y,z);//将y,z作为e的左右子树 f.MakeTree('b',a,a); x.MakeTree('c',e,f); cout<<"前序输出此二叉树："<<endl; x.PreOutput(); cout<<endl; cout<<"后序输出此二叉树："<<endl; x.PostOutput(); cout<<endl; cout<<"中序输出此二叉树："<<endl; x.InOutput(); cout<<endl; cout<<"逐层输出此二叉树："<<endl; x.LevelOutput(); cout<<endl; cout<<"二叉树的节点数目输出："<<endl; int count1=x.Size(); cout<<count1<<endl; cout<<"二叉树的高度输出："<<endl; int count2=x.Height(x.root); cout<<count2<<endl; cout<<"请输入数据大小："<<endl; cin>>n; char *pre=new char[n]; char *pin=new char[n]; cout<<"请输入前序："<<endl; for(int i=0;i<n;i++) cin>>pre[i]; cout<<"请输入中序："<<endl; for(int j=0;j<n;j++) cin>>pin[j]; cout<<"则后序输出："<<endl; b.root=b.Creat(0,0,n,pre,pin,n);//根据前序和后序将树创建 b.PostOutput(); cout<<endl; return 0; }