二叉树非递归和递归遍历（先序，中序，后序）

首先创建二叉树，然后对二叉树遍历进行了单元测试。只要将相应的注释取消，便可以成功运行。

/********************************************
二叉树遍历前序、中序、后序的递归和非递归实现
********************************************/
#include<stdio.h>
#include<stack>

using namespace std;

struct BinaryTreeNode
{
	int m_nValue;
	BinaryTreeNode* m_pLeft;
	BinaryTreeNode* m_pRight;
};
//创建二叉树节点
BinaryTreeNode* createBinaryTreeNode(int value)
{
	BinaryTreeNode* pNode = new BinaryTreeNode();
	pNode->m_nValue = value;
	pNode->m_pRight = NULL;
	pNode->m_pLeft = NULL;
	return pNode;
}
//连接二叉树节点
void connectBinaryTreeNode(BinaryTreeNode* pParent,BinaryTreeNode* pLeft,BinaryTreeNode* pRight)
{
	if(pParent != NULL){
	pParent->m_pLeft = pLeft;
	pParent->m_pRight = pRight;
	}
}
//销毁二叉树
void destoryBinaryTree(BinaryTreeNode* pRoot)
{
	if(pRoot != NULL)
	{
		BinaryTreeNode* pLeft = pRoot->m_pLeft;
		BinaryTreeNode* pRight = pRoot->m_pRight;
		delete pRoot;
		destoryBinaryTree(pLeft);
		destoryBinaryTree(pRight);
	}
}
/**********************************
//前序遍历，递归实现
void preOrder(BinaryTreeNode* pRoot)
{
	if(pRoot)
	{
		printf("%d\n",pRoot->m_nValue);
		preOrder(pRoot->m_pLeft);
		preOrder(pRoot->m_pRight);		
	}
}
***********************************/

/****************************************
//前序遍历，非递归实现
void preOrder(BinaryTreeNode* pRoot)
{
	if(pRoot)
	{
		stack<BinaryTreeNode*> btnStack;
		while(pRoot || !btnStack.empty())
		{
			if(pRoot)
			{
				printf("%d\t",pRoot->m_nValue);
				btnStack.push(pRoot);
				pRoot = pRoot->m_pLeft;
			}
			else
			{
				pRoot = btnStack.top();
				btnStack.pop();
				pRoot = pRoot->m_pRight;
			}
		}
	}
}
*********************************************/

/*******************************************
//中序遍历,递归实现
void midOrder(BinaryTreeNode* pRoot)
{
	if(pRoot)
	{
		midOrder(pRoot->m_pLeft);
		printf("%d\t",pRoot->m_nValue);
		midOrder(pRoot->m_pRight);
	}
}
*******************************************/

/*******************************************
//中序遍历,非递归实现
void midOrder(BinaryTreeNode* pRoot)
{
	if(pRoot)
	{
		stack<BinaryTreeNode*> btnStack;
		while(pRoot || !btnStack.empty())
		{
			if(pRoot)
			{
				btnStack.push(pRoot);
				pRoot = pRoot->m_pLeft;
			}
			else
			{
				pRoot = btnStack.top();
				printf("%d\t",pRoot->m_nValue);
				btnStack.pop();
				pRoot = pRoot->m_pRight;
			}
		}
	}
}
**********************************************

/******************************************
//后序遍历，递归实现
void postOrder(BinaryTreeNode* pRoot)
{
	if(pRoot)
	{
		postOrder(pRoot->m_pLeft);
		postOrder(pRoot->m_pRight);
		printf("%d\t",pRoot->m_nValue);
	}
}
******************************************/
//后序遍历，非递归实现
void postOrder(BinaryTreeNode* pRoot)
{
	if(pRoot)
	{
		stack<BinaryTreeNode*> btnStack;
		btnStack.push(pRoot);
		BinaryTreeNode* pPreNode = NULL;	//前一次访问的节点

		while(!btnStack.empty())
		{
			pRoot = btnStack.top();
			if((!pRoot->m_pLeft && !pRoot->m_pRight)	//叶子节点或
				|| (pPreNode && ((pPreNode==pRoot->m_pLeft)
					||(pPreNode==pRoot->m_pRight))))//左右子节点都已经访问过的节点
			{
				printf("%d\t",pRoot->m_nValue);
				pPreNode = pRoot;
				btnStack.pop();
			}
			else
			{
				if(pRoot->m_pRight)					//空节点不入栈
					btnStack.push(pRoot->m_pRight);	//将后访问的节点先入栈
				if(pRoot->m_pLeft)
					btnStack.push(pRoot->m_pLeft);
			}
		}
	}
}
//单元测试
//两边都有树枝
/*
     10
    /     6   14
  / \  /  4  8 12 16
*/
void test1()
{
	BinaryTreeNode* pNode1 = createBinaryTreeNode(10);
	BinaryTreeNode* pNode2 = createBinaryTreeNode(6);
	BinaryTreeNode* pNode3 = createBinaryTreeNode(14);
	BinaryTreeNode* pNode4 = createBinaryTreeNode(4);
	BinaryTreeNode* pNode5 = createBinaryTreeNode(8);
	BinaryTreeNode* pNode6 = createBinaryTreeNode(12);
	BinaryTreeNode* pNode7 = createBinaryTreeNode(16);

	connectBinaryTreeNode(pNode1,pNode2,pNode3);
	connectBinaryTreeNode(pNode2,pNode4,pNode5);
	connectBinaryTreeNode(pNode3,pNode6,pNode7);
	
	//preOrder(pNode1);
	//midOrder(pNode1);
	postOrder(pNode1);

	destoryBinaryTree(pNode1);
}
//左边有树枝
/*
     10
    /  
   6  
  / \  
 14  4 
*/
void test2()
{
	BinaryTreeNode* pNode1 = createBinaryTreeNode(10);
	BinaryTreeNode* pNode2 = createBinaryTreeNode(6);
	BinaryTreeNode* pNode3 = createBinaryTreeNode(14);
	BinaryTreeNode* pNode4 = createBinaryTreeNode(4);
	connectBinaryTreeNode(pNode1,pNode2,NULL);
	connectBinaryTreeNode(pNode2,pNode3,pNode4);
	
	//preOrder(pNode1);
	//midOrder(pNode1);
	postOrder(pNode1);

	destoryBinaryTree(pNode1);

}
//右边有树枝
/*
  10
         6
    /    14  4
*/
void test3()
{
	BinaryTreeNode* pNode1 = createBinaryTreeNode(10);
	BinaryTreeNode* pNode2 = createBinaryTreeNode(6);
	BinaryTreeNode* pNode3 = createBinaryTreeNode(14);
	BinaryTreeNode* pNode4 = createBinaryTreeNode(4);
	connectBinaryTreeNode(pNode1,NULL,pNode2);
	connectBinaryTreeNode(pNode2,pNode3,pNode4);
	
	//preOrder(pNode1);
	//midOrder(pNode1);
	postOrder(pNode1);

	destoryBinaryTree(pNode1);

}
//只有根节点
void test4()
{
	BinaryTreeNode* pNode1 = createBinaryTreeNode(10);

	//preOrder(pNode1);
	//midOrder(pNode1);
	postOrder(pNode1);

	destoryBinaryTree(pNode1);

}
//空树
void test5()
{
	//preOrder(NULL);
	//midOrder(NULL);
	postOrder(NULL);
}

int main()
{
	test1();
	printf("\n");
	test2();
	printf("\n");
	test3();
	printf("\n");
	test4();
	printf("\n");
	test5();
	return 0;
}

二叉树非递归和递归遍历（先序，中序，后序）,布布扣,bubuko.com

二叉树非递归和递归遍历（先序，中序，后序）

原文：http://blog.csdn.net/walkerkalr/article/details/20287119