pex13_11.cpp

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

#include <iostream.h>
#pragma hdrstop

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

// traverse a tree in postorder
template <class T>
class PostorderIterator: public Iterator<T>
{
	private:
		// stack of node addresses
		Stack<TreeNode<T> *> S;
		// root of the tree
		TreeNode<T> *root;
		// initialize the scan
		void InitScan(TreeNode<T> *t);
	public:
		// constructor
		PostorderIterator(TreeNode<T> *t);

		// implementation of methods defined in the abstract
		// base class as pure virtual functions
		virtual void Next(void);
		virtual void Reset(void);
		virtual T& Data(void);
};

// initialize for scan
template <class T>
void PostorderIterator<T>::InitScan(TreeNode<T> *t)
{
	// traverse the tree in NRL order and stack node addresses.
	// the nodes come off the stack in LRN order
	if (t != NULL)
	{
		S.Push(t);
		InitScan(t->Right());
		InitScan(t->Left());
	}
}

// constructor. call Reset
template <class T>
PostorderIterator<T>::PostorderIterator(TreeNode<T> *t): root(t)
{
	Reset();
}

// move to the next node in postorder
template <class T>
void PostorderIterator<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);
	}

	// pop the stack. the next node in postorder is on the
	// top of the stack
	S.Pop();

	// if the stack is empty, the scan is complete
	if (S.StackEmpty())
		iterationComplete = 1;
}

// reset the postorder scan
template <class T>
void PostorderIterator<T>::Reset(void)
{
	// clear the existing stack
	S.ClearStack();
	
	// assign iterationComplete to True if the tree is non-empty
	// and False if the tree is empty
	iterationComplete = (root == NULL);

	// if there are nodes to scan, initialize the stack
	if (!iterationComplete)
		InitScan(root);
}

// return the data in the current node
template <class T>
T& PostorderIterator<T>::Data(void)
{
	// error if tree empty or we have completed traversal
	if (root == NULL || iterationComplete)
	{
		cerr << "Data: invalid reference!" << endl;
		exit(1);
	}
   
	// the current data value in the postorder traversal
	// is in the node whose address is on the top of the tack
	return S.Peek()->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 postorder iterator for the tree
	PostorderIterator<int> postorderIter(T.GetRoot());
	
	// traverse the tree in postorder and print the data values
	cout << "Postorder traversal:" << endl;
	for(postorderIter.Reset();!postorderIter.EndOfList();postorderIter.Next())
		cout << postorderIter.Data() << "  ";
	cout << endl;
}

/*
<Run>

             100

      55            135

   25    88      106    145

  5  26        103    142

       33

         45

       33

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