pex13_12.cpp

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

#include <iostream.h>
#pragma hdrstop

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

// traverse a binary tree in postorder
template <class T>
class PostorderIterator: public Iterator<T>
{
	private:
		// maintains stack of node addresses
		Stack<TreeNode<T> *> S;
		// root of the tree and address of current node
		TreeNode<T> *root, *current;
		// indicates whether moving down the tree (state = 0)
		// or up the tree (state = 1)
		int state;
	public:
		// constructor
		PostorderIterator(TreeNode<T> *t);
		
		// implementation of the pure virtual functions declared
		// in the abstract base class
		virtual void Next(void);
		virtual void Reset(void);
		virtual T& Data(void);
};


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

// move the the next node in postorder
template <class T>
void PostorderIterator<T>::Next(void)
{	
	TreeNode<T> *child;
	
	// error if we have already visited all the nodes
	if (iterationComplete)
	{
		cerr << "Next: iterator has passed the end of list!"
			 << endl;
		exit(1);
	}
	
	// loop until we find the next node or determine that
	// the traversal is complete
	for(;;)
	{
		//  are moving down or up the tree?
		if (state == 0)
		{
			// we are moving down. if current is not NULL
			// stack it and move left. if current is NULL,
			// we want to move up
			if (current != NULL)
			{
				S.Push(current);
				current = current->Left();
			}
			else
				state = 1;
		}
		else
		{
			// moving up the tree to the parent of the current node.
			// if the stack is empty, the traversal is complete
			if (S.StackEmpty())
			{
				iterationComplete = 1;
				break;
			}

			// child is the current node. assign current the node
			// address on the top of the stack
			child = current;
			current = S.Peek();

			// if the child address is the address stored in the left
			// pointer field of current and the current node as a right
			// subtree, we must move right and then move down the tree
			// to the left
			if (child == current->Left() && current->Right() != NULL)
			{
				current = current->Right();
				state = 0;
			}
			// we have visited both the left and right subtrees of current.
			// visit current
			else
			{
				S.Pop();
				break;
			}
		}
	}
}

// reset the iteration
template <class T>
void PostorderIterator<T>::Reset(void)
{
	// clear the stack of node addresses
	S.ClearStack();
	
	// state is initially down and the current node is root
	state = 0;
	current = root;

	// drive down the tree to the first node in postorder
	Next();
}

// return a reference to the data value 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);
	}

	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 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
*/