树的应用 —— 树的简介

树的应用 —— 树的简介

【什么是树】

树（Tree）是n （n ≥0）个节点的有限集合，当n = 0时，为空树；当n > 0 时，为非空树。

任意一棵非空树，都满足：

① 有且仅有一个被称为根的节点；
② 除根节点外的其余节点可分为m （m ＞0）个互不相交的有限集T 1 , T 2 , …, Tm ，其中每一个集合本身又是一棵树，被称为根的子树（SubTree）。

【举个栗子】

一棵树如下图所示。该树除了树根，还有3棵互不相交的子树：T1、T2 、T3 。

该定义是从集合论的角度给出的对树的递归定义，即把树的节点看作一个集合，除了树根，其余节点被分为m 个互不相交的集合，每一个集合又都是一棵树。

【树的相关术语】

• 节点：节点包含数据元素及若干指向子树的分支信息。
• 节点的度：节点拥有的子树个数。
• 树的度：树中节点的最大度数。
• 终端节点：度为0的节点，又被称为叶子。
• 分支节点：度大于0的节点。除了叶子，都是分支节点。
• 内部节点：除了树根和叶子，都是内部节点。

[举个栗子]

一棵树如下图所示，该树的度为3，其内部节点和终端节点均用虚线圈起来。

• 节点的层次：从根到该节点的层数（根节点为第1层）。
• 树的深度（或高度）：所有节点中最大的层数。

[举个栗子]

一棵树如下图所示，根为第1层，根的子节点为第2层……该树的最大层次为4，因此树的深度为4。

• 路径：树中两个节点之间所经过的节点序列。
• 路径长度：两个节点之间路径上经过的边数。

[举个栗子]

一棵树如下图所示，D到A的路径为D-B-A，D到A的路径长度为2。由于树中没有环，因此树中任意两个节点之间的路径都是唯一的。

如果把树看作一个族谱，就成了一棵家族树，如下图所示。

• 双亲、孩子：节点的子树的根被称为该节点的孩子，反之，该节点为其孩子的双亲。
• 兄弟：双亲相同的节点互称兄弟。
• 堂兄弟：双亲是兄弟的节点互称堂兄弟。
• 祖先：即从该节点到树根经过的所有节点，被称为该节点的祖先。
• 子孙：节点的子树中的所有节点都被称为该节点的子孙。

[举个栗子]

祖先和子孙的关系。如下图所示，D的祖先为B、A，A的子孙为B、C、D、E、F、G。

• 有序树：节点的各子树从左至右有序，不能互换位置，如下图所示。

• 无序树：节点的各子树可以互换位置
• 森林：由m （m ≥0）棵不相交的树组成的集合。

[举个栗子]

上图中的树，删除树根A后，余下的3棵子树构成一个森林，如下图所示