上篇文章我们讲到树，而在树当中，有一个极为特殊的树——二叉树 ( Binary Tree )

那么今天就来学习关于二叉树的知识

二叉树

那么，什么是二叉树呢，与它的名字差不多，它会分两个叉，这就是二叉树最直观的特点，准确来说，二叉树是在树的基础上规定了树上的任何一个节点的度不能大于 2，简单点说就是一个结点最多只能有两个儿子结点，如下图就是一棵二叉树

二叉树可以没有子结点，只有一个子结点或有两个子结点

另外，只有根结点或者为空的树也是二叉树

二叉树的术语，类型及性质

因为二叉树的特别，在树的基础上又有了其他新的术语

1. 左儿子 : 在二叉树的结点中，在其儿子中位于左边的儿子叫做左儿子，可能没有

2. 右儿子 : 在二叉树的结点中，在其儿子中位于右边的儿子叫做右儿子，可能没有

二叉树有着其他的类型，也有不同的名称

1. 满二叉树 : 整个二叉树中只包含度为 0 ( 叶子结点 ) 和 2 ( 左右儿子都有 ) 的结点且度为 0 的结点都在同一层时，这棵二叉树就称为满二叉树与它的名字相同，这种二叉树是饱满的，就像是一个三角形，例如下面第一张图就是一个满二叉树

2. 完全二叉树 : 容易与满二叉树混淆，高度为 h 的二叉树与高度同为 h 的完全二叉树按层次的顺序编号，如果两者位置相同且存在的结点编号相同，则此二叉树为完全二叉树简单点来说，完全二叉树就是三角形 ( 满二叉树 ) 缺失了最后一行的右下角的部分，且是从右到左连续的一部分，特别的，满二叉树是完全二叉树，例如下面第二张图就展示了哪些是完全二叉树，哪些不是

一棵满二叉树，同时也是完全二叉树

满二叉树

满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树

一些例子

二叉树的特别让它也有了一些性质，至于原因会在后面讲

1. 二叉树的第 k 层上最多有  个结点

2. 高度为 h 的二叉树最多有  个结点

3. 在二叉树中，度为 0 的结点的数量 = 度为 2 的结点数量 + 1

4. 有 n 个结点的满二叉树的高度为 

5. 对一个有 n 个结点的完全二叉树按照层次进行编号 ( 从 1 到 n )，若有 i (  )当 i = 1 时，则该结点为此树的根结点当 i > 1 时，则该结点的父亲结点的编号为 当 2i ≤ n 时，则该结点的左儿子结点的编号为 ，如果 2i ＞n 则没有左儿子，并且同时没有右儿子当 2i + 1 ≤ n 时，则该结点的右儿子结点的编号为 ，如果 2i+1 > n 则没有右儿子

现在让我们来依次证明一下

1. 要使二叉树每一层的结点数量尽可能的多，就要让那一层全部排满，而我们知道，二叉树的一个结点最多只有两个儿子，所以第一层最多只有一个结点，第二层最多就只有两个结点，第三层最多就只有四个结点，第四层最多就只有八个结点，就像是细胞分裂一样以此类推，第 k 层上最多就只有  个结点

2. 利用上一个性质可以得出在某一层最多的结点个数，一棵高度为 h 的二叉树的结点总数为怎么算?好吧用第二个式子×2减去第二个式子就行了 这就证明出来了

3. 度为 0 的结点就是叶子结点，那么我们可以这样想，如果根结点的度为 1，那么下一层的结点数量就为 1，如果根结点的度为 2，那么下一层的结点数量就为 2也就是说，如果度为 2，那么就会新增一个分支的结点，叶子结点无论如何都会增加 1，至于为什么要加 1 是因为就算没有度为 2 的结点也总是会有一个叶子结点

4. 这个性质跟第二条性质一样，这里就不说了

5. 这里必须是要完全二叉树，不是完全二叉树是没有这个性质的

二叉树的遍历以及根据遍历画树

二叉树的遍历分为前序遍历，中序遍历以及后序遍历

这三种不同的遍历方式遵循不同的优先方式，分别为根左右，左根右，左右根

这代表先写下树中的哪一个部分，例如根左右，就是先写根，在写左子树，最后写右子树

例如下面这棵树，它的前序遍历为 124536，中序遍历为 425163，后序遍历为 452631

额...没错就是上面那张图...

那如何根据树来写相对应的遍历方式呢

例如前序遍历，首先写下根 ( 1 )，然后是左边，这时候，我们将左边以 2 为根的子树看做是一棵树，并在这棵树上继续进行遍历，继续按照根左右来写下 ( 2 )，然后继续向左走，将以 4 为根的子树看做一棵树，并写下根 ( 4 )，但是这里已经没有左右子树了，所以就向上回溯，来到以 2 为根的子树，刚才遍历到了左边，现在遍历右子树，即以 5 结点为根的子树继续遍历...

最后就能够得到前序遍历了

同样的方法，也可以得到二叉树的中序和后序遍历

单单学会写遍历不行，还要根据遍历画树，这里就先讲比较简单的根据前序遍历和中序遍历画树及根据后序遍历和前序遍历画树

前序遍历为 124356，中序遍历为 421536

我们知道，前序遍历遍历的第一个结点就是整棵树的根结点，即 1 号结点，所以我们可以先将结点 1 画下来

先画一个结点 1

随后我们看到中序遍历，找到其中的 1，我们知道中序遍历的顺序是左根右，所以根结点的左边就是根的左子树 ( 42 )，根的右边就是根的右子树 ( 536 )，同样的，在前序遍历中找到 ( 42 ) 和 ( 536 ) ( 顺序不对不用管，只要找到这几个数就行 )，先看左子树部分，第一个数为 2，所以左子树的根结点为 2，就把 2 给画下来

画下结点 2，并与结点 1 连接

随后与第一步相同，在中序遍历中以 2 为分界，找出左子树 ( 4 ) 和右子树 ( 无 )，我们发现结点 2 没有右子树，只有左子树，且只有一个结点，这时候就可以直接画上去了

画出结点 4，并连接结点 2

并以此类推，继续画出结点 1 的右子树，最后你就成功知道了作者懒得画树得到了这棵二叉树树

成功画出来啦

同理，因为后序遍历是左右根，所以根结点在最后面，只要在找根结点时找最后面即可

好了那么关于二叉树的内容就讲到这里了，下篇文章将会讲一讲如何使用线性表存储非线性的数据结构

如果你觉得本篇文章对你有所帮助，请不要忘记三连支持！