树的定义
树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称为树根。我们可以形式地给出树的递归定义如下:
- 单个结点是一棵树，树根就是该结点本身。
- 设T1,T2,..,Tk是树，它们的根结点分别为n1,n2,..,nk。用一个新结点n作为n1,n2,..,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称n1,n2,..,nk为一组兄弟结点，它们都是结点n的儿子结点。我们还称n1,n2,..,nk为结点n的子树。
空集合也是树，称为空树。空树中没有结点。
一棵典型的树如图1所示：
图1
树的层次结构
由图1可以看出树的形状就像一棵现实中的树，只不过是倒过来的。
树的相关术语
1.
一个结点的儿子结点的个数称为该结点的度。一棵树的度是指该树中结点的最大度数。
2.
树中度为零的结点称为叶结点或终端结点。
3.
树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。
例如在图1中，结点A，B和E的度分别为3，2，0。其中A为根结点,B为内部结点，E为叶结点，树的度为3。
4.
如果存在树中的一个结点序列K1,K2,..,Kj，使得结点Ki是结点Ki+1的父结点(1≤i≤j)，则称该结点序列是树中从结点K1到结点Kj的一条路径或道路。我们称这条路径的长度为j-1，它是该路径所经过的边(即连接两个结点的线段)的数目。树中任一结点有一条到其自身的长度为零的路径。
例如，在图1中，结点A到结点I有一条路径ABFI，它的长度为3。
5.
如果在树中存在一条从结点K到结点M的路径，则称结点K是结点M的祖先，也称结点M是结点K的子孙或后裔。
例如在图1中，结点F的祖先有A，B和F自己，而它的子孙包括它自己和I,J。注意，任一结点既是它自己的祖先也是它自己的子孙。
6.
我们将树中一个结点的非自身祖先和子孙分别称为该结点的真祖先和真子孙。在一棵树中，树根是唯一没有真祖先的结点。叶结点是那些没有真子孙的结点。子树是树中某一结点及其所有真子孙组成的一棵树。
7.
树中一个结点的高度是指从该结点到作为它的子孙的各叶结点的最长路径的长度。树的高度是指根结点的高度。
例如图1中的结点B，C和D的高度分别为2，0和1，而树的高度与结点A的高度相同为3。
8.
从树根到任一结点n有唯一的一条路径，我们称这条路径的长度为结点n的深度或层数。根结点的深度为0，其余结点的深度为其父结点的深度加1。深度相同的结点属于同一层。
例如，在图1中，结点A的深度为0；结点B，C和D的深度为1；结点E，F，G，H的深度为2；结点I和J的深度为3。在树的第二层的结点有E，F，J和H，树的第0层只有一个根结点A。
9.
树的定义在某些结点之间确定了父子关系，我们又将这种关系延拓为祖先子孙关系。但是树中的许多结点之间仍然没有这种关系。例如兄弟结点之间就没有祖先子孙关系。如果我们在树的每一组兄弟结点之间定义一个从左到右的次序，则得到一棵有序树；否则称为无序树。设结点n的所有儿子按其从左到右的次序排列为n1,n2,..,nk，则我们称n1是n的最左儿子，或简称左儿子，并称ni是ni-1的右邻兄弟，或简称右兄弟(i=2,3,..k)。
图2中的两棵树作为无序树是相同的，但作为有序树是不同的，因为结点a的两个儿子在两棵树中的左右次序是不同的。后面，我们只关心有序树，因为无序树总可能转化为有序树加以研究。
图2
两棵不同的有序树
我们还可以将兄弟结点之间的左右次序关系加以延拓：如果a与b是兄弟，并且a在b的左边，则认为a的任一子孙都在b的任一子孙的左边。
10.
森林是m(m>0)棵互不相交的树的集合。如果我们删去一棵树的树根，留下的子树就构成了一个森林。当我们删去的是一棵有序树的树根时，留下的子树也是有序的，这些树组成一个树表。在这种情况下，称这些树组成的森林为有序森林或果园。
11.
在讨论表的时候，我们对表的每一位置的元素赋予一个元素值。这里，我们也用树的结点来存储元素，即对于树中的每一个结点赋予一个标号，这个标号并不是该结点的名称，而是存储于该结点的一个值。结点的名称总是不变的，而它的标号是可以改变的。我们可以做这样的类比：
树：表 = 标号：元素 = 结点：位置
树的数学定义
连通无回路的无向图称为无向树，简称树。若该无向图至少含有两个连通分支，则称为森林。
在无向树中，悬挂顶点称为树叶，度数大于或等于2的顶点称为分支点。
设D是有向图，若D的基图是无向树，则称D为有向树。
设T是n(n≥2)阶有向树，若T中有一个顶点的入度为0，其余顶点的入度均为1，则称T为根树。入度为0的顶点称为树根，入度为1出度为0的顶点称为树叶，入度为1出度不为0的顶点称为内点，内点和树根统称为分支点。从树根到T的任意顶点v的通路（路径）长度称为v的层数，层数最大顶点的层数称为树高。将平凡树也称为根树。
注意：在计算机学中所讨论的树和纯粹数学中的树有所不同。事实上，计算机学中的树就是离散数学中的根树。
ADT树的操作
树的最重要的作用之一是用以实现各种各样的抽象数据类型。与表的情形相同，定义在树上的操作也是多种多样的。在这里我们只考虑作为抽象数据类型的树的几种典型操作。
以下的∧表示空结点，∧在树的不同实现方法中有不同的定义。
ADT树的基本运算
|
运算
|
含义
|
|
Parent(v,T)
|
这是一个求父结点的函数，函数值为树T中结点v的父亲。当v是根结点时，函数值为∧，表示结点v没有父结点。
|
|
Leftmost_Child(v,T)
|
这是一个求最左儿子结点的函数。函数值为树T中结点v的最左儿子。当v是叶结点时，函数值为∧，表示结点v没有儿子。
|
|
Right_Sibling(v,T)
|
这是一个求右邻兄弟的函数，函数值为树T中结点v的右邻兄弟。当v没有右邻兄弟时，函数值为∧。
|
|
Create(i,x,T1,T2,..,Ti,T)
|
这是一族建树过程。对于每一个非负整数i，该函数生成一棵新树T，T的根结点是标号为x的新结点v，并令v有i个儿子，这些儿子从左到右分别为树T1,T2,..,Ti的根。当i=0时，v既是树根，又是树叶。
|
|
Label(v,T)
|
这时一个求标号的函数，函数值就是结点v的标号。
|
|
Root(T)
|
这是一个求树根的函数，函数值为树T的根结点。当T是空树时，函数值为∧。
|
|
MakeNull(T)
|
这是一个过程，它使T成为一棵空树。
|
树的遍历
树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的系统的访问，即依次对树中每个结点访问一次且仅访问一次。树的3种最重要的遍历方式分别称为前序遍历、中序遍历和后序遍历。以这3种方式遍历一棵树时，若按访问结点的先后次序将结点排列起来，就可分别得到树中所有结点的前序列表，中序列表和后序列表。相应的结点次序分别称为结点的前序、中序和后序。
树的这3种遍历方式可递归地定义如下：
§
如果T是一棵空树，那么对T进行前序遍历、中序遍历和后序遍历都是空操作，得到的列表为空表。
§
如果T是一棵单结点树，那么对T进行前序遍历、中序遍历和后序遍历都只访问这个结点。这个结点本身就是要得到的相应列表。
§
否则，设T如图6所示，它以n为树根，树根的子树从左到右依次为T1,T2,..,Tk，那么有：
§
对T进行前序遍历是先访问树根n,然后依次前序遍历T1,T2,..,Tk。
§
对T进行中序遍历是先中序遍历T1，然后访问树根n，接着依次对T2,T2,..,Tk进行中序遍历。
§
对T进行后序遍历是先依次对T1,T2,..,Tk进行后序遍历，最后访问树根n。
图6
树T
前序遍历和中序遍历可形式地依次描述如下
三种遍历可以形式地描述如下，其中用到了树的ADT操作：
|
Procedure
Preorder_Traversal(v:NodeType); {前序遍历算法}
begin
Visite(v);
{访问节点v}
i:=Leftmost_Child(v);
while i<>∧
do
begin
Preorder_Traversal(i);{从左到右依次访问v的每一个儿子节点i}
i:=Right_Sibling(i);
end;
end;
|
|
Procedure
Inorder_Traversal(v:NodeType); {中序遍历算法}
begin
if
Leftmost_Child(v)=∧ {判断v是否是叶节点}
then
Visite(v)
else
begin
Inorder_Traversal(Leftmost_Child(v)); {中序遍历v的左边第一个儿子节点}
Visite(v); {访问节点v}
i:=Right_Sibling(Leftmost_Child(v)); {i=v的左边第二个儿子}
while i<>∧ do
begin
Inorder_Traversal(i);
{从左边第二个开始到最右边一个为止依次访问v的每一个儿子节点i}
i:=Right_Sibling(i);
end;
end;
end;
|
|
Procedure
Postorder_Traversal(v:NodeType); {后序遍历算法}
begin
i:=Leftmost_Child(v);
while i<>∧ do
begin
Preorder_Traversal(i);{从左到右依次访问v的每一个儿子节点i}
i:=Right_Sibling(i);
end;
Visite(v);
{访问节点v}
end;
|
为了将一棵树中所有结点按某种次序列表，只须对树根调用相应过程。例如对图7中的树进行前序遍历、中序遍历和后序遍历将分别得到前序列表：A
B E F I J C D G H；中序列表：E
B I F J A C G D H；后序列表：E
I J F B C G H D A。
图7
一棵树
下面介绍一种方法可以产生上述3种遍历方式的结点列表。设想我们从树根出发，依逆时针方向沿树的外缘绕行(例如围绕图7中的树绕行的路线如图8所示)。绕行途中可能多次经过同一结点。如果我们按第一次经过的时间次序将各个结点列表，就可以得到前序列表；如果按最后一次经过的时间次序列表，也就是在即将离开某一结点走向其父亲时将该结点列出，就得到后序列表。为了产生中序列表，要将叶结点与内部结点加以区别。叶结点在第一次经过时列出，而内部结点在第二次经过时列出。
