树_概念

树

树(型)存储结构
一种非线性存储结构，存储的是具有“一对多”关系的数据元素的集合。
图 1 树的示例

树的结点

结点：
父结点（双亲结点）、子结点和兄弟结点：
树根结点（简称“根结点”）：
树根的判断依据为：如果一个结点没有父结点，那么这个结点就是整棵树的根结点。
叶子结点：

子树和空树

子树：
注意：单个结点也是一棵树，只不过根结点就是它本身。
图 1（A）中，结点 K、L、F 等都是树，且都是整棵树的子树。
知道了子树的概念后，树也可以这样定义：树是由根结点和若干棵子树构成的。
空树：如果集合本身为空，那么构成的树就被称为空树。空树中没有结点。
补充：在树结构中，对于具有同一个根结点的各个子树，相互之间不能有交集。如果有，就破坏了树的结构，不能算做是一棵树。

结点的度和层次

对于一个结点，拥有的子树数（结点有多少分支）称为结点的度（Degree）。
一棵树的度是树内各结点的度的最大值。
结点的层次：从一棵树的树根开始，树根所在层为第一层，根的孩子结点所在的层为第二层，依次类推。
一棵树的深度（高度）是树中结点所在的最大的层次。
如果两个结点的父结点虽不相同，但是它们的父结点处在同一层次上，那么这两个结点互为堂兄弟。

有序树和无序树

如果树中结点的子树从左到右看，谁在左边，谁在右边，是有规定的，这棵树称为有序树；反之称为无序树。
在有序树中，一个结点最左边的子树称为”第一个孩子”，最右边的称为”最后一个孩子”。

森林

由 m（m >= 0）个互不相交的树组成的集合被称为森林。
前面讲到，树可以理解为是由根结点和若干子树构成的，而这若干子树本身是一个森林，
所以，树还可以理解为是由根结点和森林组成的。用一个式子表示为：
Tree =（root,F）
其中，root 表示树的根结点，F 表示由 m（m >= 0）棵树组成的森林。

树的表示方法

图 1（A）表示树的方法外，还有其他表示方法：
图 2（A）是以嵌套的集合的形式表示的（集合之间绝不能相交，即图中任意两个圈不能相交）。
图 2（B）使用的是凹入表示法（了解即可），表示方式是：最长条为根结点，相同长度的表示在同一层次。
例如 B、C、D 长度相同，都为 A 的子结点，E 和 F 长度相同，为 B 的子结点，K 和 L 长度相同，为 E 的子结点，依此类推。

图2 树的表示形式

最常用的表示方法是使用广义表的方式。图 1（A）用广义表表示为：
(A , ( B ( E ( K , L ) , F ) , C ( G ) , D ( H ( M ) , I , J ) ) )

5.1、树和二叉树的定义
5.1.1、树的定义
树是一种非线性的数据结构,
它是由n个有限结点组成有层次关系的集合.

树具有以下特点，可以根据这些特点来判断一个数据结构是否是树
•每个结点具有0个或多个子结点
•每个子结点只有一个父结点
•没有前驱的结为根结点
•除了根结点外，每个子结点又可以由m棵不相关的子树组成