第6章 二叉树

6.1 二叉树基础知识

二叉树（Binary Tree）也称为二分树、二元树、对分树等，它是n（n≥0）个有限元素的集合，该集合或者为空，或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。

在二叉树中，一个元素也称作一个结点。二叉树的递归定义为：二叉树或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的分别称作根结点的左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二叉树。

以下是二叉树的一些常见的基本概念：

1）结点的度：结点所拥有的子树的个数称为该结点的度。

2）叶结点：度为0的结点称为叶结点，或者称为终端结点。

3）分支结点：度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结点外，其余的都是分支结点。

4）左孩子、右孩子、双亲：树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。

5）路径、路径长度：如果一棵树的一串结点n1,n2,…,nk有如下关系：结点ni是ni+1的父结点（1≤i＜k），就把n1,n2,…,nk称为一条由n1～nk的路径。这条路径的长度是k-1。

6）祖先、子孙：在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。

7）结点的层数：规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。

8）树的深度：树中所有结点的最大层数称为树的深度。

9）树的度：树中各结点度的最大值称为该树的度，叶子结点的度为0。

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

11）完全二叉树：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。

二叉树的基本性质如下：

性质1：一棵非空二叉树的第i层上最多有2^i-1个结点（i≥1）。

性质2：一棵深度为k的二叉树中，最多具有2^k-1个结点，最少有k个结点。

性质3：对于一棵非空的二叉树，度为0的结点（即叶子结点）总是比度为2的结点多一个，即如果叶子结点数为n0，度数为2的结点数为n2，则有n0=n2+1。

证明：用n0表示度为0（叶子结点）的结点总数，用n1表示度为1的结点总数，n2表示度为2的结点总数，n表示整个完全二叉树的结点总数。则n=n0+n1+n2，根据二叉树和树的性质，可知n=n1+2×n2+1 （所有结点的度数之和+1=结点总数），根据两个等式可知n0+n1+n2=n1+2×n2+1，所以，n2=n0-1，即n0=n2+1。所以，答案为1。

性质4：具有n个结点的完全二叉树的深度为「log₂n」+1。

证明：根据性质2，深度为k的二叉树最多只有2^k-1个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数n位于k层和k-1层满二叉树容量之间，即2^k-1＜n≤2^k-1或2^k-1＜n≤2^k，不等式的三部分同时取对数，于是有k-1≤log₂n＜k，因为k是整数，所以，k=「log₂n」+1。

性质5：对于具有n 个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有：①如果i＞1，则序号为i的结点的双亲结点的序号为i/2（其中“/”表示整除）；如果i=1，则序号为i的结点是根结点，无双亲结点。②如果2i≤n，则序号为i的结点的左孩子结点的序号为2i；如果2i＞n，则序号为i的结点无左孩子。③如果2i+1≤n，则序号为i的结点的右孩子结点的序号为2i+1；如果2i+1＞n，则序号为i的结点无右孩子。

此外，若对二叉树的根结点从0开始编号，则相应的i号结点的双亲结点的编号为（i-1）/2，左孩子的编号为2i+1，右孩子的编号为2i+2。

例题1：一棵完全二叉树上有1001个结点，其中叶子结点的个数是多少？

分析：二叉树的公式：n=n0+n1+n2=n0+n1+（n0-1）=2×n0+n1-1。而在完全二叉树中，n1只能取0或1。若n1=1，则2×n0=1001，可推出n0为小数，不符合题意；若n1=0，则2×n0-1=1001，则n0=501。所以，答案为501。

例题2：如果根的层次为1，具有61个结点的完全二叉树的高度为多少？

分析：根据二叉树的性质，具有n个结点的完全二叉树的深度为㊣㊣log2n㊣㊣+1，因此，含有61个结点的完全二叉树的高度为6层。所以，答案为6。

例题3：在具有100个结点的树中，其边的数目为多少？

分析：在一棵树中，除了根结点之外，每一个结点都有一条入边，因此，总边数应该是100-1，即99条。所以，答案为99。

下面是一个用PHP构造二叉树的方法：

6.2 如何实现二叉树

难度系数：★★★★☆

被考查系数：★★★☆☆

分析与解答：

方法一：用数组构造简单的二叉树

使用数组构造一个二叉树，将二叉树的每个结点存储到数组中，往数组添加结点时，需要指定将该结点存放在左子树还是右子树。初始化时，创建一个指定长度的二叉树，并设置数组的第一个值为根结点。

以自然数数组（0, 1, 2,…, 10）为例，实现代码如下：

程序的运行结果为

方法二：用链表结构构造二叉树

先构造一个链表结构，在链表中构造出根结点、左子树和右子树的结构。构造一棵二叉树的方法：链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。其结点结构：lchild、data、rchild。

实现代码如下：

程序的运行结果为

以上两种方法中，方法一简单直接明了，但只能线性结构的展示二叉树，不能对二叉树进行前序排序、中序排序或后序排序。而方法二更接近二叉树的结构，可以对二叉树进行前序、中序、后序的遍历，更具有结构性，更像二叉树。所以要实现一个二叉树结构的方法更推荐使用方法二。

6.3 如何用树结构实现多层级分类

难度系数：★★★☆☆

被考查系数：★★★★☆

题目描述：

假设存在以下一个省市区结构的数组，需要按多层级结构排序输出，请使用PHP代码实现该功能。

分析与解答：

方法一：非递归，通过引用实现多层级结构排序

通过题目的$items数组结构知道，pid为0的是父级分类，pid大于0的数组是等于对应id值下的子分类。可以把pid=0的分类认为是根结点，pid=id的认为是该根下的子树，所以可以在每个结点用一个son 字段存储对应结点下的子树。对数组进行遍历时，可以利用引用的方法，将每个分类添加到父类的一个son 字段中，而son 字段存储的是子树数组，一次遍历就可以实现层级树的结构排序返回结果。

实现代码如下：

方法二：递归实现多层级结构排序

通过对数组遍历，找到父结点，再对父结点下的数组递归遍历找到子结点，然后存到父结点的son数组中，再把排序好的多层级结构返回。

实现代码如下：

由于以上程序运行结果较长，这里暂不罗列。

方法一通过引用的方法构造数组，只需要一次遍历就可以把生成的层级关系返回。而方法二需要多次递归遍历找到子结点给到父结点才能得到层级结构。对比方法一和方法二，方法一的执行效率比方法二更高。

6.4 如何找到二叉树中的最大最小值

难度系数：★★★★☆

被考查系数：★★★★☆

题目描述：

在日常的开发中经常需要从数据集合中找出最大值和最小值，现要求编程实现从一个二叉树中找出最大值和最小值。

分析与解答：

在初始化一棵二叉树时，每次将插入的结点和父结点进行对比，比父结点小的子结点插到左子树中，比父结点大的子结点插到右子树中。当需要查找最小值时从左子树中递归查找，当需要查找最大值时从右子树中递归查找。

例如：存在一个数组结构为831016144713，需要从中找出最大值和最小值。

1）查找最小值：

构造一棵二叉树，8为根结点，存在左子树和右子树，当插入3的时候，由于3小于8，因此把3插入到8的左子树中。在插入到左子树时还需要判断左子树是否已存在结点，如果为空结点则直接插入即可点，否则需要将左子树的根结点与新结点对比，若根结点大于待插入的值，则直接插入到左子树中，否则插入到右子树。需要注意的是：如果父结点与子结点相等，那么不用插入或做其他操作。初始化对比判断过程如下图所示。

经多次遍历对比后，得到的结果如下图所示。

这样保证了左子树永远存在的是最小值，求最小值时，对左子树遍历，判断父结点下的左子树是否存在结点，若不存在结点则该父结点就是最小值。

2）查找最大值：

与查找左子树同理，在最初插入结点时已经将每个根结点和新结点进行了对比，保证了插入到右子树的结点都是最大值。当要求出最大值时，只需对右子树进行遍历，判断父结点下的右子树是否存在结点，若不存在结点则该父结点就是最大值。实现代码如下：

程序的运行结果为

求最小值时，需要对左子树进行多次递归判断，判断左子树的根结点是否还有左孩子，如果没有则该结点就是最小值，否则需要继续遍历下去。求最大值时同理，对右子树递归判断右孩子时，如果右孩子下面没有子结点则该结点就是最大值，否则需要继续遍历右结点下的结点，直至找到右子树的最后一个右结点。

6.5 如何对二叉树进行遍历

难度系数：★★★★☆

被考查系数：★★★★☆

分析与解答：

方法一：使用前序遍历二叉树

前序遍历的步骤如下：

若二叉树非空，则依次执行如下操作：

1）访问根结点。

2）遍历左子树。

3）遍历右子树。

实现代码如下：

方法二：使用中序遍历二叉树

中序遍历的步骤如下：

若二叉树非空，则依次执行如下操作：

1）遍历左子树。

2）访问根结点。

3）遍历右子树。

实现代码如下：

方法三：使用后序遍历二叉树

中序遍历的步骤如下：

若二叉树非空，则依次执行如下操作：

1）遍历左子树。

2）遍历右子树。

3）访问根结点。

实现代码如下：

方法四：层序遍历

层序遍历的步骤如下：

1）二叉树的根结点所在层数为1，层序遍历就是从所在二叉树的根结点出发。

2）首先访问第一层的树根结点，然后从左到右访问第2层上的节点。

3）接着是第3层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

实现代码如下：

6.6 如何判断一棵二叉树是否是完全二叉树

难度系数：★★★★☆

被考查系数：★★★★☆

题目描述：

若设二叉树的深度为h，除第h 层外，其他各层 （1～h-1） 的结点数都达到最大个数，第h 层所有的结点都连续集中在最左边，叫做完全二叉树。现请编程判断一个二叉树结构是否是完全二叉树。

分析与解答：

可以使用层序遍历，通过以下条件判断一个二叉树结构是不是完全二叉树：

1）遍历到的结点只有右子树没有左子树的二叉树不是完全二叉树。

2）如果遍历到一个结点只有左子树，那么后面遍历到的结点必须是叶子结点（即没有子结点的结点），否则也不是完全二叉树。

3）除最后一层之外，其他各层只要有一层的结点数没能达到最大个数，那么就不是完全二叉树。

4）不满足1）、2）的二叉树，可以认为该二叉树是完全二叉树。

实现代码如下：

程序的运行结果为

由于在创建该二叉树时，新增结点比父结点及后续父结点小的都放到该父结点的左子树中，新增结点及后续结点比父结点大的都放到该父结点的右结点下，所以该二叉树的结构如下图所示。

最终求解出该树是完全二叉树。需要注意的是，一棵树是满二叉树则该树一定是完全二叉树，但一棵树是完全二叉树，不一定是满二叉树。