bst.h

该压缩文件夹内有诸多常用算法和数据结构的c++模板编程实现

#ifndef BST_H
#define BST_H

#include<iostream.h>
#include<math.h>
#include<iomanip.h>
#include"lQueue.h"
template<class T>
class BSTNode
{
public:
	T info;
	BSTNode<T> *left,*right;
	BSTNode(T el,BSTNode<T> *l=NULL,BSTNode<T> *r=NULL)
	{
		info=el;
		left=l;
		right=r;
	}
};
template<class T>
class BST
{
private:
	BSTNode<T> *root;
	bool isPowerTwo(int el)
	{
		for(1;el>1;el/=2)
			if(el%2!=0)
				return false;
		return true;
	}
public:
	BST(BSTNode<T> *r=NULL)
	{
		root=r;
	}
	BSTNode<T>* getRoot()	{return root;}
	BSTNode<T>* serch(T el)
	{
		lQueue<BSTNode<T>*> a;
		BSTNode<T>* p=root;
		while(p!=NULL)
		{
			if(p->info==el)
				return p;
			if(p->left!=NULL)
				a.enqueue(p->left);
			if(p->right!=NULL)
				a.enqueue(p->right);
			if(!a.isEmpty())
				p=a.dequeue();
			else
				break;
		}
		return NULL;
	}
	void insert(int el)
	{
		BSTNode<T> *p=root,*pre=NULL;
		while(p!=NULL)
		{
			pre=p;
			if(p->info<el)
				p=p->right;
			else
				p=p->left;
		}
		if(root==NULL)
			root=new BSTNode<T>(el);
		else if(pre->info<el)
			pre->right=new BSTNode<T>(el);
		else 
			pre->left=new BSTNode<T>(el);
	}
	void delBSTNode(T el)
	{
		BSTNode<T>* p=serch(el);
		if(p==NULL)
			cout<<"No such a BSTNode!"<<endl;
		else if(p->left==NULL&&p->right==NULL)
		{
			p=NULL;
		}
		else if(p->left!=NULL&&p->right==NULL)
		{ 
			BSTNode<T>* p2=p->left;
			p->info=p2->info;
			p->left=p2->left;
			p->right=p2->right;
			delete p2;
		}
		else if(p->left==NULL&&p->right!=NULL)
		{
			BSTNode<T>* p2=p->right;
			p->info=p2->info;
			p->left=p2->left;
			p->right=p2->right;
			delete p2;
		}
		else
		{	
			BSTNode<T> *p2=p->left;
			BSTNode<T> *p3=p->right;	
			p->info=p2->info;
			p->left=p2->left;
			p->right=p2->right;
			delete p2;
			while(p->right!=NULL)
				p=p->right;
			p->right=p3;
		}
	}
	int nodeNumber()
	{
		BSTNode<T> *ro=root;
		int i=0;
		if(ro==NULL)
			return 0;
		else
		{
		
			lQueue<BSTNode<T>*> a;
			a.enqueue(ro);
			while(!a.isEmpty())
			{
				ro=a.dequeue();
				i++;
				if(ro->left!=NULL)
					a.enqueue(ro->left);
				if(ro->right!=NULL)
					a.enqueue(ro->right);
			}
			return i;
		}
	}
	int height(BSTNode<T> *ro)
	{
		if(ro==NULL)
			return 0;
		else if(ro->left==NULL&&ro->right==NULL)
			return 1;
		else
		{
			int l=height(ro->left),r=height(ro->right);
			if(l>r)
				return 1+l;
			else 
				return 1+r;
		}

	}
	bool isBalance(BSTNode<T>* r)
	{
		if(r==NULL)
			return true;
		else
		{
			int a=height(r->left),b=height(r->right);
			if(a-b>=2||a-b<=-2)
				return false;
			isBalance(r->left);
			isBalance(r->right);
			return true;
		}
	}
	void visualPrint()
	{
		lQueue<BSTNode<T>*> s;
		BSTNode<T> *r=root;
		int h=height(root),i=1,j=1;
		double a=pow(2,h)-1;
		while(i<=a)
		{
			if(isPowerTwo(i))
			{
				cout<<setw(int(pow(2,h)/pow(2,j)));
				if(r==NULL)
					cout<<" ";
				else	cout<<r->info;
			}
			else
			{
				cout<<setw(int(pow(2,h)/pow(2,j-1)));
				if(r==NULL)
					cout<<" ";
				else	cout<<r->info;
			}
			if(isPowerTwo(i+1))
			{
				cout<<endl;
				j++;
			}
			if(r==NULL)
			{
				s.enqueue(NULL);
				s.enqueue(NULL);
			}
			else
			{
				s.enqueue(r->left);
				s.enqueue(r->right);
			}
			r=s.dequeue();
			i++;
		}
	}
};

#endif