gsort.h

可能是能找到的处理速度最快

#ifndef _GSORT_H_
#define _GSORT_H_
//#include"tlink.h"
#include<stdio.h>
/*
Type T must provide the following methous:
	-					:	Compare operator ,return -1,0,1
	(*func)()			:	Visit operate function
	Copy Constructor	:	a copy constructor to copy objects if in Own mode
*/
template<class T,class T2=T> class CTree;
template<class T,class T2=T> class CTreeNode
{
	T *data;
	CTreeNode<T,T2> *left;
	CTreeNode<T,T2> *right;
	bool Own;
	int balance;
//	int Count;
public:
	T *Data()
	{
		return data;
	}
	CTreeNode():
	{
		data=NULL;
		left=NULL;
		right=NULL;
		Own=FALSE;
		balance=0;
	}
	CTreeNode(T *t,bool O=false,CTreeNode<T,T2> *l=NULL,CTreeNode<T,T2> *r=NULL)	// point-to version
	{
		Own=O;
		if (Own)
			data=new T(*t);
		else
			data=t;
		left=l;
		right=r;
		balance=0;
	}
	CTreeNode(T &t,CTreeNode<T,T2> *l=NULL,CTreeNode<T,T2> *r=NULL)	// copy version
	{
		Own=true;
		data=new T(t);
		left=l;
		right=r;
		balance=0;
	}
	~CTreeNode()
	{
		if (Own)
			delete data;
	}
	friend void SearchAndAdd(CTreeNode<T,T2> *t1, CTree<T,T2>  &t2, CTree<T,T2> &NewTree);
	friend void Copy(CTreeNode<T,T2> *t1, CTree<T,T2> &NewTree);
	friend class CTree<T,T2>;
};

enum SearchType {Equal,Left,Right};

template<class T,class T2=T>
class CTree
{
	CTreeNode<T,T2> *Root;
	CTreeNode<T,T2> *Current;
	bool Own;
	int DelDuplicate;
	bool ShowMsg;
	CTreeNode<T,T2> *Add(CTreeNode<T,T2> *, CTreeNode<T,T2> *t =NULL);
	void Clear(CTreeNode<T,T2> *t=NULL);
protected:
	unsigned long count;
public:
	unsigned long Count()
	{
		return count;
	}
	T *Add(T *p)	// point-to version
	{
		CTreeNode<T,T2> *p2=new CTreeNode<T,T2>(p,Own);
		if(Root)
		{
			CTreeNode<T,T2> *p3=Add(p2);
			if (p3!=p2)
				delete p2;
			return p3->data;
		}
		else
		{
			Root=p2;
			return p2->data;
		}
	}
	T *Add(T &p)		// copy version
	{
		CTreeNode<T,T2> *p2=new CTreeNode<T,T2>(p);
		if(Root)
		{
			CTreeNode<T,T2> *p3=Add(p2);
			if (p3!=p2)
				delete p2;
			return p3->data;
		}
		else
		{
			Root=p2;
			return p2->data;
		}
	}
	CTree()
	{
		Root=NULL;
		DelDuplicate=true;
		Current=NULL;
		Own=FALSE;
		ShowMsg=true;
		count=0;
	}
	CTree(bool O,bool NoDulp=true,int=true)
	{
		Own=O;
		DelDuplicate=NoDulp;
		Root=NULL;
		Current=NULL;
		count=0;
	}
	~CTree()
	{
		if (Root)
		{
			Clear();
			delete Root;
		}
	}
	void LeftMidRight(void (*func)(T *),CTreeNode<T,T2> *t=NULL);
	void RightMidLeft(void (*func)(T *),CTreeNode<T,T2> *t=NULL);
	void MidLeftRight(void (*func)(T *),CTreeNode<T,T2> *t=NULL);
//	T *FindFirst(T &,SearchType tp=Equal,CTreeNode<T,T2> *t=0);
//	T *FindNext(T &,SearchType tp=Equal);
	T *FindFirst(T2 &,SearchType tp=Equal,CTreeNode<T,T2> *t=0);
	T *FindNext(T2 &,SearchType tp=Equal);
	friend CTree operator&(CTree &tree1, CTree &tree2);		// get the same part and build a tree, compare by data only
	CTree &operator=(CTree &tree2);				
	CTree(CTree &tree2);					// copy constructor , copy pointer only
	CTreeNode<T,T2> *CurrentNode()
	{
		return Current;
	}
};
template<class T, class T2>
CTreeNode<T,T2> *CTree<T,T2>::Add(CTreeNode<T,T2> *tree2,CTreeNode<T,T2> *tree1)// tree2 add to tree1
{   
	if(tree2==NULL)
		return NULL;
	CTreeNode<T,T2> *most_recent=Root,*most_recent_parent=NULL,*parent=NULL,*new_Root=NULL;
	CTreeNode<T,T2> *p=NULL;//,*tree1=Root;
	bool AdjustBalance=false;
	if (tree1==NULL)
		tree1=Root;
	if (tree1==Root)
		AdjustBalance=true;
	while(tree1)
	{
		if (tree1->balance!= 0)
		{
			most_recent = tree1;
			most_recent_parent = parent;
		}
		int a=*(tree2->data)-*(tree1->data);
		if (a==0)
		{
			if (DelDuplicate)
				return tree1;
		}
		if (a<=0)
		{
			if (tree1->left)
			{
				parent=tree1;
				tree1=tree1->left;
			}
			else
			{
				tree1->left=tree2;
				break;
			}
		}
		else
		{
			if ( tree1->right)
			{
				parent=tree1;
				tree1=tree1->right;
			}
			else
			{
				tree1->right=tree2;
				break;
			}
		}
	}
	count++;
	if (!AdjustBalance)
		return tree2;
	int rebal_direc;
	if ( *(tree2->data)-*(most_recent->data) > 0)
	{
		tree1 = most_recent->right;
		rebal_direc = -1;
	}
	else
	{
		tree1 = most_recent->left;
		rebal_direc = +1;
	}
	CTreeNode<T,T2> *most_recent_child = tree1;
	while (tree1!= tree2)
	{
		if (*(tree2->data)-*(tree1->data) > 0)
		{
			tree1-> balance = -1;// hight of right is increased by 1
			tree1 = tree1->right;
		}
		else
		{
			tree1->balance = +1;				// hight of left is increased by 1
			tree1 = tree1->left;
		}
	}
	// need to check if the balance of
	// the tree is alright
	int unbal_flag = 1;
	if (most_recent-> balance == 0)
	{
		// tree is not unbalanced
		most_recent->balance = rebal_direc;
		unbal_flag = 0;
	}
	if ( (most_recent->balance + rebal_direc) == 0 )
	{
		// tree is not unbalanced
		most_recent->balance = 0;
		unbal_flag = 0;
	}
	if (unbal_flag == 1)
	{
		// Tree is unbalanced. determine
		// rotation direction, and rotate.
		if (rebal_direc == +1)
		{
			// left subtree is imbalanced
			// Rotate left
			if (most_recent_child->balance == +1)
			{
				most_recent->left = most_recent_child->right;
				most_recent_child->right = most_recent;
				most_recent->balance = 0;
				most_recent_child->balance = 0;
			}
			else
			{
				new_Root = most_recent_child->right;
				most_recent_child->right = new_Root->left;
				most_recent->left = new_Root->right;
				new_Root->left = most_recent_child;
				new_Root->right = most_recent;
				switch (new_Root->balance)
				{
				case +1:
					most_recent->balance = -1;
					most_recent_child->balance = 0;
					break;
				case -1:
					most_recent_child->balance = 1;
					most_recent->balance = 0;
					break;
				case 0:
					most_recent_child->balance = 0;
					most_recent->balance = 0;
					break;
				}// end of the switch statement
				new_Root->balance = 0;
				most_recent_child = new_Root;
			}
		}
		else
		{
			// right substree is unbalanced
			if (most_recent_child->balance == -1)
			{
				most_recent->right = most_recent_child->left;
				most_recent_child->left = most_recent;
				most_recent->balance = 0;
				most_recent_child->balance = 0;
			}
			else
			{
				new_Root = most_recent_child->left;
				most_recent_child->left = new_Root->right;
				most_recent->right = new_Root->left;
				new_Root->right = most_recent_child;
				new_Root->left = most_recent;
				switch (new_Root->balance)
				{
				case -1:				// Should be -1
					most_recent->balance = 1;
					most_recent_child->balance = 0;
					break;
				case +1:				// Should be +1
					most_recent_child->balance = -1;
					most_recent->balance = 0;
					break;
				case 0:
					most_recent_child->balance = 0;
					most_recent->balance = 0;
					break;
				}
				new_Root->balance = 0;
				most_recent_child = new_Root;
			}// end of the else
		}  // end of the if rebal_direc = -1

		if (most_recent_parent == NULL)
			Root = most_recent_child;
		else if (most_recent == most_recent_parent->left)
			most_recent_parent->left = most_recent_child;
		else if (most_recent == most_recent_parent->right)
			most_recent_parent->right = most_recent_child;
	} // end of if unbalanced
	return tree2;
}

template<class T, class T2>
void CTree<T,T2>::LeftMidRight(void (*func)(T *),CTreeNode<T,T2> *tree)
{
	if (tree==NULL)
		tree=Root;
	if (tree->left!=NULL)
		LeftMidRight(func,tree->left);

	(*func)(tree->data);

	if (tree->right!=NULL)
		LeftMidRight(func,tree->right);
}

template<class T, class T2> void CTree<T,T2>::MidLeftRight(void (*func)(T *),CTreeNode<T,T2> *tree)
{
	if (tree==NULL)
		tree=Root;
	(*func)(tree->data);

	if (tree->left!=NULL)
		MidLeftRight(func,tree->left);

	if (tree->right!=NULL)
		MidLeftRight(func,tree->right);
}

template<class T, class T2> void CTree<T,T2>::RightMidLeft(void (*func)(T *),CTreeNode<T,T2> *tree)
{
	if (tree==NULL)
		tree=Root;
	if (tree->right!=NULL)
		RightMidLeft(func,tree->right);

	(*func)(tree->data);

	if (tree->left!=NULL)
		RightMidLeft(func,tree->left);
}

template<class T, class T2> void CTree<T,T2>::Clear(CTreeNode<T,T2> *tree)
{
	if (tree==NULL)
		tree=Root;
	if (tree->left)
	{
		Clear(tree->left);
		delete tree->left;
		tree->left=NULL;
	}
	if (tree->right)
	{
		Clear(tree->right);
		delete tree->left;
		tree->right=NULL;
	}
}

template<class T, class T2>
T *CTree<T,T2>::FindFirst(T2 &str,SearchType tp,CTreeNode<T,T2> *tree1)
{
	if (tree1==NULL)
		tree1=Root;
	CTreeNode<T,T2> *left=tree1,*right=tree1;
	while(tree1)
	{
		int a=*(tree1->data)-str;
		if (a==0)		//if match
		{
			Current=tree1;
			return tree1->data;
		}
		else	if (a>0)		// if not match and the str is smaller than the node
		{
			left=tree1;
			tree1=tree1->left;	// turn to left branch
		}
		else
		{
			right=tree1;
			tree1=tree1->right;
		}
	}
	Current=NULL;
	switch(tp)
	{
	case Equal:
		return NULL;	// no the equal one
	case Left:
		Current=left;
		return left->data;		// user can select return  the bigger one (the smallest that bigger than the target) >=
	case Right:
		Current=right;
		return right->data;		// or the smaller one(the biggest that smaller than the target) <=
	}
	return NULL;
}

template<class T,class T2>
T *CTree<T,T2>::FindNext(T2 &str,SearchType tp)
{
	if (Current)
		return FindFirst(str,Current->left,tp);
	else
		return NULL;
}

template<class T, class T2>
void SearchAndAdd(CTreeNode<T,T2> *t1, CTree<T,T2>  &t2, CTree<T,T2> &NewTree)
{
	if (t1->left)
		SearchAndAdd(t1->left,t2,NewTree);
	if (t2.FindFirst(*(t1->data)))
		NewTree.Add(t1->data);
	if (t1->right)
		SearchAndAdd(t1->right,t2,NewTree);
}

template<class T,class T2> CTree<T,T2> operator&(CTree<T,T2> &tree1, CTree<T,T2> &tree2)		// get the same part and build a tree, compare by data 
	{
		CTree<T,T2> newtree(/*own the data=*/false,/*kill_dup=*/false,/*showmsg=*/false);
		SearchAndAdd(tree1.Root,tree2,newtree);
		return newtree;
	}

template<class T, class T2> 
void Copy(CTreeNode<T,T2> *t1, CTree<T,T2> &NewTree)
{
	if (t1==NULL) return;
	if (t1->left)
		Copy(t1->left,NewTree);
	NewTree.Add(t1->data);
	if (t1->right)
		Copy(t1->right,NewTree);
}
template<class T, class T2>
CTree<T,T2> &CTree<T,T2>::operator=(CTree<T,T2> &tree2)
	{
		Clear();
		delete Root;
		Root=NULL;
		Current=NULL;
		DelDuplicate=tree2.DelDuplicate;
		Own=false;
		count=tree2.count;
		Copy(tree2.Root,*this);
		return *this;
	}
template <class T,class T2> 
CTree<T,T2>::CTree<T,T2>(CTree &tree2)					// copy constructor , copy pointer only
	{	
		count=tree2.count;
		Root=NULL;
		Current=NULL;
		DelDuplicate=tree2.DelDuplicate;
		Own=false;
		Copy(tree2.Root,*this);
	}

#endif