树的基本概念

树的定义

​ 树是 n( n >= 0 )个节点有限集。当 n = 0时，称为空树。在任意一颗非空树中应该满足：

​ 1）有且仅有一个特定的称为根的节点。

​ 2）当 n >1时，其余节点可分为 m (m > 0)个互不相交的有限集合T1，T2 ···，Tm，其中每个集合本身又是一棵树，并且称为根的子树。

​ 显然，树的定义是递归的，即在树的定义中又用到了其自身，树是一种递归结构，树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

​ 1）树的根结点没有前驱，除根结点外的所有节点有且只有一个前驱。

​ 2）树中所有结点可以有零个或多个后继。

​ 树适合于表示具有层次结构的数据。树中的某个结点（除根结点外）最多只和一个上一层的一个结点（即其父节点）有直接关系，根节点没有直接上层结点，因此，**n个节点的树中有n-1条边。**而树中每个结点与其下一层的零个或多个结点（即其子女结点）有直接关系。

基本术语

• 考虑结点K。根A到结点K唯一路径上的任意结点，称为结点K的祖先。如结点B是结点K的祖先。而结点K是结点B的子孙。路径上最接近结点K的结点E称为K的双亲,而K为结点E的孩子。根A是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟，如结点K和结点L有相同的双亲E，即K和L为兄弟。

• 树中一个结点的孩子个数称为改结点的度， 树中结点的最大度数称为数的度。如结点B的度为2，结点D的度为3，数的度为3。

• 度大于0的结点称为分支节点（又称非终端节点）：度为0（没有子女结点）的节点称为叶子结点（又称终端节点）。在分支结点中，每个结点的分支数就是该结点的度。

• 结点的深度，高度和层次。结点的层次从树根结点开始定义，根结点为第1层，它的子结点为第2层，以此类推。双亲在同一层的结点互为堂兄弟，如图中结点G与E，F，H，I，J互为堂兄弟。

  • 结点的深度是从根节点开始自顶向下逐层累加的。
  • 结点的高度是从叶节点开始自底向上逐层累加的。
  • 数的高度（或深度）是树中结点的最大层数。图中树的高度为4。

• 有序树和无序树。树种结点的个子树从左到右是有次序的，不能互换，称该数为有序树，否则为无序树。假设上图为有序树，若将子结点位置互换，则变成一颗不同的树。

• 路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。

注意：由于树中的分支是有向的，即从双亲指向孩子，所以树中的路径是从上向下的，同一双亲的两个孩子之间不存在路径。

• 森林。森林是m (m >= 0)棵互不相交的树的集合。森林的概念与树的概念是否相近，因为只要把树的根节点删去就成了森林，反正，只有给m棵独立的树假设一个结点，并把这m棵树作为该结点的子树，森林就变成了树。

树的性质

数据有以下最基本的性质：

1. 树中的结点树等于所有节点的度数加1.**
2. 度为m的树中第 i 层上至多有 m ^ (i -1) 个结点（i >=1 )
3. 高度为 h 的 m叉树至多有（m ^ h - 1)* (m - 1)个结点。
   4. 具有 n 个结点的 m 叉树的最小高度为 ⌈log m (n*(m-1)+1)⌉。

部分摘抄自王道考研-数据结构