树型结构是一类重要的非线性数据结构，其中以树和二叉树最为常用，直观来看，树是以分支关系定义的层次结构。
树的定义
树（Tree）是 n(n>=0) 个节点的有限集合
(1) n = 0 时，树为空树，这是一种特殊情况；
(2) n = 1 时，树为非空树，有且仅有一个特定的称为根（Root）的节点；
(3) n > 1 时，树为非空树，除去唯一的根节点外，剩余 n-1 个节点可分为 m(m>0) 个互不相交的有限集合 T1，T2，…，Tm，其中每一个集合本身又是一棵树，称为根节点的子树（SubTree）。
数学表示
ADT Tree {
数据对象 D： D是具有相同特性的数据元素的集合。
数据关系 R：
若 D 为空集，则称为空树；
若 D 仅含一个数据元素，则 R 为空集，否则 R = { H }，H 为如下二元关系：
(1) 在 D 中存在唯一的称为根的数据元素 root，它在关系 H 下无前驱；
(2) 若 D - { root } ≠ Φ，则存在 D – { root } 的一个划分 D1，D2，…，Dm(m>0)，对任意的 j ≠ k(0≤j,k≤m)，有 Dj ∩ Dk = Φ，且对任意的 i(1≤i≤m)，唯一存在数据元素 xi ∈ Di，有 <root, xi> ∈ H；
(3) 对应于 D - { root } 的划分，H - { <root, x1>，…，<root, xm> } 有唯一的一个划分 H1，H2，…，Hm(m>0)，对任意的 j ≠ k(0≤j,k≤m)，有 Hj ∩ Hk = Φ，且对任意的 i(1≤i≤m)，Hi 是 Di 上的二元关系，(Hi, Di) 是一棵符合本定义的树，称为根 root 的子树。
基本操作 P：
InitTree(& T)；
…
TraverseTree(T, Visit())；
}
基本术语
- 祖先节点 - 子孙节点、双亲节点 - 孩子节点、兄弟节点；
- 节点的度、树的度；
- 叶子 / 终端节点 - 分支节点 / 非终端节点；
- 节点的层次：从根开始定义，根为第 1 层，依次往下；节点的深度：从根节点开始自顶向下逐层累加；节点的高度：从叶节点开始自底向上逐层累加；树的高度/深度；
- 有序树：节点的子树从左向右有次序，不可交换；无序树：
- 路径：自上而下经过的节点序列；路径长度：经过的边的个数；
- 森林（Forest）：m 棵互不相交的树的集合；对树的节点来说，其子树的集合即为森林；给 n 棵独立的树加上一个节点，将这些树作为该节点的子树，便构成了一棵树。
基本性质
- 树是一种递归的数据结构，逻辑结构上也是一种分层结构；
- 树的根节点没有前驱节点，除根结点外所有节点有且只有一个前驱节点（除根结点外，树上某个节点最多之和上层的一个节点有直接关系，即父节点）；
- 树中所有节点可以有零个或多个后继节点；
- 由 2 得，n 个节点的树中有 n-1 条边；，即树中节点数等于所有节点的度数和加1；
- 度为 m 的树中第 i 层至多有 mi-1 个节点（i≥1）；
- 高度为 h 的 m 叉树至多有 (mh-1)/(m-1) 个节点（等比数列求和）；
- 当树为完全树时，由 6 反向求最小高度得，具有 n 个节点的 m 叉树的最小高度为 ⌈logm(n(m-1)+1)⌉（向上取整）。