第 5 节 树 前两章学习的栈和队列属于线性结构
在这种结构中，数据元素的逻辑位置之间呈线性关系，每一个数据元素通常只有一个前件（除第一个元素外）和一个后件（除最后一个元素外）
在实际生活中，可以用线性结构描述数据元素之间逻辑关系的问题是很广泛的，但也有很多问题不能依靠线性结构来解决，例如家谱、行政组织机构等都是非线性的数据结构
其中树就是一种非线性的数据结构
一、树的定义 一棵树是由 n （ n>0 ）个元素组成的有限集合，其中：（ 1 ）每个元素称为结点 (node) ；（ 2 ）有一个特定的结点，称为根结点或树根（ root ）；（ 3 ）除根结点外，其余结点能分成 m （ m>=0 ）个互不相交的有限集合 T0,T1,T2,……Tm-1
其中的每个子集又都是一棵树，这些集合称为这棵树的子树
如下图是一棵典型的树：二、树的基本概念•树是递归定义的；•一棵树中至少有 1 个结点
这个结点就是根结点，它没有前驱，其余每个结点都有唯一的一个前驱结点
每个结点可以有 0 或多个后继结点
因此树虽然是非线性结构，但也是有序结构
至于前驱后继结点是哪个，还要看树的遍历方法，我们将在后面讨论；•一个结点的子树个数，称为这个结点的度（ degree ，结点 1 的度为 3 ，结点 3 的度为 0 ）；度为 0 的结点称为叶结点（树叶 leaf ，如结点3 、 5 、 6 、 8 、 9 ）；度不为 0 的结点称为分支结点（如结点1 、 2 、 4 、 7 ）；根以外的分支结点又称为内部结点（结点 2 、 4 、 7）；树中各结点的度的最大值称为这棵树的度（这棵树的度为 3 ）
•在用图形表示的树型结构中，对两个用线段（称为树枝）连接的相关联的结点，称上端结点为下端结点的父结点，称下端结点为上端结点的子结点
称同一个父结点的多个子结点为兄弟结点
如结点 1 是结点 2 、 3 、 4的
