【数据结构】二叉树(Binary Tree)

1 树的概念

1.1 树的定义

树是由根结点和若干颗子树构成的。

树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。

这是一个普通的树。

1.2 相关概念

• 结点（node）：包含一个数据元素及若干指向子树分支的信息。
• 结点的度：一个结点拥有子树的数目称为结点的度（二叉树节点的度不大于2）。
• 叶子结点：也称为终端结点，没有子树的结点或者度为零的结点。
• 分支结点：也称为非终端结点，度不为零的结点称为非终端结点。
• 树的度：一棵树中，最大的结点的度称为树的度；
• 结点的层次：从根结点开始，假设根结点为第1层，根结点的子节点为第2层，依此类推，如果某一个结点位于第L层，则其子节点位于第L+1层。
• 树的深度：也称为树的高度，树中所有结点的层次最大值称为树的深度 。
• 有序树：如果树中各棵子树的次序是有先后次序，则称该树为有序树。
• 无序树：如果树中各棵子树的次序没有先后次序，则称该树为无序树。
• 森林：由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根结点删除，则该树就变成了一片森林，森林中的树由原来根结点的各棵子树构成 。

2 二叉树的概念

2.1 二叉树的定义

普通定义：二叉树是指树中节点的度不大于2的有序树。
递归定义：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。

2.2 二叉树的性质

• 每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
• 左子树和右子树是有顺序的，次序不能任意颠倒。
• 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

2.3 特殊二叉树

2.3.1 满二叉树

在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

特点：

• 叶子只能出现在最下一层。出现在其它层就不可能达成平衡。
• 非叶子结点的度一定是2。
• 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

2.3.2 完全二叉树

对一颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

特点：

• 叶子结点只能出现在最下层和次下层。
• 最下层的叶子结点集中在树的左部。
• 倒数第二层若存在叶子结点，一定在右部连续位置。
• 如果结点度为1，则该结点只有左孩子，即没有右子树。
• 同样结点数目的二叉树，完全二叉树深度最小。
  注：满二叉树一定是完全二叉树，但反过来不一定成立。

3 二叉树的储存结构

3.1 顺序储存

二叉树的顺序存储结构就是使用一维数组存储二叉树中的结点，并且结点的存储位置，就是数组的下标索引。

存储在一位数组中的形式：

如果二叉树为完全二叉树，节点刚好填满数组。

当二叉树不为完全二叉树时，图中（D、H、I）为不存在的节点。

起存储结构如下，∧表示数组中此位置没有存储结点。此时，存储结构存在浪费问题。

所以顺序储存结构适用于完全二叉树。

3.2 二叉链表

既然顺序存储不能满足二叉树的存储需求，那么考虑采用链式存储。

由二叉树定义可知，二叉树的每个结点最多有两个孩子。因此，可以将结点数据结构定义为一个数据和两个指针域。

如图采用一种链表结构存储二叉树，这种链表称为二叉链表。

4 二叉树的遍历

二叉树的遍历是指从二叉树的根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次。共分为4种：

• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历

4.1 前序遍历 NLR

前序遍历：Preorder Traversal
NLR：Node→Left→Right

从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。

访问顺序为：
A→B→D→H→D→I→D→B→E→J→E→B→A→C→F→C→G

遍历输出为：
ABDHIEJCFG

4.2 中序遍历 LNR

中序遍历：Inorder Traversal
LNR：Left→Node→Right

从二叉树的根结点出发，先访问左子树，然后访问根节点，最后访问右子树。

或者说，只有当结点的子结点已经被遍历后才能遍历该结点。

访问循序为：
A→B→D→H→D→I→D→B→E→J→E→B→A→C→F→C→G

遍历输出为：
HDIBJEAFCG

4.3 后序遍历 LRN

后序遍历：Postorder Traversal
LRN：Left→Right→Node

从二叉树的根结点出发，从左到右先叶子后节点的方式遍历左右子树，最后访问根节点。

访问循序为：

A→B→D→H→D→I→D→B→E→J→E→B→A→C→F→C→G→C→A

遍历输出为：
HIDJEBFGCA

4.4 层序遍历

从根节点从上往下逐层遍历，在同一层，按从左到右的顺序对节点逐个访问。与上面提到的顺序存储相类似。

遍历输出：
ABCDEFGHIJ

---

参考
https://www.jianshu.com/p/bf73c8d50dc2
https://www.cnblogs.com/du001011/p/11229170.html