bitrpreiterator.h

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

#include "LinStack.h"
#include "BiTreeIterator.h"

template <class T> class BiTrPreIterator: public BiTreeIterator<T>
{
	protected:
		LinStack<BiTreeNode<T> *> S;		//存放二叉树结点指针的堆栈
	public:
		BiTrPreIterator(BiTreeNode<T>* tree):
		  BiTreeIterator<T>(tree){}

		virtual void Next(void);
		virtual void Reset(void);
};

template <class T>
void BiTrPreIterator<T>::Reset(void)
{
	S.ClearStack();
	iteComplete = (root == NULL);
	if(root == NULL) return;
	current = root;							//根结点指针为当前结点指针
	if(root->Right() != NULL) S.Push(root->Right());	//右子树入栈
	if(root->Left() != NULL) S.Push(root->Left());		//左子树入栈
}

template <class T>
void BiTrPreIterator<T>::Next(void)
{
	if(iteComplete == 1)
	{
		cerr << "已到二叉树尾!" << endl;
		exit(1);
	}
	if(!S.StackEmpty())
	{
		current = S.Pop();							//退栈取得当前结点指针
		if(current->Right() != NULL) S.Push(current->Right());//右子树入栈
		if(current->Left() != NULL) S.Push(current->Left());//左子树入栈
	}
	else
		iteComplete = 1;						//堆栈空时置结束标记为1
}