【CPP】各种各样的树（2）——普通二叉树（数组与链表）

不知道多久以前的上期介绍了一种比较广泛的树，儿子兄弟表示法的普通树。这种树实际上也是一种二叉树，但是由于它在概念上并不是二叉的，所以决定先来介绍这种树。而如今，儿子兄弟表示法的树已经讲完了，现在来理解更为实用且实际上更为简单的二叉树想必会更加容易了。

二叉树，顾名思义是如封面图一样分为两叉的树形结构，仍然是树根朝上来绘制，这种树很适合计算机进行理解，树通常左子树用0表示，右子树用1表示，也算是充满了二进制思想的数据结构了。如果上次的普通树有好好去实现过的话，写一个二叉树想来也是很轻松的，如同上次的代码一样来写个链表实现的二叉树吧。

如上图使用最简单的递归生成二叉树的方法，在函数内来输入树，按照前序遍历的顺序来一个个结点地输入这个二叉树，很短很简单的代码便能生成一个没有任何特殊地方的二叉树。二叉树的重点就是每个结点都分为两叉，由左右指针来指向下一级。

刚才提到前序遍历，想必这并不是一个很好理解的部分。什么是前序遍历呢？我们这里先假定我们有一棵完整的二叉树，然后我们来用前序遍历来遍历它的每一个结点。前序遍历，也叫先根遍历，这个遍历的方法就是先访问（输出）根结点，然后输出左子树根结点，然后不断深入，直到叶子结点返回，逐层先根地访问右子树，直到完成整棵树的遍历。通过我的描述可以想象，这是会是段很适合递归的代码，代码如下想象一下。

很简单的一段递归程序，在代码中我们可以发现规律，前序遍历就是先访问再进行递归，对应一下刚才二叉树的生成，前序遍历生成树就是结点的输入是按照前序输入的。那么有了前序遍历，我们自然会想，是否有中序和后序呢？确实是有的，而且只需改变一下访问的时机就能实现这两种遍历。

到这里我们可能会有疑惑，人类平时在看树形结构的时候，一般是按照视觉习惯以类似读文字的顺序来看的，也就是从上往下从左往右地看，为什么计算机要用这几种奇怪的遍历呢？很简单可以想到，这样的遍历方式更简单编写，且在很多时候更适合实际的问题需要，我们在很多时候是并不需要访问树的每一层的，很多时候我们只需要它的某一子树即可。但是平时的那种观看方式也并不是没有用处，它被称作层次遍历，利用之前说过的队列结构就能实现，实现起来也并不是非常麻烦，这里我们使用stl库的queue文件。

这就是链表二叉树的几个常用的遍历方式了，它的插入，删除，查找这三个常见操作我们以后再说。

说过二叉树的链表实现，细想一下我们可以想，二叉树是不是可以不用链表来实现呢？没错，我们可以使用数组来实现二叉树，而且也一样简单，数组二叉树的关键规则是左子树放置在根的2n+1位置，右子树放在根的2n+2的位置，根放在n的位置，然后仍然需要用特定的规则来访问它，只不过数组实现的二叉树在有些时候会有意想不到的效果，例如我们由此可以随机地来访问树的每个结点。下面是代码，这代码采取了直接输入数组的每个元素来实现树然后先序遍历来打印。