vlambda博客
学习文章列表

不知道大家有没有玩过这样一种游戏，一个人写一个数，另一个人猜这个数是多少，每次回答不对都会回复是比这个数大还是比这个数小，然后规定在有限的次数中猜出这个数，否则就算失败。菜鸟的猜法，是先猜一个比较小的数，然后慢慢把数往上提，这么做每次增加的大小不太好把握，在有限的次数下很容易猜小或者猜过了。

如果你是一个学过数据结构的高手，那么你就会采取这种策略，先猜一个较大的数，然后再猜一个比写的数小的数，这样就划定了一个范围，在这个范围内我们重复之前的操作，不断缩小这个范围，最后在有限的次数中便可以缩小锁定要猜的数。

有学过数据结构的同学会知道这被称为二分查找法，这我们在之后的学习中也会讲到，但是我们可以看出在这个查找的每个阶段我们都有两种结果需要去判断，这就很适合用树状结构来建模，而且这种树是一种很特殊的树状结构，也是我们这期要学习的内容，叫做二叉树。

二叉树是由n（n>=0）个结点组成的有序集合，集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。二叉树的五种形态如图1所示：

二叉树之所以说是特别的树，是因为有以下几种特点，区别于普通的树形结构：

1. 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。注意不是只有两棵子树，而是最多有。没有子树或者有一棵子树都是可以的。

2. 左子树和右子树是有顺序的，次序不能任意颠倒。就像人是双手、双脚，但显然左手、左脚和右手、右脚是不一样的，右手戴左手套、右脚穿左鞋都会极其别扭和难受。

3. 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。图2中，树1和树2是同一棵树，但它们却是不同的二叉树。就好像你一不小心，摔伤了手，伤的是左手还是右手，对你的生活影响度是完全不同的。

其中，在普通二叉树的基础上，进一步发展出了满二叉树和完全二叉树，如图3所示：

在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。满二叉树的特点有：

1. 叶子只能出现在最下一层。出现在其它层就不可能达成平衡。

2. 非叶子结点的度一定是2。

3. 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

对一颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。就是保证叶子节点的上面层都要达到最大，最低下两层，最后一层的叶子节点都靠左排列，如图4所示：

完全二叉树的特点有：

1. 同样结点数的二叉树，完全二叉树的高度最小。

2. 完全二叉树的叶子结点仅出现在最下边两层，并且最底层的叶子结点一定出现在左边，倒数第二层的叶子结点一定出现在右边。

3. 完全二叉树中度为1的结点只有左孩子。

但不管是普通二叉树、满二叉树、完全二叉树，都满足以下的数学特性：

1. 在二叉树的第i层上最多有2^(i-1)个结点（i>=1）。

2. 高度为k的二叉树，最多有2^k-1个结点（k>=0）。

3. 对任何一棵二叉树，如果其叶结点有n个，度为2的非叶子结点有m个，则n = m + 1。

4. 具有n个结点的完全二叉树的高度为logn + 1

5. 对于有n个结点的完全二叉树，按层次对结点进行编号（从上到下，从左到右），对于任意编号为i的结点有：

如果i=1，则结点i是二叉树的根。

如果i>1，则其双亲结点为⌊i/2⌋。

如果2i<=n，则结点i的左孩子为2i。

如果2i>n，则结点i无左孩子。

如果2i+1<=n，则结点i的右孩子为2i+1。

如果2i+1>n，则结点i无右孩子。

讲完了二叉树的一些数学上的抽象概念和特性，我们来看一下这样一种特殊的树形结构在计算机中的存储实现。前面我们谈到了树的存储结构，并提到顺序存储对数这种一对多的数据结构实现起来是比较困难的。所以对于二叉树，我们也更多地考虑链式存储结构。二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，包含三个固定的成员：结点的数据域、指向左子结点的指针域、指向右子结点的指针域，我们称这样的链表叫做二叉链表。结点结构图如图5所示。

图5

其中data是数据域，lchild和rchild都是指针域，分别存放指向左孩子和右孩子的指针。

在对二叉树有了一定的了解后，我们来看代码。

这期主要还是注重对二叉树知识的了解，明白二叉树的结构和特点，二叉树的链式存储结构描述代码也很简单，记住设计一个数据域和两个孩子指针域，很容易就可以记忆。