目录
树
在讲二叉树之前，我们先需要简单了解一下树的相关知识。
树的定义
树的定义如下：树（Tree）是n个节点的有限集。n=0时称为空树。在任意一颗非空树中：
- 有且仅有一个特定的称为根（Root）的节点；
- 当n>1时，其余节点可分为m（m>0）个互不相交的有限集T1、T2、···、Tm。其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。
注意事项：
- m>0时，子树的个数没有限制 ，但子树之间不能有交集，否则就不是树形结构。
- n>0时根节点是唯一的，不可能存在多个根节点。
节点的分类
树的节点包含一个数据元素及若干个指向其子树的分支。
在将树的分类之前先介绍度概念：
- 节点的度（Degree）：节点拥有的子树数。
- 树的度：树内各节点度的最大值。
分类：
- 叶节点（终端节点）：度为0的节点。
- 分支节点（内部节点，非终端节点）：度不为0的节点。
节点间的关系
关系如下：
- 节点的子树的根称为该节点的孩子（Child），相应该节点称为孩子的双亲（Parent）。
- 同一个双亲的孩子之间互称兄弟（Sibling）。
- 节点的祖先是从根到该节点所经分支上的所有节点。
- 以某节点为根的子树中的任一节点都称为该节点的子孙。
树的表示方法
树有多种表示方法。
双亲表示法
树这种结构除了根节点外，其余每个节点，不一定有孩子节点，但是一定有且仅有一个双亲节点。
假设一段连续空间存储树的节点，将根结点的parent值为-1，其余节点的parent存储双亲节点的下标。
public class Tree{
public TreeNode [] elem;//节点数组
public int r;//根的位置
public int n;//节点个数
static class TreeNode{
int data;//节点数据
int parent;//双亲位置
}
}
孩子表示法
使用多重链表，每个节点有多个指针域，其中每个指针指向一颗子树的根节点。
由于树中每个节点的度是不一样的，所以有两种方式。
- 方式一：指针域的个数就是树的度（节点度的最大值），这种方式浪费空间大。
- 方式二：每个节点的指针域个数等于该节点的度。
public class Tree{
public TreeNode []elem;//节点数组
int r;//跟的位置
int n;//节点数
static class TreeNode{
int child;
TreeNode next;
}
}
孩子兄弟表示法
任意一棵树，它的节点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。
因此我们使用两个指针，分别指向该节点的第一个孩子和此节点的右兄弟。
class TreeNode {
int value; // 树中存储的数据
Node firstChild; // 第一个孩子引用
Node nextBrother; // 下一个兄弟引用
}
概念总结
关于树的重要概念总结如下：
- 结点的度：一个结点含有子树的个数称为该结点的度；
- 树的度：一棵树中，所有结点度的最大值称为树的度；
- 叶子结点或终端结点：度为0的结点称为叶结点；
- 双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；
- 孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；
- 根结点：一棵树中，没有双亲结点的结点；
- 结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推；
- 树的高度或深度：树中结点的最大层次；
- 非终端结点或分支结点：度不为0的结点；
- 兄弟结点：具有相同父结点的结点互称为兄弟结点；
- 堂兄弟结点：双亲在同一层的结点互为堂兄弟；
- 结点的祖先：从根到该结点所经分支上的所有结点；
- 子孙：以某结点为根的子树中任一结点都称为该结点的子孙；
- 森林：由m（m>=0）棵互不相交的树组成的集合称为森林。