#include "BiSearchTree.h"
void main(void){ BiSearchTree<int>searchTree; int a[]={18,14,24,5,16,20,38,7,30,10,35},n=11; for(int i=0;i<n;i++) searchTree.Insert(a[i]); searchTree.PrintVTree(); cout<<endl; cout<<"非递归前序遍历:"<<endl; searchTree.PreOrder(); cout<<endl; cout<<"非递归后序遍历:"<<endl; searchTree.PostOrder(); cout<<endl; cout<<" 删除24"; searchTree.Delete(a[2]); searchTree.PrintVTree(); cout<<endl; } //BiSearchTree.h #include "LinStack.h" #include<math.h>
struct Info{ int xIndent; int yLevel; }; template<typename T>class BiSearchTree{ private: BiTreeNode<T> *root; void PreOrder(BiTreeNode<T> *&t); void InOrder(BiTreeNode<T> *&t); void PostOrder(BiTreeNode<T> *&t); void Insert(BiTreeNode<T> *&ptr,const T &item); void Delete(BiTreeNode<T> *&ptr,const T &item); void PrintVTree(BiTreeNode<T> *&t); public: BiSearchTree():root(NULL){}; ~BiSearchTree(){}; void PrintVTree(){PrintVTree(root);} BiTreeNode<T> *&GetRoot(){return root;} void PreOrder(){ PreOrder(root);} void PostOrder(){ PostOrder(root);} BiTreeNode<T> *&Find(const T &item); void Insert(const T &item){ Insert(GetRoot(),item);} void Delete(const T &item){ Delete(GetRoot(),item);} }; template<typename T>void BiSearchTree<T>::PrintVTree(BiTreeNode<T> *&t){ int screenWidth=64; int dataWidth=2; LinQueue<Info> QI; LinQueue<BiTreeNode<T>*> Q; BiTreeNode<T> *p; Info s,s1,s2; int offset,level=-1,len,i; Q.Insert(t); s.xIndent=screenWidth/dataWidth; s.yLevel=0; QI.Insert(s); while(!Q.Empty()&&!QI.Empty()) { s2=s; p=Q.Delete(); s=QI.Delete(); if(s.yLevel!=level){ cout<<"\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->Left()!=NULL) { Q.Insert(p->Left()); s1.yLevel=s.yLevel+1; offset=screenWidth/(int)pow(dataWidth,s1.yLevel+1); s1.xIndent=s.xIndent-offset; QI.Insert(s1); } if(p->Right()!=NULL) { Q.Insert(p->Right()); s1.yLevel=s.yLevel+1; offset=screenWidth/(int)pow(dataWidth,s1.yLevel+1); s1.xIndent=s.xIndent+offset; QI.Insert(s1); } } } template<typename T>BiTreeNode<T> *&BiSearchTree<T>::Find(const T &item) { if(root!=NULL) { BiTreeNode<T> *temp=root; while(temp!=NUll) { if(temp->data==item) return temp; if(temp->data<item) temp=temp->Right(); else temp=temp->Left(); } } return NULL; } template<typename T>void BiSearchTree<T>::Insert(BiTreeNode<T> *&ptr,const T &item) { if(ptr==NULL) ptr=new BiTreeNode<T>(item); else if(item<ptr->data) Insert(ptr->Left(),item); else if(item>ptr->data) Insert(ptr->Right(),item); } template<typename T>void BiSearchTree<T>::Delete(BiTreeNode<T> *&ptr,const T &item) { BiTreeNode<T> *temp; if(ptr!=NULL){ if(ptr->data<item) Delete(ptr->Right(),item); else if(ptr->data>item) Delete(ptr->Left(),item); else if(ptr->Left()!=NULL&&ptr->Right()!=NULL){ BiTreeNode<T> *min; min=ptr->Right(); while(min->Left()!=NULL) min=min->Left(); ptr->data=min->data; Delete(ptr->Right(),min->data); } else{ temp=ptr; if(ptr->Left()==NULL) ptr=ptr->Right(); else if(ptr->Right()==NULL) ptr=ptr->Left(); delete temp; } } } template<typename T>void BiSearchTree<T>::PreOrder(BiTreeNode<T> *&ptr){ LinStack<BiTreeNode<T>*> s; BiTreeNode<T> *p; p=ptr; while(p!=NULL||!s.IsEmpty()) { while(p!=NULL){ cout<<p->data<<'\t'; s.Push(p); p=p->Left(); } p=s.pop(); p=p->Right(); } } template<typename T>void BiSearchTree<T>::PostOrder(BiTreeNode<T> *&ptr){ LinStack<BiTreeNode<T>*> s; BiTreeNode<T> *p; int tag[100],top=-1; p=ptr; while(p!=NULL||!s.IsEmpty()){ while(p!=NULL){ s.Push(p); tag[++top]=0; p=p->Left(); } if(top>-1) if(tag[top]==1){ cout<<s.GetTop()->data<<'\t'; s.pop(); top--; } else{ p=s.GetTop(); if(top>-1){ tag[top]=1; p=p->Right(); } } } } //LinQueue.h #include<iostream> #include<stdlib.h> using namespace std;
template<typename T>class LinQueue; template<typename T>class QueueNode{ QueueNode<T> *next; T data; public: QueueNode(const T &item,QueueNode<T> *perNext=NULL); ~QueueNode(){}; friend class LinQueue<T>; }; template<typename T>QueueNode<T>::QueueNode(const T &item,QueueNode<T> *perNext=NULL){ data=item; next=perNext; } template<typename T>class LinQueue{ QueueNode<T> *rear,*front; int size; public: LinQueue(); ~LinQueue(); void Insert(const T &item); T Delete(); int Empty(){ return size<=0; } void MakeEmpty(); }; template<typename T>LinQueue<T>::LinQueue(){ rear=front=NULL; size=0; } template<typename T>LinQueue<T>::~LinQueue(){ MakeEmpty(); } template<typename T>void LinQueue<T>::MakeEmpty(){ QueueNode<T> *temp; while(front!=NULL){ temp=front; front=front->next; delete temp; } } template<typename T>void LinQueue<T>::Insert(const T &item){ QueueNode<T> *p; p=new QueueNode<T>(item,NULL); if(front==NULL) front=rear=p; else {rear->next=p; rear=p;} size++; } template<typename T>T LinQueue<T>::Delete(){ QueueNode<T> *temp; if(size==0) exit(1); temp=front; T data=temp->data; front=front->next; delete temp; size--; return data; } //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(); bool IsEmpty(){return top==NULL;} void ClerStack(); T GetTop(){ return top->data;} }; 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=top->next; delete temp; size--; return data; } //Tree.h #include<iostream> using namespace std;
template<typename T>class BiTreeNode{ private: BiTreeNode<T> *leftChild; BiTreeNode<T> *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(){} BiTreeNode<T> *&Left(){return leftChild;} BiTreeNode<T> *&Right(){return rightChild;} };
