树及其抽象数据类型

结构是从自然界的树抽象出来的,它具有树根、从根开始类似枝杈的分支关系和作为终点的叶子等特点。尽管在生活中看到的文件系统、家谱等表现形式各异,但本质上都是树结构。这些结构可以通过图形化的方式呈现出来,如下所示:

1
2
3
4
5
6
7
8
我的电脑
   ├── C:\
   │   ├── a.txt
   │   └── b.txt
   └── D:\
       ├── c.txt
       └── d.txt
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
祖父
 ├── 伯父
 │    └── 堂兄
 ├── 父亲
 │    ├── 兄
 │    ├── 我
 │    │    └── 子
 │    │        └── 孙
 │    └── 弟
 └── 叔叔
      └── 堂弟

1 树的定义

树 (Tree) 是一个由 $n$($n \geq 0$)个节点组成的有限集合,节点即树中的元素。当 $n=0$ 时,树称为空树;当 $n>0$ 时,树 $T$ 符合以下两个条件:

  1. 有一个特殊的节点称为根 (Root) 节点,它只有后继节点,没有前驱节点。
  2. 除根节点之外的其他节点可以分为 $m$ ($0 \leq m < n$) 个互不相交的集合 $T_0$、$T_1$、$\dots$、$T_{m-1}$,其中每个集合 $T_i$ ($0 \leq i < m$) 也具有树结构,并称为根节点的子树

树是递归定义的。节点是树的基本单位,若干个节点组成一棵子树,若干个互不相交的子树组成一棵树。树中的每个节点都是该树中某一棵子树的根。因此,树是由节点组成的、节点之间具有层次关系的非线性结构。

空树、1 个节点和 $n$ 个节点的树如下图所示,节点与其子树的根节点之间的连线表示节点之间的层次关系。

N 个节点的树

对于上图中的树 (c):

  • $A$ 为树的根节点,其他节点组成 3 个相互不相交的子集 $T_0$、$T_1$、$T_2$ 作为 $A$ 的子树。
  • $T_0=[B,E,F]$,$T_1=[C,G]$,$T_2=[D,H,I,J]$,3 棵子树的根节点分别为 $B$、$C$、$D$。

2 树的术语

2.1 父母、孩子、兄弟节点

在一棵树中,一个节点的子树的根节点称为其孩子 (Child) 节点;相对地,该节点是其孩子节点的父母 (Parent) 节点。只有根节点没有父母节点,其他节点有且只有一个父母节点。

拥有同一个父母节点的多个节点之间称为兄弟 (Sibling) 节点

节点的祖先 (Ancestor) 是指其父母节点,以及父母节点的父母节点等,直至根节点。节点的后代 (Descendant) 是指其所有孩子节点,以及孩子节点的子节点等。

2.2 度、叶子节点、分支节点

节点的度 (Degree) 是指节点所拥有的子树的棵树。

度为 0 的节点称为叶子 (Leaf) 节点,又称终端节点。树中除叶子节点之外的其他节点称为分支节点,又称非叶节点。

一棵树的度指的是树中各节点的度的最大值。

2.3 节点层次、树的深度

节点的层次 (Level) 属性反映节点处于树中的层次位置。约定根节点的层次为 1,其他节点的层次是其父节点的层次加 1。显然,兄弟节点的层次相同。

树的深度 (Depth)高度 (Height) 是指树中节点的最大层次数。

2.4 边、路径

设树中 $X$ 节点是 $Y$ 节点的父母节点,有序对儿 $(X,Y)$ 称为连接这两个节点的分支,也称为边 (Edge)

设 $(X_0,X_1, \dots, X_k)$ ($0 < k < n$) 是由树中节点组成的一个序列,且 $(X_i,X_{i+1})$ ($0 \leq i < k$) 都是树中的边,则称该序列为从 $X_0$ 到 $X_k$ 的一条路径 (Path)路径长度 (Path Length) 为路径上的边数。

2.5 无序树、有序树

在树的定义中,节点的子树 $(T_0, T_1, \dots, T_{m-1})$ 之间没有次序,可以交换位置的,称为无序树,简称树。如果节点的子树 $(T_0, T_1, \dots, T_{m-1})$ 从左至右是有次序的,不能交换位置,则称该树为有序树(Ordered Tree)

2.6 森林

森林 (Forest) 是 $m$ ($m \geq 0$) 棵互不相交的树的集合。给森林加上一个根节点就会变成一棵树,将树的根节点删除就会变成森林。

3 树的抽象数据类型

树的操作主要有创建树、获得父母/孩子/兄弟节点、遍历、插入和删除等。声明树的抽象数据类型如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 树的抽象数据类型
 * @param <T> 节点元素类型
 */
public abstract class AbstractTree<T> {
    //树的根节点
    AbstractTreeNode<T> root;

    //判断是否是空树
    abstract boolean isEmpty();
    //返回关键字为 key 节点所在的层次
    abstract int level(T key);
    //返回树的节点数
    abstract int size();
    //返回树的深度
    abstract int depth();
    //输出树的先根次序遍历结果
    abstract void preOrder();
    //输出树的后根次序遍历结果
    abstract void postOrder();
    //输出树的层次遍历结果
    abstract void levelOrder();
    //插入 x 元素作为根节点并返回
    abstract AbstractTreeNode<T> insert(T x);
    //插入 x 作为 p 节点的第 i 个子节点并返回
    abstract AbstractTreeNode<T> insert(AbstractTreeNode<T> p, T x, int i);
    //先序遍历查找首个关键字为 key 的节点
    abstract AbstractTreeNode<T> search(T key);
    //判断是否包含关键字为 key 的元素
    abstract boolean contains(T key);
    //删除以 key 节点为根的子树
    abstract T remove(T key);
    //删除 p 节点的第 i 棵子树
    abstract void remove(AbstractTreeNode<T> p, int i);
    //删除树的所有节点
    abstract void clear();
}

其中,树的节点抽象类型如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
/**
 * 树节点抽象类
 * @param <T> 节点元素类型
 */
public abstract class AbstractTreeNode<T> {
    //数据域
    public T data;
    //节点的所有孩子节点
    List<AbstractTreeNode<T>> children;
}

尽管在无序树中,孩子节点没有固定的次序,但是实际存储时会给孩子节点指定一个序号(children 集合的下标)来标识它们的顺序。因此,对孩子节点的获取、插入、删除等操作都会使用序号 $i$(0 ≤ $i$ < 孩子节点数)作为标识。如果 $i$ 指定的序号超出了孩子节点的范围,则会抛出序号越界的异常。