数据结构学习笔记(十七)——树的基本概念

1 树：由n(n≥0)个节点组成的有限集合（记为T）。如果n=0，表示为空树，这是树的特例；如果n＞0，这n个节点中存在（有且仅有）一个节点作为树的根节点，简称根(root)，其余为互不相交的有限集，每个子集本身又符合树的定义，称为根的子树。

2 树的特点

（1）每个节点可以有零个或多个后继节点，但有且仅有一个前驱节点（根节点除外）；

（2）这些数据节点按分支组织起来，清晰地反应了数据元素之间的层次关系。

3 基本运算：

（1）InitTree(&t)：初始化树

（2）DestroyTree(&t)：销毁树

（3）Parent(t)：求t所指节点的双亲节点

（4）Sons(t)：求t所指节点的子孙节点

4 树的逻辑表示方法：

（1）树形表示法：用一个圆圈表示一个节点，圆圈内的符号代表该节点的数据信息，节点之间的关系通过连线表示。

（2）文氏图表示法：每棵树对应一个圆圈，圆圈内包含根节点和子树的圆圈，同一个根节点下各个子树对应的圆圈不能相交。节点之间的关系是通过圆圈的包含关系来表示的。

（3）凹入表示法：每棵树的根对应着一个条形，子树的根对应着一个较短的条形，且树根在上，子树的根在下，同一根下的各个子树的根对应的条形长度一样。

（4）括号表示法：每棵树对应一个由根作为名字的表，表名放在表的左边，表是由在一个括号里的各子树对应的表组成的，各子树对应的表之间用逗号分开。节点之间的关系是通过括号的嵌套表示的。如:A(B(D,E),C(F))。

5 树的基本术语

（1）节点的度与树的度：树中某个节点的子树个数称为该节点的度。树中各节点的度的最大值称为树的度，通常将度为m的树称为m次树。

（2）分支节点与叶子节点：度不为零的节点称为非终端节点，又叫分支节点。度为零的节点称为终端节点或叶子节点。

（3）路径与路径长度：对于任意两个节点ki和kj，若树中存在一个节点序列ki,ki1,ki2,...,kin,kj,使得序列中除ki外的任一节点都是其在序列中的前一个节点的后继节点，则称该节点序列为由ki到kj的一条路径，用路径所通过的节点序列表示这条路径。路径长度等于路径所通过的节点数目减1（即路径上分支数目）。

（4）孩子节点、双亲节点和兄弟节点：在一棵树中，每个节点的后继节点称为该节点的孩子节点（或子女节点）。而该节点则称为其孩子节点的双亲节点（或父母节点）。具有同一双亲的孩子节点互为兄弟节点。另外，可以把每个节点的所有子树中的节点称为该节点的子孙节点，从树根节点到达该节点的路径上经过的所以节点（除自身外）称为该节点的祖先节点。

（5）节点的层次和树的高度：树中的每个节点都处在一定的层次上。节点层次从树根开始定义，根节点为第一层，它的孩子节点为第二层，以此类推，一个节点所在的层次为其双亲节点所在的层次加1.树中节点的最大层次称为树的高度（或树的深度）。

（6）有序树和无序树：若树中各节点的子树是按照一定的次序从左向右安排的，且相对次序是不能随意变换的，则称为有序树，否则称为无序树。

（7）森林：n(n>0) 个互不相交的树的集合称为森林。去掉树的根节点就成了森林。