树的定义

之前我们一直谈的是一对一的线性结构，可现实中，还有很多一对多的情况需要处理，所以我们要研究这种一对多的数据结构——“ 树 ”。

树（Tree）是 n (n >= 0)个结点的有限集。 n = 0 时称为空树， 在任何一棵非空树中：

1. 有且仅有一个特定的称为根（Root）的结点；
2. 当 n > 1 时，其余结点可分为 m ( m > 0) 个互不相的有限集 T₁ 、T₂、……、T_m，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree），如图所示。
   

树的定义强调两点：

1. n>0 时根结点是唯一的，不可能存在多个根结点。
2. m>0 时，子树的个数没有限制，但它们一定是互补相交的。

错误示范：

结点分类

• 结点定义：树的结点包含一个数据元素及若干指向其子树的分枝。
• 度的定义：结点拥有的子树数称为结点的度（degree），树的度是树内各结点的度的最大值。
• 叶结点：度为 0 的结点称为叶结点（Leaf）或终端结点；
• 分支结点：度不为 0 的结点称为非终端结点或分支结点。分支结点也称为内部结点。

结点间关系

• 孩子（Child）/双亲（Parent）：结点的子树的根称为该结点的孩子，相应的该结点称为孩子的双亲（Parent），
• 兄弟（Sibling）: 同一个双亲的孩子之间称为兄弟。
• 祖先： 结点的祖先是从根到该结点所经分支上的所有结点。反之，以某个结点为根的子树中的任一结点都称为该结点的子孙。
  

树的其他相关概念

• 结点的层次（Level ）：从根开始定义起，根为第一层，根的孩子为第二层。树中结点的最大层次称为树的深度（Depth）或高度。
• 有序树/ 无序树： 如果将树中各结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。
• 森林（Forest）：是 m (m >= 0)棵互不相交的树的集合，对于树中每个结点而言，其子树的集合即为森林。

对于线性表与树的结构，它们有很大的不同。

树的抽象数据类型