pex13_9.cpp

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

#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>
#pragma hdrstop

#include "treenode.h"
#include "stack.h"
#include "random.h"
#include "bstree.h"

// abstract base class for iterators. Next declared
// using the postincrement operator
template <class T>
class Iterator
{
   protected:
      // indicates whether iterator has reached end of list.
      // must be maintained by the derived class
      int iterationComplete;
   
   public:
      // constructor
      Iterator(void);
      
      // required iterator methods
      virtual void operator++ (int) = 0;
      virtual void Reset(void) = 0;
      
      // data retrieval/modification method
      virtual T& Data(void) = 0;
      
      // test for end of list
      virtual int EndOfList(void) const;
};

// constructor. sets iterationComplete to 0 (False)
template <class T>
Iterator<T>::Iterator(void): iterationComplete(0)
{}

// return the value of iterationComplete.
template <class T>
int Iterator<T>::EndOfList(void) const
{
   return iterationComplete;
}

// Inorder iterator for binary tree; uses Iterator base class
template <class T>
class InorderIterator: public Iterator<T>
{
   private:
      // we maintain a stack of TreeNode addresses
      Stack< TreeNode<T> * > S;
      // tree root and current node
      TreeNode<T> *root, *current;
      
      // traverse a left path. used by Next
      TreeNode<T> *GoFarLeft(TreeNode<T> *t);
   public:
	  // constructor
      InorderIterator(TreeNode<T> *tree);

	  // implementation of basic traversal operations
      virtual void operator++ (int);
      virtual void Reset(void);
      virtual T& Data(void);
      
	  // assign new tree list to iterator
      void SetTree(TreeNode<T> *tree);
};

// return address of last node on the left branch from t,
// stacking node addresses as we go
template <class T>
TreeNode<T> *InorderIterator<T>::GoFarLeft(TreeNode<T> *t)
{
   // if t is NULL, return NULL
   if (t == NULL)
      return NULL;
      
   // go as far left in the tree t as possible, stacking each
   // node address on S until a node is found with a NULL
   // left pointer. return a pointer to that node
   while (t->Left() != NULL)
   {
      S.Push(t);
      t = t->Left();
   }
   return t;
}

// initialize iterationComplete. base class sets it to 0, but
// the tree may be empty. first node in traversal is farthest
// node left.
template <class T>
InorderIterator<T>::InorderIterator(TreeNode<T> *tree):
      Iterator<T>(), root(tree)
{
   iterationComplete = (root == NULL);
   current = GoFarLeft(root);
}

// move the iterator to the next node of the tree inorder
template <class T>
void InorderIterator<T>::operator++ (int)
{  
   // error if we have already visited all the nodes
   if (iterationComplete)
   {
      cerr << "Next: iterator has passed the end of list!"
          << endl;
      exit(1);
   }
   
   // we have visited node current. if we have a right
   // subtree, move right and go far left, stacking
   // up nodes on the left subtree
   if (current->Right() != NULL)
      current = GoFarLeft(current->Right());
      
   // no right subtree, but there are other nodes we have
   // stacked we must process. pop stack into current
   else if (!S.StackEmpty())     // move up the tree
      current = S.Pop();

   // no right branch of current node and no stacked nodes.
   // the traversal is complete
   else
      iterationComplete = 1;
}

// reset the traversal to the first tree node
template <class T>
void InorderIterator<T>::Reset(void)
{
   // clear out the stack of node addresses
   S.ClearStack();
   
   // reassign iterationComplete and current the address of
   // the first node in the inorder scan
   iterationComplete = (root == NULL);
   current = GoFarLeft(root); // go back to 1st node inorder
}

// return current data value
template <class T>
T& InorderIterator<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;
}

template <class T>
void InorderIterator<T>::SetTree(TreeNode<T> *tree)
{
   // clear out the stack of node addresses
   S.ClearStack();
   
   // assign new tree root. initialize iterationComplete.
   // assign current the address of first node in the scan
   root = tree;
   iterationComplete = (root == NULL);
   current = GoFarLeft(root); // go to 1st node inorder
}

void main(void)
{
	BinSTree<int> T;
	RandomNumber rnd;
	int A[25];
	
	// initialize A with 25 random integers in the
	// range 0..32767. print the list
	cout << "Original list:" << endl;
	for(int i=0;i < 25;i++)
	{
		if (i % 10 == 0)
			cout << endl;
		A[i] = rnd.Random(32768L);
		cout << setw(6) << A[i];
	}
	cout << endl << endl;
	
	// insert the 25 integers into the binary search tree
	for (i=0;i < 25;i++)
		T.Insert(A[i]);
		
	// declare an inorder iterator for the tree
	InorderIterator<int> inorderIter(T.GetRoot());
	
	// traverse the tree inorder and print the sorted list
	cout << "Sorted list:" << endl;
	inorderIter.Reset();
	i = 0;
	while(!inorderIter.EndOfList())
	{
		if (i++ % 10 == 0)
			cout << endl;
		cout << setw(6) << inorderIter.Data();
		inorderIter++;
	}
	cout << endl;
}

/*
<Run>

Original list:

 12006 14706 11739 10323 13600   470 16255 26990 23332 31157
  3638  3389 17905 18042 23499  7793 12823  9389 13608  7088
  8144 27609 10716 13161 13531

Sorted list:

   470  3389  3638  7088  7793  8144  9389 10323 10716 11739
 12006 12823 13161 13531 13600 13608 14706 16255 17905 18042
 23332 23499 26990 27609 31157
*/