第 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的父结点，结点 2 、 3 、 4 是结点 1 的子结点，它们又是兄弟结点，同时结点 2 又是结点 5 、 6 的父结点。称从根结点到某个子结点所经过的所有结点为这个子结点的祖先。如结点 1 、 4 、 7 是结点 8的祖先。称以某个结点为根的子树中的任一结点都是该结点的子孙。如结点 7 、 8 、 9 都是结点 4 的子孙。 E. 定义一棵树的根结点的层次（ level ）为 1 ，其它结点的层次等于它的父结点层次加 1 。如结点 2 、 3 、 4 的层次为 2 ，结点 5 、 6 、7 的...
VIP
