avltree.h

这是一个非常经典的二叉平衡树

//avltree.h

#ifndef _cavltree_
#define _cavltree_

#include "avlnode.h"
#include"avlite~1.h"


template<class T>
class CAVLTree
{
	private:
		friend class CAVLIterator<T,IN_ORDER>;
		friend class CAVLIterator<T,PRE_ORDER>;
		friend class CAVLIterator<T,POST_ORDER>;
		CAVLNode<T> *m_root;
	public:
		
		CAVLTree();
		int Del(T content);
		int Insert(T content);
		CAVLNode<T>* Search(T content);
};

template<class T>
CAVLTree<T>::CAVLTree()
{
	m_root=NULL;
}

template<class T>
int CAVLTree<T>::Insert(T content)
{
	CAVLNode<T>* help,*n;
	if(m_root==NULL)
		m_root=new CAVLNode<T>(content);
	else
	{
		if(!(n=new CAVLNode<T>(content)))
			return 0;
		help=m_root->Find(content);
		if(help->m_content==content)
			return 0;
		if(content<help->m_content)
			help->m_left=n;
		else
			help->m_right=n;
		n->m_prev=help;
		m_root=n->AVL();
	}
	return 1;
}

template<class T>
int CAVLTree<T>::Del(T content)
{
	CAVLNode<T>* help=m_root->Find(content);
	if(help->m_content!=content||!m_root)
		return 0;
	help=help->Del();
	if(help)
		m_root=help->AVL();
}

template<class T>
CAVLNode<T>* CAVLTree<T>::Search(T content)
{
	CAVLNode<T> *help=m_root?m_root->Find(content):NULL;
	if(help)
		return help->m_content==content?help:NULL;
	return NULL;
}


#endif