pex13_10.cpp

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

#include <iostream.h>
#pragma hdrstop

#include "bstree.h"
#include "treeprnt.h"
#include "iterator.h"
#include "treenode.h"
#include "queue.h"

// traverse a binary tree in level order
template <class T>
class LevelorderIterator: public Iterator<T>
{
	private:
		// queue of node addresses
		Queue<TreeNode<T> *> Q;
		// root of the tree and a pointer to the current
		// node in the traversal
		TreeNode<T> *root, *current;
		
	public:
		// constructor
		LevelorderIterator(TreeNode<T> *t);

		// implementation of methods declared in the abstract
		// base class Iterator
		virtual void Next(void);
		virtual void Reset(void);
		virtual T& Data(void);
};

// constructor. initialize base class, set root to t
// and call Reset
template <class T>
LevelorderIterator<T>::LevelorderIterator(TreeNode<T> *t):
      Iterator<T>(), root(t)
{
	Reset();
}

// move to the next node in level order
template <class T>
void LevelorderIterator<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);
	}
	
	// if the queue is not empty, we have more nodes to visit
	if(!Q.QEmpty())
	{
		// delete front node from queue. it is the current node
		current = Q.QDelete();
            
		// if a left child exists, insert it in the queue
		if(current->Left() != NULL)
			Q.QInsert(current->Left());
		// if a right child exists, insert next to its sibling
		if(current->Right() != NULL)
			Q.QInsert(current->Right());
	}
	else
		// Q is empty, and the traversal is complete
		iterationComplete = 1;
}

// reset the traversal to the root node
template <class T>
void LevelorderIterator<T>::Reset(void)
{
	// clear the queue of node addresses
	Q.QClear();
   
	// there is a traversal only if root is not NULL
	if (root != NULL)
	{
		// start at the root node
		current = root;
		// if root has a left child, insert it in the queue
		if(current->Left() != NULL)
			Q.QInsert(current->Left());
		// if root has a right child, insert next to its sibling
		if(current->Right() != NULL)
			Q.QInsert(current->Right());
		// iteration is not complete yet
		iterationComplete = 0;
	}
	else
		iterationComplete = 1;
}

// return a reference to the data in the current node of the tree
template <class T>
T& LevelorderIterator<T>::Data(void)
{
   // error if tree empty or we have completed traversal
   if (root == NULL || iterationComplete)
   {
      cerr << "Data: invalid reference!" << endl;
      exit(1);
   }
   return current->data;
}

void main(void)
{
	// create a binary search tree whose data values come
	// from array data
	BinSTree<int> T;
	int data[] = {100,55,135,145,25,106,88,5,26,33,45,103,142,33},i;
	
	// insert the 14 numbers into the binary search tree
	for (i=0;i < 14;i++)
		T.Insert(data[i]);
		
	// print the tree vertically
	PrintVTree(T.GetRoot(),2,30);
	cout << endl << endl;
	
	// declare a level order iterator for the tree
	LevelorderIterator<int> levelorderIter(T.GetRoot());
	
	// traverse the tree in level order and print the data values
	cout << "Level order traversal:" << endl;
	for(levelorderIter.Reset();!levelorderIter.EndOfList();levelorderIter.Next())
		cout << levelorderIter.Data() << "  ";
	cout << endl;
}

/*
<Run>

             100

      55            135

   25    88      106    145

  5  26        103    142

       33

         45

       33

Level order traversal:
100  55  135  25  88  106  145  5  26  103  142  33  45  33
*/