二叉树遍历（前序、中序、后序、层次）

四种遍历的基本思想：
前序遍历：根节点 --> 左子树 --> 右子树
中序遍历：左子树 --> 根节点 --> 右子树
后序遍历：左子树 --> 右子树 --> 根节点
层次遍历：由上到下，由左到右依次遍历

例子：

前序遍历：1 2 4 5 3 6 7
中序遍历：4 2 5 1 6 3 7
后序遍历：4 5 2 6 7 3 1
层次遍历：1 2 3 4 5 6 7

一、层次遍历
层次遍历需要借助一个队列，代码如下：

//层次遍历
void levelOrder(TreeNode* pRoot) {
	if (!pRoot) return;
	queue<TreeNode*> que;
	que.push(pRoot);
	while (!que.empty()) {
		TreeNode* pNode = NULL;
		pNode = que.front();
		cout << pNode->data << " ";
		que.pop();
		if (pNode->left != NULL)
			que.push(pNode->left);
		if (pNode->right != NULL)
			que.push(pNode->right);
	}
}

二、前序、中序、后序遍历的递归实现

//前序遍历递归实现
void preOrderRecursion(TreeNode* pRoot) {
	if (!pRoot) return;
	cout << pRoot->data << " ";			//根结点
	preOrderRecursion(pRoot->left);		//左子树
	preOrderRecursion(pRoot->right);	//右子树
}
//中序遍历递归实现
void inOrderRecursion(TreeNode* pRoot) {
	if (!pRoot) return;
	inOrderRecursion(pRoot->left);		//左子树
	cout << pRoot->data << " ";			//根结点
	inOrderRecursion(pRoot->right);		//右子树
}
//后序遍历递归实现
void postOrderRecursion(TreeNode* pRoot) {
	if (!pRoot) return;
	postOrderRecursion(pRoot->left);		//左子树
	postOrderRecursion(pRoot->right);		//右子树
	cout << pRoot->data << " ";				//根结点
}

三、前序、中序、后序遍历的非递归实现
能用递归实现的代码，一般都能借助堆栈用非递归实现。

1、前序遍历非递归实现
a、访问根结点它并把入栈，如果根结点左孩子存在，访问左孩子并将其入栈，重复此操作直到当前结点无左孩子；
b、当到达最左端后，栈中结点依次出栈，每出栈一个结点后都判断该结点右孩子是否存在；
c、如果出栈结点的右孩子存在，则以右孩子为根节点重复a操作。

//前序遍历非递归实现
void preOrder(TreeNode* pRoot) {
	if (!pRoot) return;
	stack<TreeNode*> sta;
	TreeNode* p = pRoot;
	while (p != NULL || !sta.empty()) {
		while (p) {
			cout << p->data << " ";
			sta.push(p);
			p = p->left;
		}
		if (!sta.empty()) {
			p = sta.top();
			sta.pop();
			p = p->right;
		}
	}
}

2、中序遍历非递归实现
a、将根结点入栈，如果根结点左孩子存在，将其入栈，重复此操作直到当前结点无左孩子；
b、当到达最左端后，栈中结点依次出栈，每出栈一个结点后都访问它，并判断其右孩子是否存在；
c、如果出栈结点的右孩子存在，则以右孩子为根节点重复a操作。

注：前序遍历和中序遍历非递归实现的思想是一样的，都借助堆栈，唯一区别就是访问结点的时机不同。

//中序遍历非递归实现
void inOrder(TreeNode* pRoot) {
	if (!pRoot) return;
	stack<TreeNode*> sta;
	TreeNode* p = pRoot;
	while (p != NULL || !sta.empty()) {
		while (p) {
			sta.push(p);
			p = p->left;
		}
		if (!sta.empty()) {
			p = sta.top();
			cout << p->data << " ";
			sta.pop();
			p = p->right;
		}
	}
}

3、后序遍历非递归实现
思路：从根结点开始，将所有最左结点入栈，每当一个结点出栈时，都先扫描该节点的右子树，只有当一个结点的左孩子和右孩子均被访问过了，才能访问结点自身。
a、将根结点入栈，如果根结点左孩子存在，将其入栈，重复此操作直到当前结点无左孩子；
b、当到达最左端后，并判断其右孩子是否存在且没有被访问过，若其右孩子存在且为被访问过，重复a操作；
c、若当前结点右孩子不存在或被访问过，则访问当前结点并将其出栈，并将pre指向它（pre标记上一个被访问的结点）。

//后序遍历非递归实现
void postOrder(TreeNode* pRoot) {
	if (!pRoot) return;
	stack<TreeNode*> sta;
	TreeNode* p = pRoot->left, *pre = NULL;
	sta.push(pRoot);
	while (!sta.empty()) {
		while (p) {
			sta.push(p);
			p = p->left;
		}
		TreeNode* pNode = sta.top();
		if (pNode->right && pre != pNode->right) {
			p = pNode->right;
		}
		else {
			cout << pNode->data << " ";
			pre = pNode;
			sta.pop();
		}
	}
}

C++完整代码如下：

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

struct TreeNode {
	int data;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
		data(x), left(NULL), right(NULL) {
	}
};

//层次遍历
void levelOrder(TreeNode* pRoot) {
	if (!pRoot) return;
	queue<TreeNode*> que;
	que.push(pRoot);
	while (!que.empty()) {
		TreeNode* pNode = NULL;
		pNode = que.front();
		cout << pNode->data << " ";
		que.pop();
		if (pNode->left != NULL)
			que.push(pNode->left);
		if (pNode->right != NULL)
			que.push(pNode->right);
	}
}
//前序遍历递归实现
void preOrderRecursion(TreeNode* pRoot) {
	if (!pRoot) return;
	cout << pRoot->data << " ";	//根结点
	preOrderRecursion(pRoot->left);		//左子树
	preOrderRecursion(pRoot->right);		//右子树
}
//中序遍历递归实现
void inOrderRecursion(TreeNode* pRoot) {
	if (!pRoot) return;
	inOrderRecursion(pRoot->left);		//左子树
	cout << pRoot->data << " ";	//根结点
	inOrderRecursion(pRoot->right);		//右子树
}
//后序遍历递归实现
void postOrderRecursion(TreeNode* pRoot) {
	if (!pRoot) return;
	postOrderRecursion(pRoot->left);		//左子树
	postOrderRecursion(pRoot->right);		//右子树
	cout << pRoot->data << " ";				//根结点
}

//前序遍历非递归实现
void preOrder(TreeNode* pRoot) {
	if (!pRoot) return;
	stack<TreeNode*> sta;
	TreeNode* p = pRoot;
	while (p != NULL || !sta.empty()) {
		while (p) {
			cout << p->data << " ";
			sta.push(p);
			p = p->left;
		}
		if (!sta.empty()) {
			p = sta.top();
			sta.pop();
			p = p->right;
		}
	}
}
//中序遍历非递归实现
void inOrder(TreeNode* pRoot) {
	if (!pRoot) return;
	stack<TreeNode*> sta;
	TreeNode* p = pRoot;
	while (p != NULL || !sta.empty()) {
		while (p) {
			sta.push(p);
			p = p->left;
		}
		if (!sta.empty()) {
			p = sta.top();
			cout << p->data << " ";
			sta.pop();
			p = p->right;
		}
	}
}

//后序遍历非递归实现
void postOrder(TreeNode* pRoot) {
	if (!pRoot) return;
	stack<TreeNode*> sta;
	TreeNode* p = pRoot->left, *pre = NULL;
	sta.push(pRoot);
	while (!sta.empty()) {
		while (p) {
			sta.push(p);
			p = p->left;
		}
		TreeNode* pNode = sta.top();
		if (pNode->right && pre != pNode->right) {
			p = pNode->right;
		}
		else {
			cout << pNode->data << " ";
			pre = pNode;
			sta.pop();
		}
	}
}

//二叉树遍历算法
void binaryTreeOrder()
{
	struct TreeNode t1(1), t2(2), t3(3), t4(4), t5(5), t6(6), t7(7);
	t1.left = &t2;
	t1.right = &t3;
	t2.left = &t4;
	t2.right = &t5;
	t3.left = &t6;
	t3.right = &t7;
	printf(" 层次遍历：");
	levelOrder(&t1);
	printf("\n 递归\n");
	printf(" 前序遍历：");
	preOrderRecursion(&t1);
	printf("\n 中序遍历：");
	inOrderRecursion(&t1);
	printf("\n 后序遍历：");
	postOrderRecursion(&t1);
	printf("\n 非递归\n");
	printf(" 前序遍历：");
	preOrder(&t1);
	printf("\n 中序遍历：");
	inOrder(&t1);
	printf("\n 后序遍历：");
	postOrder(&t1);
}

int main()
{
	binaryTreeOrder();
	system("pause");
	return 0;
}

执行结果如下：