二叉树的先序、中序、后序遍历的递归跟非递归实现

二叉树的先序、中序、后序遍历的递归和非递归实现

#include "stdafx.h"
#include <iostream>
using namespace std;

const int MAXSIZE = 20; //定义栈空间大小为20

struct BTNode
{
	char m_value;
	BTNode *m_left;
	BTNode *m_right;
};

BTNode *stackArr[MAXSIZE] = {0};//用一个静态数组模拟栈
int nTop = -1;//初始状态下nTop=-1表示栈空

//先序创建二叉树
void CreatBTree(BTNode *&root)
{	
    char nValue = 0;
	cin >> nValue;
	if ('#' == nValue)
	{
	   return;
	}
	else
	{
		root = new BTNode();
		root->m_value = nValue;
		CreatBTree(root->m_left);
		CreatBTree(root->m_right);
	}	
}

//先序遍历二叉树（递归）
void PreOrderTravse(BTNode *&pRoot)
{
	if (pRoot != NULL)
	{
		cout << pRoot->m_value << " ";
		PreOrderTravse(pRoot->m_left);		
		PreOrderTravse(pRoot->m_right);
	}
}

//中序遍历二叉树（递归）
void InOrderTravse(BTNode *&pRoot)
{
	if (pRoot != NULL)
	{
		InOrderTravse(pRoot->m_left);
		cout << pRoot->m_value << " ";
		InOrderTravse(pRoot->m_right);
	}
}

//后序遍历二叉树（递归）
void PostOrderTravse(BTNode *&pRoot)
{
	if (pRoot != NULL)
	{
		PostOrderTravse(pRoot->m_left);		
		PostOrderTravse(pRoot->m_right);
		cout << pRoot->m_value << " ";
	}
}

//先序遍历二叉树（非递归）
void PreOrderNoReTravse(BTNode *pRoot)
{
	BTNode *pCur = pRoot;
	while (pCur != NULL || nTop != -1)//当前指针不空或栈不空
	{
		while (pCur != NULL)//当前指针不空
		{
			cout << pCur->m_value << " ";
			stackArr[++nTop] = pCur;//将当前指针入栈
			pCur = pCur->m_left;
		}

		if (nTop != -1)//栈不空
		{
			BTNode *pTop = stackArr[nTop--];//获取栈顶指针且栈顶指针出栈			
			pCur = pTop->m_right;
		}
	}
}

//中序遍历二叉树（非递归）//递归转换为非递归：利用栈和while循环
void InOrderNoReTravse(BTNode *pRoot)
{
	BTNode *pCur = pRoot;
	while (pCur != NULL || nTop != -1)//当前指针不空或栈不空
	{
		while (pCur != NULL)//当前指针不空
		{			
			stackArr[++nTop] = pCur;//将当前指针入栈
			pCur = pCur->m_left;
		}

		if (nTop != -1)//栈不空
		{
			BTNode *pTop = stackArr[nTop--];//获取栈顶指针且栈顶指针出栈
			cout << pTop->m_value << " ";
			pCur = pTop->m_right;
		}
	}
}

//后序遍历二叉树（非递归）
void PostOrderNoReTravse(BTNode *pRoot)
{	
    BTNode *pCur = pRoot;
	BTNode *pTop = NULL;
	int nTag[MAXSIZE] = {0}; //标记数组标记每个元素的左右子树是否都已经被访问过了
	while (pCur != NULL || nTop != -1)//当前指针不空或栈不空
	{
		while (pCur != NULL)//当前指针不空
		{			
			stackArr[++nTop] = pCur;//将当前指针入栈
			nTag[nTop] = 0;//表示第一次位于栈顶
			pCur = pCur->m_left;
		}

		while (nTop != -1 && nTag[nTop] == 1)
		{//栈不空且栈顶指针指向的结点被标记为1即表示给结点的左右子树都已经被访问过了，第二次位于栈顶
	        pTop = stackArr[nTop--];//获取栈顶指针且栈顶指针出栈
			cout << pTop->m_value << " ";
		}

		if (nTop != -1)//栈不空  此时标记为0,意味着应该访问其右子树
		{	            
			pTop = stackArr[nTop];//取到栈顶元素，注意此时不能出栈
			pCur = pTop->m_right;
			nTag[nTop] = 1;
		}
	}
}

// 后序遍历二叉树（非递归）思想：
// 对于一棵树t,如果t非空，首先应该进入t的左子树访问，此时由于t的右子树及根结点尚未访问，
// 因此必须将t保存起来，放入栈中，以便访问完左子树后，从栈中取出t，进行其右子树及根结点的访问。
// 这里值得注意的是，当一个元素位于栈顶即将处理时，其左子树的访问一定已经完成，
// 如果其右子树尚未遍历，接下来应该进入其右子树的访问，而此时该栈顶元素是不能出栈的，
// 因为其根结点还未被访问；只有等到其右子树也访问完成后，该栈顶元素才能出栈，并输其根结点的值。
// 因此，在二叉树后序遍历的过程中，必须使用标记数组，其每个元素取值为0或1，
// 用于标识栈中每个元素的状态。当一个元素刚进栈时，其对应的tag值置0；当它第一次位于栈顶即将
// 被处理时，其tag值为0，意味着应该访问其右子树，于是将其右子树作为当前处理的对象，
// 此时该栈顶元素仍应该保留在栈中，并将其对应的tag值改为1；当其右子树访问完成后，
// 该元素又一次位于栈顶，而此时其tag值为1，意味着应该访问其根结点，并将其出栈。
// 在整个二叉树后序遍历的过程中，程序要做的工作始终分成两个部分：当前正在处理的树（子树）
// 和保存在栈中待处理的部分。只有这两部分的工作均完成后，程序方能结束。

int _tmain(int argc, _TCHAR* argv[])
{
	BTNode *pRoot = NULL;
	CreatBTree(pRoot);

    cout << "二叉树的先序、中序、后序遍历(递归)分别为：" << endl;
	PreOrderTravse(pRoot);//先序遍历递归
	cout << endl;
	InOrderTravse(pRoot);//中序遍历递归
	cout << endl;
	PostOrderTravse(pRoot);//后序遍历递归
	cout << endl;

    cout << "二叉树的先序、中序、后序遍历(非递归)分别为：" << endl;
	PreOrderNoReTravse(pRoot);//先序遍历非递归
	cout << endl;
	InOrderNoReTravse(pRoot);//中序遍历非递归
	cout << endl;
	PostOrderNoReTravse(pRoot);//中序遍历非递归
	cout << endl;

	system("pause");
	return 0;
}

运行结果：