wex13_19.cpp

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

#include <iostream.h>
#pragma hdrstop

#include "treenode.h"
#include "treelib.h"
#include "stack.h"
#include "treescan.h"

void outputNode(char& c)
{
	cout << c << " ";
}

// perform an iterative preorder traversal of binary tree t
template <class T>
void PreOrder_I(TreeNode<T> *t, void visit(T& c))
{	
	// stack of node addresses
	Stack<TreeNode<T> *> S;
	
	// continue the scan if the current node pointer
	// is not NULL
	// or the stack S is not empty
	while(t != NULL || !S.StackEmpty())
		if(t != NULL)
		{
			// current node pointer is not NULL. visit t
			visit(t->data);
			// save right subree address on the stack so we can
			// descend it after we process the left subtree
			S.Push(t->Right());
			// move to the left branch of the node
			t = t->Left();
		}
		else
			// move up the tree to a saved right subtree
			t = S.Pop();
}

void main(void)
{
	TreeNode<char> *root;
	
	// create Tree_2
	MakeCharTree(root,2);
	
	PreOrder_I(root,outputNode);
	cout << endl;
}

/*
<Run>

A B D G C E H I F

*/