#include "Tree.h"

int main(){ BinaryTree<int> b; const int n=11; int a[]={18,14,24,5,16,20,38,7,30,10,35}; for(int i=0;i<n;i++) b.CreatTree(a[i]); cout<<"打印二叉排序树:\n"; b.PrinTree(); cout<<endl; b.PrintVTree(); cout<<endl<<endl; cout<<"二叉树非递归前序遍历:\n"; b.Preorder(); cout<<endl; cout<<"中序遍历:\n"; b.Inoder(); cout<<endl; cout<<"非递归中序遍历:\n"; b.Inpreorder(); cout<<endl; cout<<"后序遍历:\n"; b.PostPerdor(); cout<<endl; cout<<"非递归后序遍历:\n"; b.POSTindor(); cout<<endl; cout<<"层序遍历:\n"; b.CxIndor(); cout<<endl; /*cout<<"中序线索二叉树\n"; b.InOrder(); cout<<endl;*/ cout<<"二叉树的深度:\n"; cout<<b.Depth(); cout<<endl; cout<<"二叉树叶结点的个树:\n"; b.Countleaf(); cout<<" 删除24"; b.Delete(a[2]); b.PrintVTree(); cout<<endl; return 0; } 下面为 LinQueue.h

#include<iostream> #include<assert.h> using namespace std;

template<typename T>class Queue; template<typename T>class Node{ T info; Node<T> *link; public: Node(T data=0,Node *l=NULL); friend class Queue<T>; }; template<typename T> Node<T>::Node(T data,Node *l){ info=data; link=l; } template<typename T>class Queue{ Node<T> *front,*rear; public: Queue(){rear=front=NULL;} ~Queue(); bool IsEmpty(){ return front==NULL;} void EnQue(const T &data); T DeQue(); T GetFront(); void MakeEmpty(); }; template<typename T>void Queue<T>::MakeEmpty(){ Node<T> *temp; while(front!=NULL){ temp=front;front=front->link;delete temp; } } template<typename T>Queue<T>::~Queue(){MakeEmpty();} template<typename T>void Queue<T>::EnQue(const T &data){ if(front==NULL) front=rear=new Node<T>(data,NULL); else rear=rear->link=new Node<T>(data,NULL); } template<typename T>T Queue<T>::DeQue(){ assert(!IsEmpty()); Node<T> *temp=front; T data=temp->info; front=front->link; delete temp; return data; } template<typename T>T Queue<T>::GetFront(){ assert(!IsEmpty()); return front->info; } 下面为 "LinStack.h" #include<iostream> #include<stdlib.h> using namespace std;

template<typename T>class LinStack; template<typename T>class StackNode{ StackNode<T> *next; public: T data; StackNode(const T &item,StackNode<T> *perNext=NULL); ~StackNode(){}; friend class LinStack<T>; }; template<typename T>StackNode<T>::StackNode(const T &item,StackNode<T> *perNext=NULL){ data=item; next=perNext; } template<typename T>class LinStack{ StackNode<T> *top; int size; public: LinStack(); ~LinStack(); void MakeEmpty(); void Push(const T &item); T pop(); T GetTop(){ if(size==0){ cerr<<"堆栈已空!"<<endl; exit(1); } return top->data; } int Empty(){ return size<=0;} }; template<typename T>LinStack<T>::LinStack(){ top=NULL; size=0; } template<typename T>LinStack<T>::~LinStack(){ MakeEmpty(); } template<typename T>void LinStack<T>::MakeEmpty(){ StackNode<T> *temp; while(top!=NULL){ temp=top; top=top->next; delete temp; } } template<typename T>void LinStack<T>::Push(const T &item){ StackNode<T> *newNode; newNode=new StackNode<T>(item,top); top=newNode; size++; } template<typename T>T LinStack<T>::pop(){ if(size==0){ cerr<<"堆栈已空!"<<endl; exit(1); } StackNode<T> *temp; temp=top; T data=temp->data; top=temp->next; delete temp; size--; return data; } 下面为 Tree.h #include<iostream> #include<math.h> #include "LinQueue.h" #include "LinStack.h" using namespace std;

struct Info{ int xIndent; int yLevel; }; template<typename T>class BinaryTree; template<typename T>class BiTreeNode{ private: BiTreeNode<T> *leftChild,*rightChild; int rTag,lTag; public: T data; BiTreeNode(){ leftChild=NULL;rightChild=NULL;} BiTreeNode(T item,BiTreeNode<T> *left=NULL,BiTreeNode<T> *right=NULL): data(item),leftChild(left),rightChild(right){} ~BiTreeNode(){} friend class BinaryTree<T>; }; template<typename T>class BinaryTree{ private: BiTreeNode<T> *root,*parent; void Insert(BiTreeNode<T> *&b,T item); void PostPerdor(BiTreeNode<T> *b); void Inoder(BiTreeNode<T> *b); void PrinTree(BiTreeNode<T> *b,int level); int Depth(BiTreeNode<T> *b); int count; void Countleaf(BiTreeNode<T> *b,int &c); void CxIndor(BiTreeNode<T> *b); void PrintVTree(BiTreeNode<T> *&t); void Preorder(BiTreeNode<T> *&t); void Inpreorder(BiTreeNode<T> *&t); void POSTindor(BiTreeNode<T> *&t); /*void InTread(BiTreeNode<T> *&t);//中序非递归线索二叉树 void InOrder(BiTreeNode<T> *t);//中序周游二叉树*/ void Delete(BiTreeNode<T> *&ptr,const T &item); public: BinaryTree(){ root=NULL;count=0;} ~BinaryTree(){}; int Research(T item); void CreatTree(T item); void PostPerdor(){PostPerdor(root);} void Inoder(){Inoder(root);} void PrinTree(){PrinTree(root,0);} int Depth(){return Depth(root);} void Countleaf(){Countleaf(root,count);cout<<count<<endl;} void CxIndor(){CxIndor(root);} void PrintVTree(){PrintVTree(root);} void Preorder(){Preorder(root);} void Inpreorder(){Inpreorder(root);} void POSTindor(){POSTindor(root);} /*void InOrder(){InOrder(root);}*/ void Delete(const T &item){ Delete(root,item);} }; template<typename T>void BinaryTree<T>::Insert(BiTreeNode<T> *&b,T item){ BiTreeNode<T> *s; if(Research(item)==0){ s=new BiTreeNode<T>(item); if(parent==NULL) b=s; else if(parent->data>item) parent->leftChild=s; else parent->rightChild=s; } } template<typename T>int BinaryTree<T>::Research(T item){ BiTreeNode<T> *ptr=root; parent=NULL; while(ptr){ if(ptr->data==item) {parent=ptr;return 1;} else if(ptr->data>item) {parent=ptr;ptr=ptr->leftChild;} else {parent=ptr;ptr=ptr->rightChild;} } return 0; } template<typename T>void BinaryTree<T>::CreatTree(T item){ Insert(root,item); } template<typename T>void BinaryTree<T>::PostPerdor(BiTreeNode<T> *b){ if(b!=NULL){ PostPerdor(b->leftChild); PostPerdor(b->rightChild); cout<<b->data<<"\t"; } } template<typename T>void BinaryTree<T>::Inoder(BiTreeNode<T> *b){ if(b!=NULL){ Inoder(b->leftChild); cout<<b->data<<"\t"; Inoder(b->rightChild); } } template<typename T>void BinaryTree<T>::PrinTree(BiTreeNode<T> *b,int level){ if(b!=NULL) { PrinTree(b->rightChild,level+1); if(level!=0){ for(int i=0;i<6*(level-1);i++)cout<<" "; cout<<"-----"; } cout<<b->data<<endl; PrinTree(b->leftChild,level+1); } } template<typename T>int BinaryTree<T>::Depth(BiTreeNode<T> *b){ int depth=0,num1,num2; if(b==NULL) return depth; else{ num1=Depth(b->leftChild)+1; num2=Depth(b->rightChild)+1; if(num1>num2) depth=num1; else depth=num2; } return depth; } template<typename T>void BinaryTree<T>::Countleaf(BiTreeNode<T> *t,int &c){ LinStack<BiTreeNode<T>*> S; BiTreeNode<T> *p; int tag[100],i=-1; p=t; c=0; while(p!=NULL||!S.Empty()){ while(p!=NULL){ S.Push(p); tag[++i]=0; p=p->leftChild; } if(i>-1) if(tag[i]==1) { if(S.GetTop()->leftChild==NULL&&S.GetTop()->rightChild==NULL) c++; S.pop(); i--; } else { p=S.GetTop(); if(i>-1) {p=p->rightChild; tag[i]=1; } } } } template<typename T>void BinaryTree<T>::CxIndor(BiTreeNode<T> *b){ Queue<BiTreeNode<T>*> q; BiTreeNode<T> *p; q.EnQue(b); while(!q.IsEmpty()){ p=q.DeQue(); cout<<p->data<<"\t"; if(p->leftChild!=NULL) { q.EnQue(p->leftChild); } if(p->rightChild!=NULL) { q.EnQue(p->rightChild); } } } template<typename T>void BinaryTree<T>::PrintVTree(BiTreeNode<T> *&t){ int screenWidth=64; int dataWidth=2; Queue<BiTreeNode<T> *> Q; Queue<Info> QI; BiTreeNode<T> *p; Info s,s1,s2; double offset,level=-1,i; Q.EnQue(t); s.xIndent=screenWidth/dataWidth; s.yLevel=0; QI.EnQue(s); while(!Q.IsEmpty()&&!QI.IsEmpty()) { s2=s; p=Q.DeQue(); s=QI.DeQue(); if(s.yLevel!=level){ cout<<"\n\n第"<<s.yLevel<<"层"; level=s.yLevel; for(i=0;i<s.xIndent-1;i++) cout<<" "; } else for(i=0;i<s.xIndent-s2.xIndent;i++) cout<<" "; cout<<p->data; if(p->leftChild!=NULL) { Q.EnQue(p->leftChild); s1.yLevel=s.yLevel+1; offset=screenWidth/pow(dataWidth,s1.yLevel+1); s1.xIndent=s.xIndent-offset; QI.EnQue(s1); } if(p->rightChild!=NULL) { Q.EnQue(p->rightChild); s1.yLevel=s.yLevel+1; offset=screenWidth/pow(dataWidth,s1.yLevel+1); s1.xIndent=s.xIndent+offset; QI.EnQue(s1); } } } template<typename T>void BinaryTree<T>::Preorder(BiTreeNode<T> *&t){ LinStack<BiTreeNode<T>*> S; BiTreeNode<T> *p; p=t; while(p!=NULL||!S.Empty()){ while(p!=NULL) { cout<<p->data<<'\t'; S.Push(p); p=p->leftChild; } p=S.pop(); p=p->rightChild; } } template<typename T>void BinaryTree<T>::Inpreorder(BiTreeNode<T> *&t){ LinStack<BiTreeNode<T>*> S; BiTreeNode<T> *p; p=t; while(p!=NULL||!S.Empty()){ while(p!=NULL) { S.Push(p); p=p->leftChild; } p=S.pop(); cout<<p->data<<'\t'; p=p->rightChild; } } template<typename T>void BinaryTree<T>::POSTindor(BiTreeNode<T> *&t){ LinStack<BiTreeNode<T>*> S; BiTreeNode<T> *p; int tag[100],i=-1; p=t; while(p!=NULL||!S.Empty()){ while(p!=NULL){ S.Push(p); tag[++i]=0; p=p->leftChild; } if(i>-1) if(tag[i]==1) { cout<<S.GetTop()->data<<'\t'; S.pop(); i--; } else { p=S.GetTop(); if(i>-1) {p=p->rightChild; tag[i]=1; } } } } /*template<typename T>void BinaryTree<T>::InTread(BiTreeNode<T> *&t){ LinStack<BiTreeNode<T>*> S; BiTreeNode<T> *ptr; t=NULL; ptr=t; while(1) { while(ptr!=NULL) { S.Push(ptr); ptr=ptr->leftChild; } if(S.Empty()) break; else{ ptr=S.GetTop(); S.pop(); if(t!=NULL) { if(t->rightChild==NULL) { t->rTag=1; t->rightChild=ptr; } else t->rTag=0; if(ptr->leftChild==NULL) { ptr->lTag=1; ptr->leftChild=t; } else ptr->lTag=0; } t=ptr; ptr=ptr->rightChild; } } t->rTag=0; } template<typename T>void BinaryTree<T>::InOrder(BiTreeNode<T> *t) { BiTreeNode<T> *p; InTread(t); if(t==NULL) exit(1); else p=t; while(p->leftChild!=NULL) p=p->leftChild; while(1){ cout<<p->data<<'\t'; if(p->rightChild==NULL) break; if(p->rTag==1) p=p->rightChild; else{ p=p->rightChild; while(p->lTag==0) p=p->leftChild; } } }*/ template<typename T>void BinaryTree<T>::Delete(BiTreeNode<T> *&ptr,const T &item) { BiTreeNode<T> *temp; if(ptr!=NULL){ if(ptr->data<item) Delete(ptr->rightChild,item); else if(ptr->data>item) Delete(ptr->leftChild,item); else if(ptr->leftChild!=NULL&&ptr->rightChild!=NULL){ BiTreeNode<T> *min; min=ptr->rightChild; while(min->leftChild!=NULL) min=min->leftChild; ptr->data=min->data; Delete(ptr->rightChild,min->data); } else{ temp=ptr; if(ptr->leftChild==NULL) ptr=ptr->rightChild; else if(ptr->rightChild==NULL) ptr=ptr->leftChild; delete temp; } } } 大家复制程序上机运行去。这个绝对经典