pex13_8.cpp

数据结构C++代码,经典代码,受益多多,希望大家多多支持

#include <iostream.h>
#pragma hdrstop

#include "iterator.h"
#include "stack.h"

// preorder iterator for an array-based tree
template <class T>
class ArrPreorderIterator: public Iterator<T>
{
	private:
		// maintain a stack of right branch indices
		Stack<int> S;
		// pointer to the array being traversed
		T *A;
		// number of elements in the array we are traversing
		int arraySize;
		// current array index in the traversal
		int current;
	public:
		// constructor
		ArrPreorderIterator(T *Arr, int n);
		
		// implementation for pure virtual functions
		// declared in the base class Iterator
		virtual void Next(void);
		virtual void Reset(void);
		virtual T& Data(void);
};

// constructor. initialize Arr, arraySize and current.
// the first element we visit is Arr[0], so current
// is initialized to 0. iterationComplete is True
// if arraySize is 0
template <class T>
ArrPreorderIterator<T>::ArrPreorderIterator(T *Arr, int n):
	A(Arr), arraySize(n), current(0)
{
	// iteration is complete if list size is 0
	iterationComplete = (arraySize == 0);
}

// move to the next array element in preorder
template <class T>
void ArrPreorderIterator<T>::Next(void)
{
	// error if we have already visited all the nodes
	if (iterationComplete)
	{
		cerr << "Next: iterator has passed the end of list!"
			 << endl;
		exit(1);
	}
   
	// save a non-empty right branch on the stack
	if (2*current+2 < arraySize)
		S.Push(2*current+2);
		
	// if a left branch, take it
	if (2*current+1 < arraySize)
		current = 2*current+1;
	// otherwise, move to a saved right branch
	else if (!S.StackEmpty())
		current = S.Pop();
	// no left branch or saved right branch. done.
	else
		iterationComplete = 1;
}

// reset the traversal back to the root
template <class T>
void ArrPreorderIterator<T>::Reset(void)
{
   // clear the stack of array indices
   S.ClearStack();
   
   // reassign iterationComplete and current the index of
   // the first node in the preorder scan
   iterationComplete = (arraySize == 0);
   current = 0;
}

template <class T>
T& ArrPreorderIterator<T>::Data(void)
{
   // error if tree empty or we have completed traversal
   if (arraySize == 0 || iterationComplete)
   {
      cerr << "Data: invalid reference!" << endl;
      exit(1);
   }
   return A[current];
}

void main(void)
{
	// traverse A in preorder
	int A[] = {1,4,6,2,8,9,12,25,23,55,18,78,58,14,45};
	ArrPreorderIterator<int> arriter(A,15);
	
	// the level order traversal is just a listing
	// of the array elements A[0] ... A[14]
	cout << "Level order traversal: ";
	for(int i=0;i < 15;i++)
		cout << A[i] << " ";
	cout << endl << endl;
	
	// use the iterator to traverse and print A in preorder
	cout << "Preorder traversal:    ";
	for(arriter.Reset();!arriter.EndOfList();arriter.Next())
		cout << arriter.Data() << " ";
	cout << endl;
} 

/*
<Run>

Level order traversal: 1 4 6 2 8 9 12 25 23 55 18 78 58 14 45

Preorder traversal:    1 4 2 25 23 8 55 18 6 9 78 58 12 14 45
*/