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

树的构建代码如下：

#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 = &amp;node2;
node1.rchild = &amp;node6;
node2.rchild = &amp;node3;
node3.lchild = &amp;node4;
node3.rchild = &amp;node5;
node6.rchild = &amp;node7;
node7.lchild = &amp;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