二叉树是一种常见的数据结构，对于这种常见的数据结构，在下也思考甚多，特做此记录，以便后序使用。本文章总结了常见的四种二叉树的遍历方式，对每种遍历方式写出了两种遍历方法：递归和非递归（迭代）。严格来说，遍历方式主要是两种：深度遍历和广度遍历。只不过深度遍历一般分为前序、中序和后序遍历；而广度遍历通俗地来说就是层序遍历，即一层一层地遍历。

1 构造二叉树    

二叉树节点如下：

图1.1  二叉树节点

通过一个数组构建一个二叉树，为了简便，用先序遍历的方式构造。在数组的值当中，用 “-1” 这一值代表该节点为空。如array[] = {1,2,-1,-1,3,-1,-1},这个数组表示根节点为1，左孩子为2，右孩子为3的一个三节点二叉树。

图1.2 通过数组构造二叉树 图1.3 节点图

根据先序遍历的原则，输入int array[]={1,2,4,8,-1,-1,-1,5,-1,-1,3,6,-1,-1,7,-1,-1};

2 先序遍历

    先序遍历遵循 “根左右” 的原则来遍历的。

2.1 递归法

图2.1 递归法先序遍历

2.2 迭代法

图2.2 迭代法先序遍历

    根据 “根左右” 的遍历顺序遍历时，在把这些节点放入栈的时候，是先把右再左后根的顺序依次放入栈当中。因此在对栈进行操作的时候，先取出栈顶元素（根节点），再依次放入该节点的右、左子节点。周而复始这个过程即可。

3 中序遍历

3.1 递归法

图3.1 中序遍历递归法

3.2 迭代法

图3.2 中序遍历迭代法

    这个思想比较巧妙，它首先寻找到最左边的节点（根据 “左根右” 的遍历原则，找到当前 “子树” 或者原树的最左边节点），在寻找最左节点的同时，把走过的节点（这里可以理解为父节点）依次存放到栈当中，以便遍历左子树后能够回溯到左子树根节点对应的父节点。

4 后序遍历

4.1递归法

图4.1 后序遍历递归法

4.2 迭代法

图4.2 后序遍历迭代法

    该函数运用了一个栈，因而就能获取最近添加的节点。在对栈的判断循环中，用了一个(current->left == NULL && current->right == NULL)，该语句表示为 “叶子结点”，根据 “左右根” 的原则，如果为叶子节点，则要么是左孩子要么是右孩子，均没访问。(prevous!= NULL)&&(prevous == current->left || prevous == current->right)则表示上一个被访问的节点为当前节点的左节点或者右节点，根据节点入栈的顺序 “根右左”可知，出栈的时候，如果当前节点跟上一次被访问的节点为父子关系，则说明当前节点是根，且以该节点为根节点的左右子树均已完成遍历。如果不是父子关系，则说明是兄弟关系，且当前节点为右节点。则继续把以该节点为根节点的左右子树入栈并；遍历

5 层序遍历

图5.1 层序遍历函数设计图

    该函数的设计思想是这么回事：首先把当前一层的所有节点压入队列，在压入队列的同时，需要做两个工作，一是把当前节点的值存放到vector容器里面，二是把当前一层的所有节点的孩子压入下一层队列。周而复始这个过程，直至最后一层，就能完成二叉树的层序遍历。不能该遍历最后得出的结果找到每个结果对应的父节点的值。

6 结果

图6.1 结果