inthreaditerator.h

包含各种测试,查找和算法等代码,如冒泡算法,树的遍历,链表,队列,堆栈等

#include "ThreadIterator.h"

template <class T> 
class InThreadIterator: public ThreadIterator<T>			//共有方式继承
{
	private:
		void InThread(BiTrThNode<T>* &current, BiTrThNode<T>* &pre);
	public:
		//构造函数
		InThreadIterator(BiTrThNode<T>* tree): ThreadIterator<T>(tree){}

		void CreatInThread();							//中序线索化二叉树

		virtual void First(void);						
		virtual void Last(void);						
		virtual void Prior(void);					
		virtual void Next(void);
};

template <class T>
void InThreadIterator<T>::CreatInThread()
//中序线索化二叉树tree
{
	BiTrThNode<T> *t = root;					//保存原二叉树根结点指针
	root = new BiTrThNode<T>;					//建立头结点
	root->leftThread = 0;
	root->rightThread = 1;
	if(t == NULL)								//当为空树时
	{
		root->leftChild = root;
		root->rightChild = root;
	}
	else										//当为非空树时
	{
		current  = root->leftChild = t;			//第一个结点的左指针
		root->leftThread = 0;					//第一个结点的左线索
		BiTrThNode<T>* pre = root;				//定义临时指针pre
		InThread(current, pre);					//线索化二叉树
		pre->rightChild = root;					//最后一个结点的右指针
		pre->rightThread = 1;					//最后一个结点的右线索
		root->rightChild = pre;					//第一个结点的右指针		
		root->rightThread = 1;					//第一个结点的右线索
	}
}

template <class T>
void InThreadIterator<T>::InThread(BiTrThNode<T>* &current, BiTrThNode<T>* &pre)
//中序线索化二叉树。current为当前结点指针，pre为当前结点的中序前一结点指针
{
	if(current != NULL)
	{
		InThread(current->leftChild, pre);		//中序线索化左子树二叉树
		if(current->leftChild == NULL)			//当前结点左指针为空指针时
		{
			current->leftChild = pre;			//建立左线索指针
			current->leftThread = 1;			//建立左线索标记
		}
		if(pre->rightChild == NULL)				//前序结点右指针为空指针时
		{
			pre->rightChild = current;			//建立右线索指针
			pre->rightThread = 1;				//建立右线索标记
		}
		pre = current;							//前序结点指针等于当前结点指针
		InThread(current->rightChild, pre);		//中序线索化右子树二叉树
	}
}

template <class T>
void InThreadIterator<T>::First(void)
//使当前结点指针current指向第一个结点
{
	current = root;
	while(current->leftThread == 0) current = current->leftChild;

	if(current == root) nextComplete = 1;
	else nextComplete = 0;
}

template <class T>
void InThreadIterator<T>::Next(void)
//使当前结点指针指向当前结点的下一个结点。到尾部时正序结束标记置为1
{
	if(nextComplete == 1)
	{
		cerr << "已到二叉树尾!" << endl;
		exit(1);
	}
	
	BiTrThNode<T>* p = current->rightChild;
	if(current->rightThread == 0)
		while(p->leftThread == 0) p = p->leftChild;
	current = p;

	if(current == root) nextComplete = 1;
}

template <class T>
void InThreadIterator<T>::Last(void)
//使当前结点指针current指向最后一个结点

{
	current = root->rightChild;
	if(current == root) priorComplete = 1;
	else priorComplete = 0;
}

template <class T>
void InThreadIterator<T>::Prior(void)
//使当前结点指针指向当前结点的前一个结点。到头部时反序结束标记置为1
{
	if(priorComplete == 1)
	{
		cerr << "已到二叉树头!" << endl;
		exit(1);
	}
	
	BiTrThNode<T>* p = current->leftChild;
	if(current->leftThread == 0)
		while(p->rightThread == 0) p = p->rightChild;
	current = p;

	if(current == root) priorComplete = 1;
}