二叉树

2021-12-04

树的定义

树是一种数据结构，它是由 n（$n\geq 0$）个有限节点组成一个具有层次关系的集合。当n=0时，称为空树。之所以叫做树是因为他看起来像一棵倒挂的树，根朝上，叶朝下的树。在任意非空树中具有以下特点：

每个节点有零个或多个子节点；
没有父节点的节点称为根节点；
每一个非根节点有且只有一个父节点；
除了根节点外，每个子节点可以分为多个不相交的子树。

tree-01

树的基本术语

若一个节点有子树，那么该节点称为子树根的“双亲”，子树的根是该节点的“孩子”。有相同双亲的节点互为“兄弟”。一个节点的所有子树上的任何节点都是该节点的后裔。从根节点到某个节点的路径上的所有节点都是该节点的祖先

节点的度：节点拥有的子树的数目，图中节点C的度为2。

叶子：度为零的节点，图中D、E、F都是叶子几点。

树的度：树中节点的最大的度，图中节点C 的度最大为2，因此树的度为2。

层次：根节点的层次为1，其余节点的层次等于该节点的双亲节点的层次加1。

树的高度：树中节点的最大层次，图中树的高度为3。

无序树：如果树中节点的各子树之间的次序是不重要的，可以交换位置。

有序树：如果树中节点的各子树之间的次序是重要的，不可以交换位置。

森林：0个或多个不相交的树组成。对森林加上一个根，森林即成为树；删去根，树即成为森林。

二叉树的定义

二叉树是每个节点最多有两个子树的树结构。他有五种基本形态：二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。

tree-02

二叉树的性质

性质1：二叉树第i层上的节点数目最多为 2^{$i-1$}($i \geq 1$)

tree-03

性质2：深度为K 的二叉树至多有 $2^{k}-1$ 个节点（$k\geq1$）

tree-04

性质3：包含n个节点的二叉树的高度至少为 $\log_2(n+1)$。

性质4：二叉树中，设叶子节点数为 n₀，度为2 的节点数为 n₂，则 $n_0=n_2+1$。

tree-06

不同形态二叉树

满二叉树

定义：高度为 h，并且由 $2^h-1$ 个节点的二叉树，被称为满二叉树，满二叉树的结点要么为0（叶子节点），要么为2（非叶子节点）

tree-07

完全二叉树

定义：一棵二叉树中，只有最下面两层节点的度可以小于2，并且最下一层的叶子节点集中靠左的若干位置上。这样的二叉树成为完全二叉树

特点：叶子节点只能出现在最下层和次下层，且最下层的叶子节点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。

tree-08

二叉树的物理存储结构

二叉树可以用以下两种物理存储结构来表达：

链式存储结构
数组

链式存储结构

tree-11

二叉树每个节点得组成分为三个部分，：

存储数据得data变量
指向左孩子得 left 指针
指向右孩子得 right 指针

数组

使用数组存储时，按照层级顺序把二叉树得节点放到数组中对应得位置上。如果某一节点得左孩子或右孩子空缺，则数组的相应位置也空出来。

为什么这样设计呢？

因为这样设计可以更方便地在数组中定位二叉树的孩子节点和父节点。

假设一个父节点的下标是parent，那么它的左孩子节点下标就是 $2\times parent+1$; 右孩子节点下标就是 $2 \times parent+2$。

假如节点4在数组中的下标是3，节点4是节点2的左孩子，节点2的下标可以直接通过计算得出。

节点2的下标 = $(3-1)/2 = 1$

注意：对于一个稀疏的二叉树来说，用数组来表示是非常浪费空间的。

tree-10

二叉树的遍历

在计算机程序中，遍历本就是一个线性的操作。所以遍历同样具有线性结构的数组或链表，是一件轻而易举的事情。

二叉树是典型的非线性数据结构，遍历时需要把非线性关联的节点转化成一个线性队列，以不同的方式来遍历，遍历出的序列顺序也不同。

二叉树的遍历方式：

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

从宏观的角度来分，二叉树的遍历又可以分为两大类：

深度优先遍历（前序遍历、中序遍历、后序遍历）
广度优先遍历（层序遍历）

深度优先遍历

前序遍历

二叉树的前序遍历，输出顺序的是根节点、左子树、右子树。

中序遍历

二叉树的中序遍历，输出顺序的是左子树、根节点、右子树。

后序遍历

二叉树的后序遍历，输出顺序的是左子树、右子树、根节点。

广度优先遍历

层序遍历

二叉树的层序遍历就是按照从根节点到叶子节点的层次关系，一层一层横向遍历各个节点。

总结

在二叉树中：

若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
任意节点的左、右子树也分别为二叉查找树；
没有键值相等的节点。

二叉查找树

定义：二叉查找树(Binary Search Tree)，又被成为二叉搜索树。其特点如下：设 x 为二叉查找树中的一个节点， x 节点包含关键字key，一句话就是左孩子比父节点小，右孩子比父节点大，还有一个特性就是中序遍历可以让节点有序。

tree-09

二叉搜索树可以方便的实现搜索算法。在搜索元素x的时候，我们可以将x和根节点比较:

如果x等于根节点，那么找到x，停止搜索 (终止条件)
如果x小于根节点，那么搜索左子树
如果x大于根节点，那么搜索右子树

二叉搜索树所需要进行的操作次数最多与树的深度相等。n个节点的二叉搜索树的深度最多为n，最少为log(n)。

二叉查找树的查询复杂度为：$Olog_2(n)$~$O(n)$

二叉查找树的特性：

左子树上所有的节点的值均小于等于它的根节点的值。
右子树上所有节点的值均大于或等于它的根节点的值。
左右子树也分为二叉排序树

缺点：

因为其特性，当依次插入降序或者升序的数据时，此时的二叉树出现不平衡的状况（如下图）。如果每一层只有一个节点，则树的状态更倾向于线性结构。节点的查询类似于数组的遍历，因此查询复杂度为 $O(n)$

tree-12

构造的复杂度

二叉搜索树的构造过程，就是将节点不断插入到树中适当位置的过程。该操作过程，与查询节点元素的操作基本相同，不同在于：

查询节点过程：比较元素值是否相等，如果相等则返回，不相等则判断大小情况，迭代查询左、右子树，直到找到相等的元素，或子节点为空，返回节点不存在。
插入节点的过程是，比较元素值是否相等，相等则返回，表示已存在，不相等则判断大小，迭代查询左、右子树，直到找到相等的元素，或子节点为空，则将节点插入该空节点位置。

由此可知，单个节点的构造复杂度和查询复杂度相同。

删除复杂度

二叉搜索树的节点删除包括两个过程，查找和删除。

节点删除有以下三种情况：

待删除节点为叶子节点；
待删除节点度为一；（即待删除节点有一个子节点）
待删除节点度为二；（待删除节点有两个子节点，待删除节点有子树）

在第一种情况下，如下图，删除节点5时，会向下查找，此时节点5并没有子节点或者子树。删除后不影响树的结构特性，可以直接删除

tree-13

在第二种情况下，要删除节点4，而节点4存在一个子节点。因为需要维护二叉查找树的结构特征，需要将节点4的子节点8上移到删除的位置上。如下图

tree-14

情况三稍微复杂，删除的节点 2 既有左子树也有右子树，通常做法是，从待删除节点的右子树中查找最小的节点来补充删除节点的位置。

tree-15

由以上三种情况可知：

前两种情况下，删除节点后，“稳定结构”操作的复杂度都是常数级别，即整个的节点删除操作复杂度为 $Olog_2(n)$~$O(n)$
第三种情况下，设删除的节点为 $p$ ，“稳定结构”操作需要查找 $p$ 节点左子树中的最大值，也就是左子树中最“右”的叶子结点，即“稳定结构”操作其实也是一种内部的查询操作，所以整个的节点删除操作其实就是两个层次的查询操作，复杂度同为 $Olog_2(n)$~$O(n)$