//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; 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); 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);} }; 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> *b,int &c){ if(b!=NULL){ Countleaf(b->leftChild,c); Countleaf(b->rightChild,c); if(b->leftChild==NULL&&b->rightChild==NULL) c++; } } 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; } } } }
//LinkQueue.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; } //LinkStack.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; } #include "Tree.h"
int main(){ BinaryTree<int> b; const int n=5; int a[n]={10,6,2,3,11}; 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"; cout<<b.Depth(); cout<<endl; cout<<"二叉树叶结点的个树:\n"; b.Countleaf(); return 0; }
