bitriniterator.h

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

#include "LinStack.h"						//包含链式堆栈类

template <class T> 
class BiTrInIterator: public BiTreeIterator<T>	//二叉树中序遍历游标类
{
protected:
	LinStack<BiTreeNode<T> *> S;			//存放结点指针的堆栈

	BiTreeNode<T> *GoFarLeft(BiTreeNode<T>* &t);//寻找最左孩子结点
public:
	BiTrInIterator(BiTreeNode<T>* &tree):	//构造函数
	  BiTreeIterator<T>(tree){}				//调用基类的构造函数

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

template <class T>
BiTreeNode<T> *BiTrInIterator<T>::GoFarLeft(BiTreeNode<T>* &t)
//寻找最左孩子结点并返回该结点的指针
{
	if(t == NULL) return NULL;
	while(t->Left() != NULL)		//寻找最左孩子结点
	{
		S.Push(t);					//逐层入栈
		t = t->Left();				//t等于左孩子指针
	}
	return t;						//返回不为空的最左孩子结点的指针
}

template <class T>
void BiTrInIterator<T>::Reset(void)
//初始化设置
{
	if(root == NULL) iteComplete = 1;	
	else  iteComplete = 0;

	if(root == NULL) return;
	current = GoFarLeft(root);	//当前结点指针指向中序遍历的第一个结点
}

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

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