《计算思维与算法入门》 —2.7 树结构

2.7    树结构

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

图2-46  Windows的文件资源管理器就是以树结构来组织和存储各种文件的

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

图2-47  四叉树示意图

图2-48  地形与四叉树的对应关系

2.7.1  树的基本概念

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

图2-49  树结构的示意图

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

图2-50  不合法的树（因为节点间形成了无出口的回路）

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

图2-51  一棵合法的树

      度数（Degree）：每个节点所有子树的个数。例如图2-51中，节点Ｂ的度数为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的子节点为Ｅ、F。

图2-52  有4个树叶节点的树

      祖先（Ancestor）和子孙（Descendent）：所谓祖先，是指从树根到该节点路径上所包含的节点；而子孙则是从该节点往下追溯，子树中的任一节点。在图2-51中，K的祖先为A、B、E节点，Ｈ的祖先为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-53  森林