2.7　树结构

树结构是一种日常生活中应用相当广泛的非线性结构，包括企业内的组织结构、家族的族谱、篮球赛程以及计算机领域中的操作系统与数据库管理系统都是树结构的衍生应用。如图2-46所示的是Windows的文件资源管理器的示意图，它就是以树结构来组织和存储各种文件的。

例如，在年轻人喜爱的大型网络游戏中，需要获取某些物体所在的地形信息，如果程序依次从构成地形的模型三角面寻找，往往会耗费许多运行时间，非常低效。因此，程序员一般会使用树形结构中的二叉空间分割树（Binary Space Partitioning Tree，BSP Tree）、四叉树（Quadtree）、八叉树（Octree）等来代表分割场景的数据。四叉树示意图如图2-47所示。地形与四叉树的对应关系如图2-48所示。

2.7.1　树的基本概念

“树”是由一个或一个以上的节点组成的，存在一个特殊的节点，称为树根（Root）。每个节点都是由一些数据和指针组合而成的记录。除了树根外，其余节点可分为n≥0个互斥的集合，即T ₁ ，T ₂ ，T ₃ ，…，T _n ，其中每一个子集合本身也是一个树结构，即此根节点的子树，如图2-49所示。

一棵合法的树，节点间可以互相连接，但不能形成无出口的回路，例如图2-50所示就是一棵不合法的树。

在树结构中，有许多常用的专有名词，这里将以图2-51中这棵合法的树来为大家详细介绍。

·度数（Degree）：每个节点所有子树的个数。例如图2-51中，节点B的度数为2，D的度数为3，F、K、I、J等的度数为0。

·层数（Level）：树的层数，假设树根A为第一层，B、C、D节点的层数为2，E、F、G、H、I、J的层数为3。

·高度（Height）：树的最大层数。图2-51所示的树的高度为4。

·树叶或称终端节点（Terminal Nodes）：度数为零的节点就是树叶。图2-51中的K、L、F、G、M、I、J就是树叶。图2-52中有4个树叶节点，即E、C、H、I。

·父节点（Parent）：一个节点连接的上一层节点。如图2-51所示，F的父节点为B，而B的父节点为A，通常在绘制树形图时，我们会将父节点画在子节点的上方。

·子节点（Children）：一个节点连接的下一层节点。如图2-51所示，A的子节点为B、C、D，而B的子节点为E、F。

·祖先（Ancestor）和子孙（Descendent）：所谓祖先，是指从树根到该节点路径上所包含的节点；而子孙则是从该节点往下追溯，子树中的任一节点。在图2-51中，K的祖先为A、B、E节点，H的祖先为A、D节点，B的子孙为E、F、K、L节点。

·兄弟节点（Sibling）：有共同父节点的节点。在图2-51中，B、C、D为兄弟节点，H、I、J也为兄弟节点。

·非终端节点（Nonterminal Node）：树叶以外的节点，如图2-51中的A、B、C、D、E、H。

·同代（Generation）：在同一棵树中具有相同层数的节点，如图2-51中的E、F、G、H、I、J或B、C、D。

·森林（Forest）：n（n≥0）棵互斥树的集合。将一棵大树移去树根即为森林。例如图2-53所示为包含三棵树的森林。

2.7.2　二叉树

一般树结构在计算机内存中的存储方式以链表（Linked List）为主。对于n叉树来说，每个节点的度数都不相同，当n=2时，它的链接浪费率最低。为了避免树结构空间浪费的缺点，所以我们最常使用二叉树（Binary Tree）结构来取代其他的树结构。

二叉树（又称为Knuth树）是一个由有限节点所组成的集合，此集合可以为空集合，或由一个树根及其左右两棵子树组成。简单地说，二叉树最多只能有两个子节点，就是度数小于或等于2。二叉树每个节点在计算机中的数据结构如图2-54所示。

二叉树和一般树的不同之处整理如下：

（1）树不可为空集合，而二叉树可以。

（2）树的度数为d≥0，而二叉树的节点度数为0≤d≤2。

（3）树的子树间没有次序关系，而二叉树有。

下面我们来看一棵实际的二叉树，如图2-55所示。

图2-55是以A为根节点的二叉树，包含以B、D为根节点的两棵互斥的左子树和右子树，如图2-56所示。

以上这两棵左右子树属于同一种树结构，不过却是两棵不同的二叉树，原因是二叉树必须考虑前后次序关系。这点大家要特别注意。

由于二叉树应用得相当广泛，因此衍生了许多特殊的二叉树结构。我们分别介绍如下：

1．满二叉树（Fully Binary Tree）

如果二叉树的高度为h（h≥0），树的节点数为2 ^h -1，我们就称此树为“满二叉树”，如图2-57所示：

2．完全二叉树（Complete Binary Tree）

完全二叉树的高度为h，所含的节点数小于2 ^h -1，但其节点的编号方式如同高度为h的满二叉树一样，从左到右、从上到下的顺序一一对应，如图2-58所示。

3．斜二叉树（Skewed Binary Tree）

当一个二叉树完全没有右节点或左节点时，我们就把它称为左斜二叉树或右斜二叉树，如图2-59所示。

4．严格二叉树（Strictly Binary Tree）

二叉树中的每一个非终端节点均有非空的左右子树，如图2-60所示。

2.7.3　树转化为二叉树的算法

对于将一般树结构转化为二叉树，使用的方法称为“Child-Sibling”（Leftmost-Child-Next-Right-Sibling，左儿子右兄弟表示法）法则。以下是其执行步骤：

（1）将节点的所有兄弟节点用横线连接起来。

（2）只保留与最左子节点的连接，删掉其他所有与子节点间的连接。

（3）右子树都顺时针旋转45度。

按照下面的范例实践一次，就可以有更清楚的认识。转化前的多叉树如图2-61所示。

步骤01 将树的各层兄弟用横线连接起来，如图2-62所示。

步骤02 只保留最左边的父子节点的连接，删掉其他所有子节点间的连接，如图2-63所示。

步骤03 右子树都顺时针旋转45度，如图2-64所示。

2.7.4　二叉树转化为树的算法

既然树可以转化为二叉树，当然也可以将二叉树转化为树（多叉树），如图2-65所示。

这其实就是树转化为二叉树的逆向步骤，方法也很简单。首先右子树都逆时针旋转45度，如图2-66所示。

左子树（ABE）（DG）代表父子关系，而右子树（BCD）（EF）（GH）代表兄弟关系，按这种父子关系增加连接，同时删除兄弟节点间的连接，结果如图2-67所示。