算法：树与二叉树的基础知识

1. 树简介

1.1 树的定义

树（Tree）：由 n≥0 个节点与节点之间的关系组成的有限集合。当 n=0 时称为空树，当 n>0 时称为非空树。

之所以把这种数据结构称为「树」是因为这种数据结构看起来就像是一棵倒挂的树，也就是说数据结构中的「树」是根朝上，而叶朝下的。如下图所示。

「树」具有以下的特点：

有且仅有一个节点没有前驱节点，该节点被称为树的 「根节点（Root）」 。
除了根节点以之，每个节点有且仅有一个直接前驱节点。
包括根节点在内，每个节点可以有多个后继节点。
当 n>1 时，除了根节点之外的其他节点，可分为 m(m>0) 个互不相交的有限集合 T₁,T₂,…,T_m，其中每一个集合本身又是一棵树，并且被称为根的 「子树（SubTree）」。

如下图所示，红色节点 A 是根节点，除了根节点之外，还有 3 棵互不相交的子树 T₁(B,E,H,I,G)、T₂(C)、T3(D,F,G,K)。

1.2 树的相关术语

下面我们来介绍一下树结构中的一些基本术语。

1.2.1 节点分类

「树的节点」 由一个数据元素和若干个指向其子树的树的分支组成。而节点所含有的子树个数称为 「节点的度」。度为 0的节点称为 「叶子节点」 或者 「终端节点」，度不为 0 的节点称为 「分支节点」 或者 「非终端节点」。树中各节点的最大度数称为 「树的度」。

树的节点：由一个数据元素和若干个指向其子树的树的分支组成。
节点的度：一个节点所含有的子树个数。
叶子节点（终端节点）：度为 0的节点。例如图中叶子节点为 C、H、I、G、F、K。
分支节点（非终端节点）：度不为 0 的节点。例如图中分支节点为 A、B、D、E、G。
树的度：树中节点的最大度数。例如图中树的度为 3。

1.2.2 节点间关系

一个节点的子树的根节点称为该节点的 「孩子节点」，相应的，该节点称为孩子的 「父亲节点」。同一个父亲节点的孩子节点之间互称为 「兄弟节点」。

孩子节点（子节点）：一个节点含有的子树的根节点称为该节点的子节点。例如图中 B 是 A 的孩子节点。
父亲节点（父节点）：如果一个节点含有子节点，则这个节点称为其子节点的父节点。例如图中 B 是 E 的父亲节点。
兄弟节点：具有相同父节点的节点互称为兄弟节点。例如图中 F、G 互为兄弟节点。

1.2.3 树的其他术语

「节点的层次」 是从根节点开始定义，将根节点作为第 1 层，根的孩子节点作为第 2 层，以此类推，如果某个节点在第 i 层，则其孩子节点在第 i + 1 层。而父亲节点在同一层的节点互为 「堂兄弟节点」。树中所有节点最大的层数称为 「树的深度」 或 「树的高度」。树中，两个节点之间所经过节点序列称为 「路径」，两个节点之间路径上经过的边数称为 「路径长度」。

树的其他术语

节点的层次：从根节点开始定义，根为第 1 层，根的子节点为第 2 层，以此类推。
树的深度（高度）：所有节点中最大的层数。例如图中树的深度为 4。
堂兄弟节点：父节点在同一层的节点互为堂兄弟。例如图中 G、K 互为堂兄弟节点。
路径：树中两个节点之间所经过的节点序列。例如图中 E 到 G 的路径为 E - B - A - D - G。
路径长度：两个节点之间路径上经过的边数。例如图中 E 到 G 的路径长度为 444。
节点的祖先：从该节点到根节点所经过的所有节点，被称为该节点的祖先。例如图中 H 的祖先为 E、B、A。
节点的子孙：节点的子树中所有节点被称为该节点的子孙。例如图中 D 的子孙为 F、G、K。

1.3 树的分类

根据节点的子树是否可以互换位置，我们可以将树分为两种类型：「有序树」 和 「无序树」。

如果将树中节点的各个子树看做是从左到右是依次有序的（即不能互换），则称该树为 「有序树」。反之，如果节点的各个子树可以互换位置，则成该树为 「无序树」。

有序树：节点的各个⼦树从左⾄右有序，不能互换位置。
无序树：节点的各个⼦树可互换位置。

2. 二叉树简介

2.1 二叉树的定义

二叉树（Binary Tree）：树中各个节点的度不大于 2 个的有序树，称为二叉树。通常树中的分支节点被称为 「左子树」 或 「右子树」。二叉树的分支具有左右次序，不能随意互换位置。

下图就是一棵二叉树。

二叉树也可以使用递归方式来定义，即二叉树满足以下两个要求之一：

空树：二叉树是一棵空树。
非空树：二叉树是由一个根节点和两棵互不相交的子树 T₁、T₂，分别称为根节点的左子树、右子树组成的非空树；并且 T₁、T₂ 本身都是二叉树。

⼆叉树是种特殊的树，它最多有两个⼦树，分别为左⼦树和右⼦树，并且两个子树是有序的，不可以互换。也就是说，在⼆叉树中不存在度⼤于 2 的节点。

二叉树在逻辑上可以分为 5种基本形态，如下图所示。

2.2 特殊的二叉树

下面我们来介绍一些特殊的二叉树。

2.2.1 满二叉树

满二叉树（Full Binary Tree）：如果所有分支节点都存在左子树和右子树，并且所有叶子节点都在同一层上，则称该二叉树为满二叉树。

满二叉树满足以下特点：

叶子节点只出现在最下面一层。
非叶子节点的度一定为 2。
在同等深度的二叉树中，满二叉树的节点个数最多，叶子节点个数最多。

如果我们对满二叉树的节点进行编号，根结点编号为 1，然后按照层次依次向下，每一层从左至右的顺序进行编号。则深度为 k 的满二叉树最后一个节点的编号为 2_k - 1。

我们可以来看几个例子。

2.2.2 完全二叉树

完全二叉树（Complete Binary Tree）：如果叶子节点只能出现在最下面两层，并且最下层的叶子节点都依次排列在该层最左边的位置上，具有这种特点的二叉树称为完全二叉树。

完全二叉树满足以下特点：

叶子节点只能出现在最下面两层。
最下层的叶子节点一定集中在该层最左边的位置上。
倒数第二层如果有叶子节点，则该层的叶子节点一定集中在右边的位置上。
如果节点的度为 1，则该节点只偶遇左孩子节点，即不存在只有右子树的情况。
同等节点数的二叉树中，完全二叉树的深度最小。

完全二叉树也可以使用类似满二叉树的节点编号的方式来定义。即从根节点编号为 1 开始，按照层次从上至下，每一层从左至右进行编号。对于深度为 i 且有 n 个节点的二叉树，当且仅当每一个节点都与深度为 k 的满二叉树中编号从 1 至 n 的节点意义对应时，该二叉树为完全二叉树。

我们可以来看几个例子。

2.2.3 二叉搜索树

二叉搜索树（Binary Search Tree）：也叫做二叉查找树、有序二叉树或者排序二叉树。是指一棵空树或者具有下列性质的二叉树：

如果任意节点的左子树不为空，则左子树上所有节点的值均小于它的根节点的值。

如果任意节点的右子树不为空，则右子树上所有节点的值均大于它的根节点的值。

任意节点的左子树、右子树均为二叉搜索树。

如图所示，这 3 棵树都是二叉搜索树。

2.2.4 平衡二叉搜索树

平衡二叉搜索树（Balanced Binary Tree）：一种结构平衡的二叉搜索树。即叶节点高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉搜索树。平衡二叉树可以在 O(logn) 内完成插入、查找和删除操作。最早被发明的平衡二叉搜索树为 「AVL 树（Adelson-Velsky and Landis Tree））」。

AVL 树满足以下性质：

空二叉树是一棵 AVL 树。

如果 T 是一棵 AVL 树，那么其左右子树也是 AVL 树，并且 ∣h(ls)−h(rs)∣≤1，h(ls) 是左子树的高度，h(rs) 是右子树的高度。

AVL 树的高度为 O(logn)。

如图所示，前 2 棵树是平衡二叉搜索树，最后一棵树不是平衡二叉搜索树，因为这棵树的左右子树的高度差的绝对值超过了 1。

2.3 二叉树的存储结构

二叉树的存储结构分为两种：「顺序存储结构」和「链式存储结构」，下面进行一一讲解。

2.3.1 二叉树的顺序存储结构

其实，堆排序、优先队列中的二叉堆结构，采用的就是二叉树的顺序存储结构。

二叉树的顺序存储结构使用一维数组来存储二叉树中的节点，节点存储位置则采用完全二叉树的节点层次编号，按照层次从上至下，每一层从左至右的顺序依次存放二叉树的数据元素。在进行顺序存储时，如果对应的二叉树节点不存在，则设置为「空节点」。

下图为二叉树的顺序存储结构。

从图中我们也可以看出节点之间的逻辑关系。

如果某二叉树节点（非叶子节点）的下标为 i，那么其左孩子节点下标为 2∗i+1，右孩子节点下标为 2∗i+2。
如果某二叉树节点（非根结点）的下标为 i，那么其根节点下标为 (i−1)//2。// 表示整除。

对于完全二叉树（尤其是满二叉树）来说，采用顺序存储结构比较合适，它能充分利用存储空间；而对于一般二叉树，如果需要设置很多的「空节点」，则采用顺序存储结构就会浪费很多存储空间。并且，由于顺序存储结构固有的一些缺陷，会使得二叉树的插入、删除等操作不方便，效率也比较低。对于二叉树来说，当树的形态和大小经常发生动态变化时，更适合采用链式存储结构。

2.3.2 二叉树的链式存储结构

二叉树采用链式存储结构时，每个链节点包含一个用于数据域 val，存储节点信息；还包含两个指针域 left 和 right，分别指向左右两个孩子节点，当左孩子或者右孩子不存在时，相应指针域值为空。二叉链节点结构如下图所示。

二叉链节点

二叉链节点结构的对应代码为：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}