什么是树

树（Tree）是一种抽象数据类型，用来模拟实现具有树状类型结构的数据集合。它具有n（n>=0）个有层次的有限结点。当n=0时，称为空树；n>0时，其余结点分为m个互斥的有限集合T1，T2，T3，每个集合分别称为子树。

与栈、队列和链表不同，树是一种非线性数据结构。一颗树只有一个根结点。拥有多颗根结点的数据结构是树的集合，称之为森林

1.树的性质

结点数n>0的树满足以下性质：

1. 每个结点存在有限个子结点或无子结点；

2. 没有父结点的结点称之为根结点；

3. 每个非根结点有且只有一个父结点；

4. 除了根节点外，每个子节点可以分为多个不相交的子树；

5. 树中不存在环。

2.树中涉及到的基本术语：

1.结点的度：

结点拥有子树的个数称为该结点的度。如上图中B的度为2，C的度为1。度为0的结点称之为叶子结点或终端结点，度不为0的结点称之为分支结点或非终端结点。除根结点外，分支结点也称之为内部结点。

2.树的度：

树的度是树内各个结点度的最大值。

3.子女节点：

若结点x存在子树，则子树的根结点称之为结点x的子女结点。

4.父结点：

若结点x有子女结点，则它为其子女结点的父结点。

5.兄弟结点：

同一父结点的子女互称兄弟。如上图中B、C、D互称兄弟。

6.祖先结点：

从根结点到目标结点所经历的所有结点称为目标结点的祖先结点，如图中E的祖先结点为A、B。

7.子孙结点：

某一结点的子女，以及这些子女的子女均为该节点的子孙结点。

8.层次与深度：

根结点所处的层次为第1层，其子女所属的层次为第2层。以此类推，若某结点所处的层次为第i层，其子女所处的层次为第i+1层。树中结点的最大层次称之为树的深度或高度。上图中树的深度为4。

9.有序树与无序树：

树的有序或无序由结构定义。如果将树中结点的子树规定了从左至右的次序，且不能互换，称该树为有序树，否则为无序树。

10.二叉树：

每个节点最多含有两个子树的树称为二叉树；

11.完全二叉树：

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树

12.满二叉树：

"除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。

13.哈夫曼树：

带权路径最短的二叉树称为哈夫曼树或最优二叉树；

3.树的存储方式

顺序存储和链式存储都不能很好地反映出树的逻辑关系，故需采用顺序和链式相结合的方式。树的存储方式主要有以下三种：

1.双亲表示法

双亲表示法采用顺序表（也就是数组）存储普通树，其实现的核心思想是：顺序存储各个节点的同时，给各节点附加一个记录其父节点位置的变量。

注意，根节点没有父节点（父节点又称为双亲节点），因此根节点记录父节点位置的变量通常置为 -1。

2.孩子表示法

使用顺序加链式的存储方式。首先会建立一个顺序表存储树中的各个结点，此外，孩子表示法还会在每个结点后配备一个链表，用于存储它的子女结点。无子女结点的结点对应的是空链表。

孩子兄弟表示法采用的是链式存储的方式。从树的根结点开始，依次使用链表存储各个结点的孩子结点和兄弟结点。该链表中的结点分为三部分：孩子结点、数据域、兄弟结点。