avliterator.h

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

//avliterator.h

#ifndef _cavliterator_
#define _cavliterator_

#define IN_ORDER 1
#define PRE_ORDER 2
#define POST_ORDER 3

template<class T>class CAVLTree;
template<class T>class CAVLNode;

template<class T,int typ>
class CAVLIterator
{
	private:
		CAVLTree<T> &m_tree;
		CAVLNode<T> *m_pos;
		int NextInOrder();
		int NextPreOrder();
		int NextPostOrder();
	public:
		CAVLIterator(CAVLTree<T> &tree);
		void Start();
		int Next();
		T GetCurrent();
};

template<class T,int typ>
CAVLIterator<T,typ>::CAVLIterator(CAVLTree<T> &tree):m_tree(tree)
{
	m_pos=NULL;
}

template<class T,int typ>
void CAVLIterator<T,typ>::Start()
{
	m_pos=m_tree.m_root;
	if(m_pos)
		m_pos->SetSigns(0);
	switch(typ)
	{
	case PRE_ORDER:		if(m_pos) m_pos->m_sign=1; break;
	case POST_ORDER:
	case IN_ORDER:		if(m_pos)
						{
							while(m_pos->m_left) m_pos=m_pos->m_left;
							m_pos->m_sign=1;
						}
							
	}
}

template<class T,int typ>
int CAVLIterator<T,typ>::Next()
{
	switch(typ)
	{
	case IN_ORDER:		return NextInOrder();
	case PRE_ORDER:		return NextPreOrder();
	case POST_ORDER:	return NextPostOrder();
	}
	return 0;
}

template<class T,int typ>
int CAVLIterator<T,typ>::NextInOrder()
{
	if(m_pos)
		if(m_pos->m_left&&!m_pos->m_left->m_sign)
		{
			m_pos=m_pos->m_left;
			return NextInOrder();
		}
		else
			if(!m_pos->m_sign)
			{
				m_pos->m_sign=1;
				return 1;
			}
			else
				if(m_pos->m_right&&!m_pos->m_right->m_sign)
				{
					m_pos=m_pos->m_right;
					return NextInOrder();
				}
				else
				{
					if(!m_pos->m_prev)
						return 0;
					m_pos=m_pos->m_prev;
					return NextInOrder();
				}
	return 0;
}

template<class T,int typ>
int CAVLIterator<T,typ>::NextPreOrder()
{
	if(m_pos)
		if(!m_pos->m_sign)
		{
			m_pos->m_sign=1;
			return 1;
		}
		else
			if(m_pos->m_left&&!m_pos->m_left->m_sign)
			{
				m_pos=m_pos->m_left;
				return NextPreOrder();
			}
			else
				if(m_pos->m_right&&!m_pos->m_right->m_sign)
				{
					m_pos=m_pos->m_right;
					return NextPreOrder();
				}
				else
				{
					if(!m_pos->m_prev)
						return 0;
					m_pos=m_pos->m_prev;
					return NextPreOrder();
				}
	return 0;
}

template<class T,int typ>
int CAVLIterator<T,typ>::NextPostOrder()
{
	if(m_pos)
		if(m_pos->m_left&&!m_pos->m_left->m_sign)
		{
			m_pos=m_pos->m_left;
			return NextPostOrder();
		}
		else
			if(m_pos->m_right&&!m_pos->m_right->m_sign)
			{
				m_pos=m_pos->m_right;
				return NextPostOrder();
			}
			else
				if(!m_pos->m_sign)
				{
					m_pos->m_sign=1;
					return 1;
				}
				else
				{
					if(!m_pos->m_prev)
						return 0;
					m_pos=m_pos->m_prev;
					return NextPostOrder();
				}
	return 0;
}


template<class T,int typ>
T CAVLIterator<T,typ>::GetCurrent()
{
	if(m_pos)
		return m_pos->m_content;
	T help;
	return help;
}

#endif