树的基本概念

2.6.1　树的基本概念

树（Tree）是一种简单的非线性结构。在树这种数据结构中，所有数据元素之间的关系具有明显的层次特性。如图2-25所示表示了一棵一般的树。由如图2-25所示可以看出，在用图形表示树这种数据结构时，很像自然界中的树，只不过是一棵倒长的树。因此，这种数据结构就用“树”来命名。

图2-25　一般的树

在树的图形表示中，总是认为在用直线连起来的两端节点中，上端节点是前件，下端节点是后件。这样，表示前后件关系的箭头就可以省略。

在现实世界中，能用树这种数据结构表示的例子有很多。例如，如图2-26所示中的树表示了学校行政关系结构；如图2-27所示中的树反映了一本书的层次结构。由于树具有明显的层次关系。因此，具有层次关系的数据都可以用树这种数据结构来描述。在所有的层次关系中，人们最熟悉的是血缘关系，按血缘关系可以很直观地了解树结构中各数据元素节点之间的关系。因此，在描述树结构时，也经常使用血缘关系中的一些术语。

图2-26　学校行政层次结构树

图2-27　书的层次结构树

下面介绍树这种数据结构中的一些基本特征，同时介绍有关树结构的基本术语。

在树结构中，每一个节点只有一个前件，称为父节点，没有前件的节点只有一个，称为树的根节点，简称为树的根。例如，在如图2-25所示中，节点R是树的根节点。

在树结构中，每一个节点可以有多个后件，它们都称为该节点的子节点。没有后件的节点称为叶子节点。例如，在如图2-25所示中，节点C、M、F、E、X、G、S、L、Z、A均为叶子节点。

在树结构中，一个节点所拥有的后件个数称为该节点的度。例如，在如图2-25所示中，根节点R的度为4；节点T的度为3；节点K、B、N、H的度为2；节点P、Q、D、O、Y、W的度为1。叶子节点的度为0。在树中，所有节点中的最大的度称为树的度。例如，如图2-25所示的树的度为4。

前面已经说过，树结构具有明显的层次关系，即树是一种层次结构。在树结构中，一般按如下原则分层：

根节点在第1层。

同一层上所有节点的所有子节点都在下一层。例如，在如图2-25所示中，根节点R在第l层;节点K、P、Q、D在第2层；节点B、E、N、O、T在第3层；节点C、H、X、Y、S、W、Z、A在第4层；节点M、F、G、L在第5层。

树的最大层次称为树的深度。例如，如图2-25所示的树的深度为5。

在树中，以某节点的一个子节点为根构成的树，称为该节点的一棵子树。例如，在如图2-25所示中：节点R有4棵子树，它们分别以K、P、Q、D为根节点；节点P有1棵子树，其根节点为N；节点T有3棵子树，它们分别以W、Z、A为根节点。

在树中，叶子节点没有子树。

在计算机中，可以用树结构来表示算术表达式。

在一个算术表达式中，有运算符和运算对象。一个运算符可以有若干个运算对象。例如，取正（+）与取负（－）运算符只有一个运算对象，称为单目运算符；加（+）、减（－）、乘（*）、除（/）、乘幂（**）运算符有两个运算对象，称为双目运算符；三元函数f（x，y，z）中的f为函数运算符，它有三个运算对象，称为三目运算符。一般来说，多元函数运算符有多个运算对象，称为多目运算符。算术表达式中的一个运算对象可以是子表达式，也可以是单变量（或单变数）。例如，在表达式a*b+c中，运算符“+”有两个运算对象，其中a*b为子表达式，c为单变量；而在子表达式a*b中，运算符“*”有a和b两个运算对象，它们都是单变量。

用树来表示算术表达式的原则如下：

①表达式中的每一个运算符在树中对应一个节点，称为运算符节点。

②运算符的每一个运算对象在树中为该运算符节点的子树（在树中的顺序为从左到右）。

③运算对象中的单变量均为叶子节点。

根据以上原则，可以将表达式a*（b+c/d）+e*h-g*f（s，t，x+y）用如图2-28所示的树来表示。表示表达式的树通常称为表达式树。由图2-28可以看出，表示一个表达式的表达式树是不唯一的。如上述表达式可以表示成如图2-28（a）和图2-28（b）所示的两种表达式树。

图2-28　a*（b+c/d）+e*h-g*f（s,t,x+y）的两种表达式树

树在计算机中通常用多重链表表示。多重链表中的每个节点描述了树中对应节点的信息，而每个节点中的链域（即指针域）个数将随树中该节点的度而定，其一般结构如图2-29所示。

在表示树的多重链表中，由于树中每个节点的度一般是不同的，因此，多重链表中各节点的链域个数也就不同，这将导致对树进行处理的算法很复杂。如果用定长的节点来表示树中的每个节点，即取树的度作为每个节点的链域个数，这就可以对树的各种处理算法大大简化。但在这种情况下，容易造成存储空间的浪费，因为有可能在很多节点中存在空链域。后面将介绍用二叉树来表示一般的树，会给处理带来方便。

图2-29　树链表中的节点结构