prethreaditerator.h

数据结构c++-书的一些源代码

#include "LinStack.h"								//包含模板的链式堆栈
#include "ThreadIterator.h"

template <class T> 
class PreThreadIterator: public ThreadIterator<T>			//共有方式继承
{
	protected:
		LinStack<BiTrThNode<T> *> S;		//存放二叉树结点指针的堆栈
		BiTrThNode<T> *GoFarLeft(BiTrThNode<T> *t);		//寻找最左孩子指针
	public:
		PreThreadIterator(BiTrThNode<T>* tree):			//构造函数
		  ThreadIterator<T>(tree){}

		  virtual void Prior(void){};					//纯虚函数
		virtual void Next(void);
		virtual void Reset(void);
};

template <class T>
BiTrThNode<T> *PreThreadIterator<T>::GoFarLeft(BiTrThNode<T> *t)
//寻找最左孩子的指针由函数返回
{
	if(t == NULL) return NULL;
	while(t->Left() != NULL)		//寻找最左孩子的指针
	{
		S.Push(t);					//逐层入栈
		t = t->Left();				//t等于左孩子指针
	}
	return t;						//返回不为空的最左孩子的指针
}

template <class T>
void PreThreadIterator<T>::Reset(void)
//
{
	S.ClearStack();					//堆栈清空
	iteComplete = (root == NULL);	//赋标记值
	if(root == NULL) return;
	current = GoFarLeft(root);		//当前结点指针指向中序遍历的第一个结点
}

template <class T>
void PreThreadIterator<T>::Next(void)
//使当前结点指针指向当前结点的中序遍历下的下一个结点。到尾部时标记置为1
{
	if(iteComplete == 1)
	{
		cerr << "已到二叉树尾!" << endl;
		exit(1);
	}
	
//寻找当前结点的中序遍历下的下一个结点由当前结点指针指示
	if(current->Right() != NULL)
		current = GoFarLeft(current->Right());
	else if(!S.StackEmpty())
		current = S.Pop();

	//到达尾部时标记置为1
	else
		iteComplete = 1;
}