数据中的树结构

前面提到过，数据结构按关系分类有四种：线性结构、树结构、图结构和集合结构，其中树结构在文件系统中使用最多，所以本书重点讲解树结构。

树的定义

树形结构是一类重要的非线性数据结构，它是由n（n≥1）个有限节点组成一个具有层次关系的集合。

在树结构中，用一个圆圈表示一个节点，圆圈内的符号代表该节点数据信息，节点之间的关系通过连线表示。即使每条连线上都不带箭头，但它仍然是有向的，其方向隐含着从上向下，即连线的上方节点是下方节点的前驱，下方节点是上方节点的后继。

把它叫作树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。图1-7是一个“树”结构的示意图。

在图1-7中，A是根节点，它一般画在树的顶部。其余节点分成两个互不相交的子集：T0＝{B,D,E,F,I,J,K}，T1＝{C,G,H,L,M,N,O,P}，它们都是根节点A的子树。再看T0，它的根是B，其余根节点又分为3个互不相交的子集T00＝{D,I,K}，T01＝{E,J}，T03＝{F}，它们是T0的子树。

树结构的基本术语

①节点。节点包含一个数据元素及若干指向其子树的分支。例如，在图1-7中的树总共有16个节点，为方便起见，每个数据项用单个字母表示。

②节点的度。节点的度是指节点所拥有的子树的个数。例如，在图1-7所示的树中，根A的度为2，节点B的度为3，节点K、J、F、L、O、P的度为0。

“树”结构的示意图

③树的度。树的度指的是树中各节点的度的最大值。例如，图1-7所示的树的度为3。

④叶节点（终端节点）。叶节点指度为0的节点。例如，在图1-7所示的树中，{K,J,F,L,O,P}构成树的叶节点的集合。

⑤分支节点（非终端节点）。分支节点指除叶节点以外的节点（度不为0的节点）。例如，在图1-7所示的树中，A、B、C、D、E、G、H、I、M、N就是分支节点。

⑥子女节点。若节点x有子树，则子树的根节点即为节点x的子女。例如，在图1-7所示的树中，节点A有2个子女，节点B有3个子女，节点K没有子女。子女节点也称作孩子节点。

⑦双亲节点。若节点x有子女，x即为子女的双亲。例如，在图1-7所示的树中，节点B、C有一个双亲A，根节点A没有双亲。双亲节点也叫父节点。

⑧兄弟节点。同一双亲的子女互称为兄弟。例如，在图1-7所示的树中，节点B、C称为兄弟；D、E、F也称为兄弟；但F、G、H不是兄弟。

⑨堂兄弟节点。双亲在同一层的节点互为堂兄弟节点。例如，在图1-7所示的树中，G和H是F的堂兄弟节点。

⑩祖先节点。祖先节点是指从根节点到该节点所经分支上的所有节点。例如，在图1-7所示的树中，节点K的祖先为A、B、D、I。

⑪子孙节点。某一节点的子女，以及这些子女的子女都是该节点的子孙。例如，在图1-7所示的树中，节点B的子孙为D、E、F、I、J、K。

⑫节点的层次。树中的每个节点都处在一定的层次上，即从根到该节点所经路径上的分支条数。例如，在图1-7所示的树中，根节点在第1层，它的子女节点在第2层，以此类推，树中任意一节点的层次为它的双亲节点的层次加1。

⑬树的高（深）度。树的高度是指树中节点所处的最大层次，空树的高度为0，只有一个根节点的树的高度为1。例如，在图1-7所示的树中，树的高度为5。

⑭有序树。有序树指树中各节点的子树是按照一定的次序从左向右排列的，且相对次序是不能随意变换的。

⑮无序树。无序树是指树中各节点的子树是没有一定的排列次序，且相对次序是可以随意变换的。

⑯森林。森林指n（n≥0）个互不相交的树的集合。删去一棵非空树的根节点，树就变成森林；反之，若增加一个根节点，让森林中每一棵树的根节点都变成它的子女，森林就成为一棵树。

树结构的特点

树结构具有以下的特点：

①每个节点有零个或多个子节点；

②每一个子节点只有一个父节点；

③没有前驱的节点为根节点；

④除了根节点外，每个子节点可以分为m个不相交的子树。