数据结构：树的定义及其性质

树的定义

树是一种重要的非线性数据结构，树作为一种逻辑结构，同时也是一种分层结构。具有以下两个特点：

1.树的根结点没有前驱，除根结点意外的节点只有一个前驱

2.树中所有结点都可以有0个或多个后继

树结构在多个领域都有广泛应用，如表示文件系统的结构、数据库的索引、层次数据关系等。

具体来说，树是由n（n≥0）个节点组成的有限集合。当n=0时，称为空树；当n>0时，为非空树。在非空树中，有且仅有一个特定的节点被称为根（root），其余节点可分为m（m>0）个互不相交的有限集T1, T2, …, Tm，其中每一个集合本身又是一棵树，并且被称为根的子树（Subtree）。

树的基本术语

1. 节点（Node）：包含一个数据元素及若干指向其子树的分支。在树中，每个节点都代表一个实体，如文件系统中的文件或目录。

2. 结点的度（Degree of a Node）：一个节点拥有的子树数目。例如，一个节点如果有两个子节点，则它的度为2。

3. 树的度（Degree of a Tree）：树中所有节点度的最大值。这表示树中最“繁忙”的节点有多少个直接子节点。

4. 叶子节点（Leaf Node）：度为零的节点，也称为终端节点。在树的最底层，没有子节点的节点都是叶子节点。

5. 分支节点（Branch Node）：度大于零的节点，也称为非终端节点。这些节点在树中起到连接其他节点的作用。

6. 路径（Path）：由从根节点到某一节点所经分支和节点构成的序列。

7. 路径的长度：是路径上边的数量。

8. 孩子节点（Child Node）：节点的子树的根称为该节点的孩子节点。例如，在文件系统中，一个目录下的文件和子目录都是该目录的孩子节点。

9. 双亲节点（Parent Node）：相应地，一个节点的直接前驱节点称为该节点的双亲节点。在文件系统中，一个目录的上级目录就是该目录的双亲节点。

10. 兄弟节点（Sibling Node）：具有同一父节点的各个节点彼此是兄弟节点。在文件系统中，同一目录下的文件和子目录互为兄弟节点。

11. 祖先节点（Ancestor Node）：从根节点到某一节点路径上的所有节点都是这个节点的祖先节点。在文件系统中，从根目录到某个文件或目录路径上的所有目录都是该文件或目录的祖先节点。

12. 子孙节点（Descendant Node）：以某节点为根的子树中任一节点都称为该节点的子孙节点。在文件系统中，一个目录下的所有文件和子目录（以及子目录的子目录等）都是该目录的子孙节点。

13. 节点的层次（Level of a Node）：从根节点到该节点所经过的路径长度加1。根节点位于第1层。

14. 树的深度（Depth of a Tree）：树中叶子节点具有的最大层次数。这表示从根节点到最远叶子节点的最长路径上的节点数。

15. 树的宽度（Width of a Tree）：整棵树中某一层中最多的节点数。这表示树在该层上的“宽度”。

16. 有序树（Ordered Tree）：如果将树中节点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树。与之相对的是无序树，其中子树的顺序不重要。

树的性质可以从多个方面来阐述，以下是一些主要的性质：

一、基本性质

1. 递归定义：树是n(n≥0)个节点的有限集合，当n=0时称为空树。在非空树中，有且仅有一个特定的称为根的节点，其余节点可分为m(m>0)个互不相交的有限集合，每个集合本身又是一棵树，并称为根的子树。这种定义是递归的。

2. 节点关系：

   • 根节点没有前驱节点，除根节点外的所有节点有且只有一个前驱节点。
   • 树中所有节点可以有零个或多个后继节点（即子节点）。

3. 层次结构：树具有层级结构，从根节点开始，根节点为第一层，根节点的子节点为第二层，以此类推。节点的层次从根开始定义，根节点为第1层（有些教材从0开始）。

4. 路径与路径长度：路径是由树中的两个节点之间的节点序列构成的，而路径长度是路径上所经过的边的个数。

二、节点与树的属性

1. 节点的度：一个节点拥有的子树数目称为该节点的度。树中节点的最大度数称为树的度。

2. 叶子节点与分支节点：度为零的节点称为叶子节点（终端节点），度大于零的节点称为分支节点（非终端节点）。

3. 节点的高度与深度：节点的高度是从该节点到其最远叶子节点的最长路径上的节点数（即从下往上数）。节点的深度是从根节点到该节点的路径长度（即从上往下数）。树的高度（深度）是树中节点的最大层次数。

三、特殊树的性质

1. 二叉树：二叉树是每个节点最多有两个子树的树结构。二叉树具有一些特殊的性质，如满二叉树、完全二叉树等。

2. m叉树：

• m叉树是每个节点最多有m个子树的树结构。对于高度为h的m叉树，其节点数至多为(m^h - 1) / (m - 1)，至少为h（每层只有一个节点）或h+m-1（只有一个分支节点有m个孩子）。
• 第i层至多有m^(i-1)个结点。

四、其他性质

1. 结点数与度数关系：树中的结点数等于所有节点的度数之和加1。这是因为每个非根节点都有一个前驱节点（即其父节点），而根节点没有前驱节点，所以总度数加1就等于结点数。

2. 有序树与无序树：树中节点的各子树从左到右是有次序的，不能交换，称该树为有序树；否则称为无序树。

3. 森林：m(m≥0)棵互不相交的树的集合称为森林。森林可以看作是由多棵树组成的集合。

最小高度分析：

度为m，具有n个结点的树的最小高度h：

度为m，具有n个结点的树的最大高度h：n-m+1