1.1.6　树与二叉树

1.树的基本概念

树是一种简单的非线性结构，所有数据元素之间的关系具有明显的层次特性，如图1-1-15所示。有关树结构的基本术语如下：

①根结点与叶子结点：在树结构中，每个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点。在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点，没有后件的结点称为叶子结点。

②结点的度：在树结构中，一个结点所拥有的后件个数称为该结点的度。

③树的度：在树中，所有结点中最大的度称为树的度。

④树的深度：树的最大层次称为树的深度。在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。在树中，叶子结点没有子树。

树结构具有明显的层次关系，即树是一种层次结构。在树结构中，一般按如下原则分层：根结点在第1层。同一层上所有结点的所有子结点都在下一层。

2.二叉树及其基本性质

（1）二叉树的特点

①非空二叉树只有一个根结点。

②每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。

在二叉树中，每一个结点的度最大为2，即所有子树（左子树或右子树）也均为二叉树，而树结构中的每一个结点的度可以是任意的。另外，二叉树中的每一个结点的子树被明显地分为左子树与右子树。在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时，该结点即是叶子结点。

（2）二叉树的基本性质

【性质1】在二叉树的第k层上，最多有2k-1个结点。

在图1-1-16所示的二叉树上：

第一层上（i=1），有21-1=1个结点。

第二层上（i=2），有22-1=2个结点。

第三层上（i=3），有23-1=4个结点。

第四层上（i=4），有24-1=8个结点。

【性质2】深度为k的二叉树最多有2k-1个结点。

20+21+22+…+2k-1=2k-1

【性质3】在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个，如图1-1-17所示。

【性质4】具有n个结点的二叉树，其深度k至少为log2n+1，其中log2n表示取log2n的整数部分（见图1-1-18）。

（3）满二叉树与完全二叉树

满二叉树与完全二叉树是两种特殊形态的二叉树。

①满二叉树。所谓满二叉树是指，除最后一层外，每一层上的所有结点都有两个子结点，如图1-1-19所示。也就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点。

②完全二叉树。所谓完全二叉树是指，除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点，如图1-1-20所示。

更确切地说，如果从根结点起，对二叉树的结点自上而下、自左至右用自然数进行连续编号，则深度为m、且有n个结点的二叉树，当且仅当其每一个结点都与深度为m的满二叉树中编号从1～n的结点一一对应时，称为完全二叉树。

对于完全二叉树来说，叶子结点只可能在层次最大的两层上出现；对于任何一个结点，若其右分支下的子结点的最大层次为p，则其左分支下的子结点的最大层次为p或p+l。

满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。

【性质5】具有n个结点的完全二叉树的深度为log2n+1。

【性质6】设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，…，n给结点进行编号，则对于编号为k（k=1，2，…，n）的结点有以下结论：

①若k=1，则该结点为根结点，它没有父结点；若k＞1，则该结点的父结点编号为INT（k/2）。

②若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（也无右子结点）。

③若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。

（4）树与二叉树的区别

①树和二叉树的结点个数最少都可为0。

②树中结点的最大度数没有限制，二叉树结点最大度数为2。

③树的结点无左、右之分，二叉树的结点子树有明确的左、右之分。

3.二叉树的存储结构

在计算机中，二叉树通常采用链式存储结构。与线性链表类似，用于存储二叉树中各元素的存储结点也由两部分组成：数据域与指针域。但在二叉树中，由于每一个元素可以有两个后件（即两个子结点），因此，用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域。由于二叉树的存储结构中每一个存储结点有两个指针域，因此，二叉树的链式存储结构又称二叉链表。

4.二叉树的遍历

二叉树的遍历是指不重复地访问二叉树中的所有结点。

由于二叉树是一种非线性结构，因此，对二叉树的遍历要比线性表的遍历复杂得多。在遍历二叉树的过程中，当访问到某个结点时，再往下访问可能有两个分支，那么先访问哪一个分支呢？对于二叉树来说，需要访问根结点、左子树上的所有结点、右子树上的所有结点，在这三者中，究竟先访问哪一个？也就是说，遍历二叉树的方法实际上是要确定访问各结点的顺序，以便不重不漏地访问到二叉树中的所有结点。

在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历。下面分别介绍这三种遍历的方法。

（1）前序遍历（根左右DLR）

所谓前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。因此，前序遍历二叉树的过程是一个递归的过程。

非空二叉树前序遍历的简单描述：访问根结点、前序遍历左子树、前序遍历右子树。

（2）中序遍历（左根右LDR）

所谓中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。因此，中序遍历二叉树的过程也是一个递归的过程。

非空二叉树中序遍历的简单描述：中序遍历左子树、访问根结点、中序遍历右子树。

（3）后序遍历（左右根LRD）

所谓后序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点；并且在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。因此，后序遍历二叉树的过程也是一个递归的过程。

非空二叉树后序遍历的简单描述：后序遍历左子树、后序遍历右子树、访问根结点。

【例1-1-8】用图1-1-21所示的二叉树写出三种遍历的遍历结果。

①前序遍历：根→左子树→右子树。

遍历过程如下：

根据以上遍历过程，前序遍历结果为ABDEGHIJCLF。

②中序遍历：左子树→根→右子树。

遍历过程同前序遍历（略）。

下面介绍中序遍历的一种投影遍历过程，如图1-1-22所示。

根据以上遍历过程，中序遍历结果为DBGEIHJALCF。

③后序遍历：左子树→右子树→根。

遍历过程同前序遍历（略）。

根据后序遍历方法，后序遍历结果为DGIJHEBLFCA。

【例1-1-9】根据三种遍历的两种遍历求第三种遍历结果。

已知一棵二叉树的前序遍历是ABDEGHIJCLF，中序遍历是DBGEIHJALCF，则该二叉树的后序遍历是什么？

分析：

①根据前序遍历找出二叉树（或子树）的根（前序遍历的第一个结点或后序遍历的最后一个结点）。

②根据中序遍历找出根的左右子树。

③重复①②步骤，直到完成建树的整个过程。

建树过程如下：

续表

综合以上建树步骤所述，最终所得到的二叉树如图1-1-23所示。

则该二叉树的后序遍历为DGIJHEBLFCA。