二叉树遍历算法主要包括递归遍历方式、非递归遍历方式。而每一种方式又分为先序遍历、中序遍历、后序遍历。如果你的二叉树是二叉排序树，希望遍历出来的结果是有序的，那么无论是递归还是飞递归都需要使用中序遍历。另外，有时，我们也需要对二叉树进行层序遍历。假设二叉树结构如下：

树的构建代码如下：

#include <iostream>

struct BiNode 
{
	char ch;
	BiNode* lchild;
	BiNode* rchild;
};

int main()
{
	//创建结点
	BiNode node1, node2, node3, node4, node5, node6, node7, node8;
	node1.ch = 'A'; node1.lchild = nullptr; node1.rchild = nullptr;
	node2.ch = 'B'; node2.lchild = nullptr; node2.rchild = nullptr;
	node3.ch = 'C';	node3.lchild = nullptr; node3.rchild = nullptr;
	node4.ch = 'D';	node4.lchild = nullptr; node4.rchild = nullptr;
	node5.ch = 'E';	node5.lchild = nullptr; node5.rchild = nullptr;
	node6.ch = 'F';	node6.lchild = nullptr; node6.rchild = nullptr;
	node7.ch = 'G';	node7.lchild = nullptr; node7.rchild = nullptr;
	node8.ch = 'H';	node8.lchild = nullptr; node8.rchild = nullptr;

	//建立结点关系
	node1.lchild = &node2;
	node1.rchild = &node6;
	node2.rchild = &node3;
	node3.lchild = &node4;
	node3.rchild = &node5;
	node6.rchild = &node7;
	node7.lchild = &node8;

	return 0;
}

1. 二叉树递归遍历 {#title-0} =====================

我们接下来编码实现其递归遍历：

// 先序遍历
void recursion_traversal(BiNode* root) 
{
	if (root == NULL) 
	{
		return;
	}
	printf("%c", root->ch);
	recursion_traversal(root->lchild);
	recursion_traversal(root->rchild);
}

// 中序遍历
void recursion_traversal(BiNode* root) 
{
	if (root == NULL) 
	{
		return;
	}
	recursion_traversal(root->lchild);
	printf("%c", root->ch);
	recursion_traversal(root->rchild);
}

// 后序遍历
void recursion_traversal(BiNode* root) 
{
	if (root == NULL) 
	{
		return;
	}
	
	recursion_traversal(root->lchild);
	recursion_traversal(root->rchild);
	printf("%c", root->ch);
}

2. 二叉树非递归遍历 {#title-1} ======================

二叉树非递归遍历算法需要借助栈容器的辅助。

void non_recursion_traversal(BiNode* root)
{

	// 根节点入栈
	std::stack<std::pair<bool, BiNode*>> stack;
	stack.push(std::make_pair(false, root));

	while (!stack.empty())
	{
		// 弹出栈顶元素
		auto element = stack.top();
		stack.pop();

		// 如果栈顶元素标记为 true 则直接输出
		if (element.first)
		{
			std::cout << element.second->ch << " ";
			continue;
		}

		// 如果栈顶元素标记为 false, 则按下面的规则再次进行入栈操作
		/*
		* 如果先序遍历，则入栈顺序为：右、左、根
		* 如果中序遍历，则入栈顺序为：右、根、左
		* 如果后序遍历，则入栈顺序为：根、右、左
		* 注意: 根节点第二次入栈时，需要将其 first 属性修改为 true
		*/

		// 右结点
		if (element.second->rchild != nullptr)
		{
			stack.push(std::make_pair(false, element.second->rchild));
		}
		
		// 左结点
		if (element.second->lchild != nullptr)
		{
			stack.push(std::make_pair(false, element.second->lchild));
		}

		// 根节点
		element.first = true;
		stack.push(element);
	}
}

程序输出结果：

A B C D E F G H

3. 二叉树层序遍历 {#title-2} =====================

二叉树的层序遍历需要借助队列容器的辅助。层序遍历顾名思义，就是从上向下，从左向右一层一层的遍历二叉树中的每个元素。

void level_traversal(BiNode* root)
{

	// 根节点入栈
	std::queue<BiNode *> queue;
	queue.push(root);

	while (!queue.empty())
	{
		// 弹出队头元素
		auto element = queue.front();
		queue.pop();

		// 打印队头元素
		std::cout << element->ch << " ";

		// 将当前根节8点的左右子结点入队列
		if (element->lchild != nullptr)
		{
			queue.push(element->lchild);
		}

		// 左结点
		if (element->rchild != nullptr)
		{
			queue.push(element->rchild);
		}
	}
}

程序输出结果：

A B F C G D E H