树形结构是一种非线性数据结构。树是以分支关系来定义的层次结构。

树形结构广泛应用在客观世界中，比如人类族谱、社会组织结构以及计算机源码中的语法结构等。

结构定义

树是具有 $n(n>=0)$ 个节点的有限集。

当 $n==0$ 时，称为空树。 当 $n>0$ 时，称为非空树。

  1. 在非空树中，有且仅有一个特定的称为根的节点(当$n==1$时)。
  2. 当 $n>1$ 时，其余节点可分为 $m(m>0)$ 个互不相交的有限集，$T_1,T_2,…,T_m$ ，其中每一个集合本身又是一棵树，并且称为根的子树。

抽象定义

ADT Tree:
数据对象 $D$：$D$ 是具有相同特性的数据元素的集合。
数据关系 $R$: 若 $D$ 为空集，则称为空树。
若 $D$ 仅含一个数据元素，则 $R$ 为空集，否则 $R = \lbrace H \rbrace $, $H$ 是如下的二元关系：
  1. 若 $D$ 中存在惟一的称为根的数据元素 $root$，它在关系 $H$ 下无前驱;
  1. 若 $D - \lbrace root \rbrace \ne \Phi$，则存在 $D - \lbrace root \rbrace $ 的一个划分 $D_1, D_2,…,D_m(m\ge0)$，对任意 $j \ne k(1 \le j,k \le m)$ 有 $D_j \cap D_k = \Phi$，且对任意的 $i(1 \le i \le m)$，惟一存在数据元素 $x_i \in D_i$，有 $\left \langle root, x_i \right \rangle \in H$;
  1. 对应于 $D-\lbrace root\rbrace$ 的划分，$H - \lbrace \left \langle root, x_1 \right \rangle, \left \langle root, x_2 \right \rangle,…,\left \langle root, x_m \right \rangle \rbrace$ 有惟一的一个划分 $H_1,H_2,…,H_m(m \ge 0)$，对任意 $j \ne k(1 \le j, k \le m)$ 有 $H_j \cap H_k = \Phi $， 且对任意 $i(1 \le i \le m)$，$H_i$ 是 $D_i$ 上的二元关系，$(D_i, \lbrace H_i \rbrace)$ 是一个符合本定义的树，称为 $root$ 的子树。
基本操作 $P$:
/* 操作结果： 构造空树T */
InitTree(&T);

/* 初始条件： 树T存在
 * 操作结果： 销毁树T
*/
DestoryTree(&T);

/* 初始条件： definition给出树T的定义
 * 操作结果： 按definition构造树T
*/
CreateTree(&T, definition);

/* 初始条件： 树T存在
 * 操作结果： 将树T清为空树
*/
ClearTree(&T);

/* 初始条件： 树T存在
 * 操作结果： 若T为空树，返回TRUE；否则返回FALSE
*/
TreeEmpty(T);

/* 初始条件： 树T存在
 * 操作结果： 返回T的深度
*/
TreeDepth(T);

/* 初始条件： 树T存在
 * 操作结果： 返回T的根
*/
Root(T);

/* 初始条件： 树T存在, cur_e是T中的某个节点
 * 操作结果： 返回cur_e的值
*/
Value(T, cur_e);

/* 初始条件： 树T存在, cur_e是T中的某个节点
 * 操作结果： 结点cur_e赋值为value
*/
Assign(T, cur_e, value);

/* 初始条件： 树T存在, cur_e是T中的某个节点
 * 操作结果： 若cur_e是T的非根节点，则返回它的双亲，否则返回为空。
*/
Parent(T, cur_e);

/* 初始条件： 树T存在, cur_e是T中的某个节点
 * 操作结果： 若cur_e是T的非叶子节点，则返回它的最左孩子，否则返回为空。
*/
LeftChild(T, cur_e);

/* 初始条件： 树T存在, cur_e是T中的某个节点
 * 操作结果： 若cur_e有有兄弟，则返回它的有兄弟，否则返回空。
*/
RightSibling(T,cur_e);

/* 初始条件： 树T存在, p指向T中的某个结点，i指节点p的度(i>=1 && i<=p>), 非空树c与T不相交
 * 操作结果： 插入c为T中p结点的第i棵子树
*/
InsertChild(&T, &p, i, c);

/* 初始条件： 树T存在, p指向T中的某个结点，i指节点p的度(i>=1 && i<=p>)
 * 操作结果： 删除T中p所指节点的第i棵子树
*/
DeleteChild(&T, &p, i);

/* 初始条件： 树T存在, Visit是对结点操作的应用函数
 * 操作结果： 按某种次序对T的每个结点调用函数visit()一次且最多一次，
 * 一旦visit()失败，则操作失败。
*/
TraverseTree(T, visit());

术语

树的结点：包含一个数据元素及若干指向其子树的分支。

结点的度：结点拥有的子树数称为。

叶子：度为0的结点。

分支结点：度不为0的结点。

子结点：当前结点的子树的根。

父结点：有子树的结点为子树的根结点的父结点。

兄弟结点：相同父结点之间的结点称为兄弟结点。

祖先结点：根到该结点所经分支的所有结点。

子孙结点：该结点子树中的任一结点。

结点层次：从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第 $l$ 层，则其子树的根就在第 $l+1$ 层。其双亲在同一层的结点互为堂兄弟。

树的深度: 树中结点的最大层次。

有序树：树中结点的各子树是从左到右有次序的。最左边子树的根为第一个孩子，最右边的为最后一个孩子。

森林是 $m(m \ge 0)$ 棵互不相交的树的集合。对树中的每个结点而言，其子树的集合即为森林。

基于森林的定义

树和森林的定义
任何一棵树是一个二元组 $Tree = (root, F)$，其中，
  1. $root$ 是数据元素，称为树的根节点；
  1. $F$ 是 $m(m \ge 0)$ 棵树的森林，$F=(T_1,T_2,…,T_m)$，其中 $T_i=(r_i, F_i)$称为根 $root$ 的第 $i$ 棵子树；（这条保证了当前结点的子树的结构）
  1. 当 $m \ne 0$ 时，在树根和其子树森林之间存在关系：$RF= \lbrace < root, r_i> | i=1,2,…,m, m \ge 0 \rbrace$ 。（这条保证了结点和其子树的根节点是父子关系）