3.6 树

树结构是非线性的，数据元素之间存在明显的层次和嵌套关系。树可分为一般树和分支固定的树，如二叉树、四叉树和八叉树。

3.6.1 树的逻辑结构

树（Tree）是由 n （ n ≥0）个结点组成的有限集 T ，结点之间呈现明显的层次关系，处于最高层次的结点称为该集合构成的树的根。除了根节点以外，其余结点可分为若干个互不相交的有限集 T ₁ ， T ₂ ， T ₃ ，…， T _m （ n ＞1, m ≥0），每一个集合本身又是一棵树，称为根的子树。可见，树结构是一个递归定义。

树的形式化定义为

T ={ V , R }

其中， V ={ x | x∈dataobject } R ={（ x , y ）| p （ x , y ）∧（ x , y∈V ）}。

V 是结点的非空有限集合， R 是两个顶点之间的关系集合， p （ x , y ）表示从顶点 x 到顶点 y 的一条直接通路。

结合图3-18所示的树结构，介绍以下树的基本术语。

1）根结点：没有直接前趋的结点，A为根结点。除根结点外，每个结点有且仅有一个直接前趋。

2）结点的度：结点的孩子（子树）的数量称为度。如结点B的度为4。

3）树的度：树中所有结点中最大的度数称为这个树的度数。本树的度为4。

4）分支结点：度不为0的结点，或者有直接后继的结点，如结点B, F, D, J。每个分支结点可以有不止一个直接后继。

5）叶结点：没有直接后继的结点，或者说度为0的结点。如结点E, K, G, H, C, I, L都是叶结节，也称终端结点。

6）双亲：结点的直接前趋称为该结点的双亲。如A是B的双亲。

7）孩子：结点的直接后继称为该结点的孩子。如B是A的孩子。

8）兄弟：相同双亲的孩子称为兄弟。如E, F, G, H。

9）堂兄弟：双亲在同一层的结点互为堂兄弟。如G与I, J互为堂兄弟。

10）深度：树的最大层次数量为树的深度或高度，图3-18所示的树深度为4。

11）祖先：从根到结点所经的所有结点都是该结点的祖先。如结点L的祖先是A, D, J结点。

12）子孙：以该结点为根的子树中任一结点都是该结点的子孙。如I, J, L是D的子孙，结点A的子孙则是树中其余的11个结点。

13）边：结点间的连线。

3.6.2 树的存储结构

由于树的逻辑结构为非线性，所以可用链式存储结构，可采用定长或不定长两种树的结点形式。

1.定长方式

以最大度数结点的结构作为该树所有结点的结构，如图3-19a所示，每个结点都有 n 个子树域。图3-19b所示的树用定长结点作为它的存储结构时，如图3-19c所示。

2.不定长方式

每个结点增加一个存放度数的域，结点长度随着度数不同而不同，如图3-20a所示。图3-19b所示树采用不定长结点表示时如图3-20b所示。

在定长方式存储中，所有结点是同构的，运算方便，但会浪费一定空间。不定长方式存储中，可节省一些空间，但运算不方便。

3.6.3 二叉树的结构及应用

1.二叉树的逻辑结构

二叉树是树结构的一种，但不同于一般树结构，即每个结点至多有两棵子树，并有左右之分，不能颠倒。二叉树可以是空的，一般树则至少有一个结点。二叉树的五种基本形态如图3-21所示。

几种特殊的二叉树如下。

1）满二叉树：深度为 k 的有2 ^k -1个结点的二叉树，如图3-22a所示。

2）顺序二叉树：深度为 k 、结点为 n 的二叉树，它从1～ n 的标号如果与深度为 k 的满二叉树标号一致，就称该二叉树为顺序二叉树，如图3-22b所示。

3）完全二叉树：结点的度数为0或2的二叉树称为完全二叉树，如图3-22a和图3-22c所示。

2.二叉树的存储结构

对于满二叉树的存储结构，可采用顺序存储。如果 i =1，此结点是根结点；如果 i = k ，则 k /2是结点 i 的双亲结点，2 k 是 i 的左孩子，2 k +1是 i 的右孩子。这种存储结构的特点是节省空间，可以利用公式随机访问每个结点和它的双亲及左、右孩子，但不便于删除或插入，如图3-23所示。

对于一般二叉树，通常采用多重链表结构，每个结点设三个域：数据域存放结点的值，左子树域存放左子树的地址，右子树域存放右子树的地址，如图3-24所示。这种存储结构会浪费一些存储空间，但便于进行删除或插入运算。

树结构在计算机内的表示也隐含着一种确定的相对次序，树结构各子树之间的相对位置也是确定的，如果交换同一层次各子树的位置就构成了不同的树。

3.二叉树的遍历

遍历二叉树是指按一定规律访问二叉树的每个结点，每个结点访问一次且只访问一次。二叉树的遍历就是按一定规则将二叉树的所有结点排列成一个线性序列。二叉树是由根结点、左子树、右子树三个基本单元组成的，因此依次遍历这三部分信息就可以遍历整个二叉树了。

根据根结点、左子树、右子树三者不同的先后次序，有六种遍历二叉树的方案，遍历次序分别是根结点、左子树、右子树；根结点、右子树、左子树；左子树、根结点、右子树；右子树、根结点、左子树；左子树、右子树、根结点；右子树、左子树、根结点。

（1）先根遍历

先根遍历的次序是：先访问根结点，再访问左子树，最后访问右子树。对图3-25所示二叉树遍历的过程如图3-26所示。遍历结果为A, B, D, H, E, C, F, G, I。

（2）中根遍历

中根遍历的次序是：先访问左子树，再访问根结点，最后访问右子树。其遍历示意图如图3-27所示。遍历结果为D, H, B, E, A, F, C, I, G。

（3）后根遍历

后根遍历的次序是：先访问左子树，再访问右子树，最后访问根结点。其遍历示意图如图3-28所示。遍历结果为H, D, E, B, F, I, G, C, A。

4.树的二叉树表示

用二叉树表示一般树可以节省存储空间，一般树转换为二叉树的规则如下。

1）树的根结点为二叉树的根结点。

2）保留根结点的孩子（从左到右）中第一个孩子作为二叉树的左子树。

3）根结点的其余孩子作为该左子树的右子树（与左子树原属于兄弟关系，现变为父子关系）。

将图3-18所示的一般树转换为二叉树的过程如图3-29所示。

5.树的应用

（1）排序

排序就是将一组无序的数据以递增或递减的规律重新排列。用二叉树排序的过程分为两步：先构造这棵二叉树，然后对这棵二叉树进行遍历。例如对一组数据（ a ₁ , a ₂ , a ₃ ,…, a _{i -1} , a _i , a _{i +1} , …, a _n )按递增的规律排序。

1）构造二叉排序树。

每一个数据将对应二叉树的一个结点。该结点在二叉树上的位置确定方法为：第一个数据元素 a ₁ 作为这棵二叉树的根结点；若 a ₂ ＜ a ₁ ， a ₂ 作为 a ₁ 的左子树，否则作为 a ₁ 的右子树；第 i 个数据元素 a _i 首先同这棵二叉树的根结点比较，若 a _i ＜ a ₁ ，则 a _i 应位于 a ₁ 的左边，再同 a ₁ 的左子树结点比较，否则同 a ₁ 的右子树结点比较，以此类推，直到找到该数据元素的位置为止。

数组（10, 36, 45, 13, 26, 7, 12, 48）的二叉排序树如图3-30所示。

2）中根遍历二叉排序树。

按照上面的方法建立二叉树以后，用中根遍历方式遍历该二叉树。

图3-29所示的二叉树排序的结果是（7, 10, 12, 13, 26, 36, 45, 48）。

（2）三维立体造型的CSG树

CSG（Constructive Solid Geometry）几何体素构造法的基本思想是由一些比较简单的基本形体经过交、并、差运算形成一个复杂的形体。当用二叉树可以描述这一形成过程时，该二叉树称为CSG树。图3-31a给出了一个复杂形体的形成过程，该过程也可以用图3-31b所示的CSG树来描述。从图中可以看出，叶结点是构成这个复杂形体的各个简单形体，其余结点描述了左右子树的运算种类，经过三层两次运算，就得到了这个复杂形体。