二叉树的遍历

自娱自乐型。

1 Tree.h 定义Tree相关的，使用了STL

#ifndef __TREE_H__
#define __TREE_H__

#include <iostream>
#include <stack>
#include <queue>
using std::iostream;
using std::cout;
using std::endl;
using std::stack;
using std::queue;

struct BinaryTreeNode;


typedef void (*BTREENODE_VISIT)(BinaryTreeNode* pBTreeNode);

struct BinaryTreeNode
{
	int data;
	int flags; //0:not in stack, 1: in stack
	int height;
	BinaryTreeNode* pLeftChildren;
	BinaryTreeNode* pRightChildren;
	BinaryTreeNode()
	{
		pLeftChildren = pRightChildren = NULL;
		flags = 0;
		height = 0;
	}
	BinaryTreeNode(int data)
	{
		pLeftChildren = pRightChildren = NULL;
		this->data = data;
		flags = 0;
		height  = 0;
	}
	void createTrees(BinaryTreeNode *pLeft,BinaryTreeNode* pRight)
	{
		pLeftChildren = pLeft;
		pRightChildren = pRight;
	}
	static void preOrderVisitRecurs(BinaryTreeNode* pBTree,BTREENODE_VISIT pBTNodeVisitFunc)
	{
		if(pBTree)
		{
			if(pBTNodeVisitFunc)
				pBTNodeVisitFunc(pBTree);
			if(pBTree->pLeftChildren)
				preOrderVisitRecurs(pBTree->pLeftChildren,pBTNodeVisitFunc);
			if(pBTree->pRightChildren)
				preOrderVisitRecurs(pBTree->pRightChildren,pBTNodeVisitFunc);
		}
		return;
	}
	static void preOrderVisit(BinaryTreeNode* pBTree, BTREENODE_VISIT pBTNodeVisitFunc)
	{
		if(pBTree == NULL)
			return;
		typedef stack<BinaryTreeNode*> CBTNodeStack;
		CBTNodeStack  btnStack;
		btnStack.push(pBTree);
		while(btnStack.size() > 0)
		{
			BinaryTreeNode* pCurrent = btnStack.top();
			if(pCurrent)
				pBTNodeVisitFunc(pCurrent);
			btnStack.pop();
			if(pCurrent->pRightChildren)
				btnStack.push(pCurrent->pRightChildren);
			if(pCurrent->pLeftChildren)
				btnStack.push(pCurrent->pLeftChildren);
		}

	};
	static void inOrderVisitRecurs(BinaryTreeNode* pBTree,BTREENODE_VISIT pBTNodeVisitFunc)
	{
		if(pBTree)
		{
			if(pBTree->pLeftChildren)
				inOrderVisitRecurs(pBTree->pLeftChildren,pBTNodeVisitFunc);
			if(pBTNodeVisitFunc)
				pBTNodeVisitFunc(pBTree);
			if(pBTree->pRightChildren)
				inOrderVisitRecurs(pBTree->pRightChildren,pBTNodeVisitFunc);
		}
		return;
	}
	static void inOrderVisit(BinaryTreeNode* pBTree,BTREENODE_VISIT pBTNodeVisitFunc)
	{
		if(pBTree == NULL)
			return;
		
		typedef stack<BinaryTreeNode*> CBTNodeStack;
		CBTNodeStack  btnStack;
		btnStack.push(pBTree);
		pBTree->flags = 1;
		while(btnStack.size() > 0)
		{
			pBTree = btnStack.top();
			while(pBTree->pLeftChildren != NULL && pBTree->pLeftChildren->flags == 0)
			{
				btnStack.push(pBTree->pLeftChildren);
				pBTree->pLeftChildren->flags = 1;
				pBTree = btnStack.top();
			}

			pBTree = btnStack.top();
			if(pBTNodeVisitFunc)
				pBTNodeVisitFunc(pBTree); //visit the left leaf or leftest root
			btnStack.pop();
			if(pBTree->pRightChildren && pBTree->pRightChildren->flags == 0)
			{
				btnStack.push(pBTree->pRightChildren);
				pBTree->pRightChildren->flags = 1;
				continue;
			}
		}
		return;
	}

	static void postOrderVisitRecurs(BinaryTreeNode* pBTree,BTREENODE_VISIT pBTNodeVisitFunc)
	{
		if(pBTree)
		{
			if(pBTree->pLeftChildren)
				postOrderVisitRecurs(pBTree->pLeftChildren,pBTNodeVisitFunc);
			if(pBTree->pRightChildren)
				postOrderVisitRecurs(pBTree->pRightChildren,pBTNodeVisitFunc);
			if(pBTNodeVisitFunc)
				pBTNodeVisitFunc(pBTree);
		}
		return;
	}
	static void postOrderVisit(BinaryTreeNode* pBTree,BTREENODE_VISIT pBTNodeVisitFunc)
	{
		if(pBTree == NULL)
			return;
		typedef stack<BinaryTreeNode*> CBTNodeStack;
		CBTNodeStack  btnStack;
		btnStack.push(pBTree);
		pBTree->flags = 1;
		while(btnStack.size() > 0)
		{
			pBTree = btnStack.top();
			while(pBTree->pLeftChildren != NULL && pBTree->pLeftChildren->flags == 0)
			{
				btnStack.push(pBTree->pLeftChildren);
				pBTree->pLeftChildren->flags = 1;
				pBTree = btnStack.top();
			}

			pBTree = btnStack.top();
			if(pBTree->pRightChildren && pBTree->pRightChildren->flags == 0)
			{
				btnStack.push(pBTree->pRightChildren);
				pBTree->pRightChildren->flags = 1;
				continue;
			}
			if(pBTNodeVisitFunc)
				pBTNodeVisitFunc(pBTree);
			
			btnStack.pop();
		}
		return;
	};
	static void levelVisit(BinaryTreeNode* pBTree,BTREENODE_VISIT pBTNodeVisitFunc)
	{
		typedef queue<BinaryTreeNode*> CBTNodeQueue;
		CBTNodeQueue btQueue;
		btQueue.push(pBTree);
		while(btQueue.size())
		{
			BinaryTreeNode* pCurrent = btQueue.front();
			if(pCurrent->pLeftChildren)
				btQueue.push(pCurrent->pLeftChildren);
			if(pCurrent->pRightChildren)
				btQueue.push(pCurrent->pRightChildren);
			if(pBTNodeVisitFunc)
				pBTNodeVisitFunc(pCurrent);
			btQueue.pop();
		}
	}

};





#endif

2 测试：

// DataStructTest.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

#include "Tree.h"


void PRINT_BNVALUE(BinaryTreeNode* pBTreeNode)
{
	cout<<"TreeVale " << pBTreeNode->data << endl;
}
void RESET_FLAGS(BinaryTreeNode* pBTreeNode)
{
	pBTreeNode->flags = 0;
}
int _tmain(int argc, _TCHAR* argv[])
{
	/*
	    构造目标树
		 1
		/  \
	   2    3
      / \   /
     4   5 6
	    /   \
	   7     8
	
	*/
	
	BinaryTreeNode testBNTree8(8);
	BinaryTreeNode testBNTree7(7);
	BinaryTreeNode testBNTree6(6);
	BinaryTreeNode testBNTree5(5);
	BinaryTreeNode testBNTree4(4);
	BinaryTreeNode testBNTree3(3);
	BinaryTreeNode testBNTree2(2);
	BinaryTreeNode testBNTree1(1);


	testBNTree1.createTrees(&testBNTree2,&testBNTree3);
	testBNTree2.createTrees(&testBNTree4,&testBNTree5);
	testBNTree5.createTrees(&testBNTree7,NULL);

	testBNTree3.createTrees(&testBNTree6,NULL);
	testBNTree6.createTrees(NULL,&testBNTree8);

	cout<<"travse pre order recurs"<<endl;
	BinaryTreeNode::preOrderVisitRecurs(&testBNTree1,PRINT_BNVALUE);
	cout<<"travse pre order NOT recurs"<<endl;
	BinaryTreeNode::preOrderVisit(&testBNTree1,PRINT_BNVALUE);

	cout<<"travse in order recurs"<<endl;
	BinaryTreeNode::inOrderVisitRecurs(&testBNTree1,PRINT_BNVALUE);
	cout<<"travse in order NOT recurs"<<endl;
	BinaryTreeNode::inOrderVisit(&testBNTree1,PRINT_BNVALUE);
	//采用层级遍历清空flags标志
	BinaryTreeNode::levelVisit(&testBNTree1,RESET_FLAGS);

	cout<<"travse post order recurs"<<endl;
	BinaryTreeNode::postOrderVisitRecurs(&testBNTree1,PRINT_BNVALUE);
	cout<<"travse post order NOT recurs"<<endl;
	BinaryTreeNode::postOrderVisit(&testBNTree1,PRINT_BNVALUE);

	cout<<"travse level"<<endl;
	BinaryTreeNode::levelVisit(&testBNTree1,PRINT_BNVALUE);


	return 0;
}