摘要：二叉树主要有3种遍历算法，分为为先序、中序、后序。本文对二叉树的3种遍历算法的遍历规则进行介绍，并给出3种遍历算法的递归和迭代版本的C++实现。文章发出后，我的好朋友指出还有一个层次遍历，我将在文章最后介绍。
1. 二叉树遍历
如图1所示，一颗二叉树T由根节点V、左子树L和右子树R构成。
图1 二叉树示意图
则二叉树T的遍历指：按照某种次序访问树中各节点，每个节点被访问恰好一次。二叉树T的先序、中序、后序遍历的结果如图2所示。
图2 二叉树的先序、中序、后序遍历
从图中可以看出，先序、中序、后序的区别在于局部根节点的访问时机，而对于左右孩子的访问，其访问顺序总是满足先左后右的规则。下面举例说明二叉树的遍历规则，一棵二叉树的结构如图3所示，则其遍历结果如下：
先序遍历结果：A B D E G H C F
中序遍历结果：D B G H E A C F
后序遍历结果：D H G E B F C A
图3 一颗普通的二叉树
2. 二叉树节点
在实现二叉树的遍历算法之前，我们先创建一个二叉树节点类。二叉树节点是二叉树的基本组成单位，节点与节点之间有父子关系、兄弟关系等，由于节点的数据类型不确定，所以采用模板实现二叉树的节点类。
/*
二叉树节点
*/
#define BiNodePos(T) BiNode<T>*
template<typename T>
struct BiNode{
BiNodePos(T) parent= nullptr, lChild = nullptr, rChild = nullptr;
T data; int height;
BiNode(T data, BiNodePos(T) parent){
this->data = data;
this->parent = parent;
}
//子树规模
int size() {
int s = 1;//计入本身
if (lChild) s += lChild.size();//递归计入左子树规模
if (rChild) s += rChild.size();//递归计入右子树规模
return s;
}
//插入左孩子
BiNodePos(T) insertAsLC(const T &) {
return lChild = new BiNode(e, this);
}
//插入右孩子
BiNodePos(T) insertAsRC(const T &) {
return rChild = new BiNode(e, this);
}
};
3. 二叉树遍历算法的实现
3.1. 递归版本
#include <stack>
using namespace std;
//先序遍历
template<typename T, typename VST >
void preTraverse(BiNodePos(T) x, VST& visit)
{
if (!x) return;
visit(x->data);
preTraverse(x->lChild);
preTraverse(x->rChild);
}//O(n)
//中序遍历
template<typename T, typename VST >
void midTraverse(BiNodePos(T) x, VST& visit)
{
if (!x) return;
midTraverse(x->lChild);
visit(x->data);
midTraverse(x->rChild);
}//O(n)
//后序遍历
template<typename T, typename VST >
void postTraverse(BiNodePos(T) x, VST& visit)
{
if (!x) return;
postTraverse(x->lChild);
postTraverse(x->rChild);
visit(x->data);
}//O(n)
3.2. 迭代版本
递归版本的时间复杂度是O(n)，理论上递归遍历算法已经事件复杂度已经最小了。但实际上，由于递归实例必须具有通用的格式，所以在运行栈中，每一个递归实例对应的一帧不可能做到足够的小。而针对于具体的问题，我们完全可以通过精巧的设计使得每一帧做到足够小的，所以，我们有必要将递归版本转化为迭代版本。
#include <stack>
using namespace std;
template<typename T, typename VST>
static void visitAlongLeftBranch(BiNodePos(T) x, VST& visit, stack<BiNodePos(T)> &s)
{
while (x!=nullptr)
{
visit(x->data);
s.push(x->rChild);
x = x->lChild;
}
}
template<typename T, typename VST >
void preIterationTraverse(BiNodePos(T) x, VST& visit)
{
stack<BiNodePos(T)> s;
while (true)
{
visitAlongLeftBranch(x, visit, s);
if (s.empty) break;
x = s.top();
s.pop();
}
}//O(n)
template<typename T>
static void goAlongLeftBranch(BiNodePos(T) x,stack<BiNodePos(T)> &s)
{
while (x!=nullptr)
{
s.push(x);
x = x->lChild;
}
}
template<typename T, typename VST >
void inIterationTraverse(BiNodePos(T) x, VST& visit)
{
stack<BiNodePos(T)> s;
while (true)
{
goAlongLeftBranch(x, s);
if (s.empty) break;
x = s.top();
s.pop();
visit(x->data);
x = x->rChild;
}
}//O(n)
template < typename T>
static void gotoLVFL(stack<BiNodePos(T)> s) {
BiNodePos(T) node;
while (node = s.top()) {
if (node->lChild){
if (node->rChild)
s->push(node->rChild);
s->push(node->lChild);
}
else
s->push(node->rChild);
}
s.pop();
}
template<typename T, typename VST >
void postIterationTraverse(BiNodePos(T) x, VST& visit)
{
stack<BiNodePos(T)> s;
if (x!=nullptr) s.push(x);
while (!s.empty())
{
if (s.top() != x->parent)
gotoLVFL<T>(s);
x = s.top();
visit(x->data);
}
}//O(n)
4. 层次遍历
首先，感谢大佬帮我指正问题。
层次遍历是指：按层次遍历树的所有节点（即逐层地，从左到右访问所有节点）。下面是层次遍历的迭代实现。
#include <deque>
using namespace std;
template<typename T, typename VST >
void levelIterationTraverse(BiNodePos(T) x, VST& visit)
{
deque<BiNodePos(T)> q;
q.push_back(x);
while (!q.empty())
{
x = q.front(); q.pop_front();
visit(x.data);
if (x->lChild) q.push_back(x->lChild);
if (x->rChild) q.push_back(x->rChild);
}
}//O(n)
5. Java版本的实现（补充）
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public void preOrder(TreeNode root)
{
Stack<TreeNode> stack = new Stack<TreeNode>();
while(root != null || !stack.empty())
{
while(root != null)
{
System.out.print(root.val + " ");
stack.push(root);
root = root.left;
}
if(!stack.empty())
{
root = stack.pop();
root = root.right;
}
}
}
void midOrder(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
while(root != null || !stack.empty())
{
while(root != null)
{
stack.push(root);
root = root.left;
}
if(!stack.empty())
{
root = stack.pop();
System.out.print(root.val + " ");
root = root.right;
}
}
}
/**
* 后序遍历的难点在于：
* 需要判断上次访问的节点是位于左子树，还是右子树。
* 若是位于左子树，则需跳过根节点，先进入右子树，再回头访问根节点；
* 若是位于右子树，则直接访问根节点
* @param root
*/
void postOrder(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode curr = root, last = null;
//先把curr移动到左子树最下边
while (curr != null){
stack.push(curr);
curr = curr.left;
}
while (!stack.isEmpty()){
curr = stack.peek();
//一个根节点被访问的前提是：无右子树或右子树已被访问过
if (curr.right == null || curr.right == last){
System.out.print(curr.val + " ");
last = curr;
stack.pop();
}
else {
//进入右子树
curr = curr.right;
while (curr != null){
stack.push(curr);
curr = curr.left;
}
}
}
}
void levelOrder(TreeNode root){
if (root == null)
return;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()){
TreeNode node = queue.poll();
System.out.print(node.val + " ");
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
}
