二叉树

树(Tree) link

graph TB
subgraph Tree
  direction TB
  A((0))-->B((1))
  A-->C((2))
  A-->D((3))
  B-->E((4))
  B-->F((5))
  B-->G((6))
  C-->H((7))
  D-->I((8))
  D-->J((9))
end

对于树我们关注以下几个概念：

• 根节点(root node)：树中最顶层的节点。
• 内部节点(internal node)：至少一个子节点的节点。
• 叶子节点(leaf node)：没有子节点的节点。
• 节点的深度(depth of a node)：从节点到根节点的边数。也称节点层级，根节点的深度为0。
• 树的高度(height of a tree)：最深层叶子节点到根节点的节点个数(包含叶子节点和根节点)。

树的性质 link

• 节点个数等于所有节点度数和加1，即$m$叉树满足$n=1+\sum_{x=1}^{m}xn_{x}$。
• 具有$n$个节点的$m$叉树最小高度为$\log_m{n(m-1)+1}$，最大高度为$n-(m-1)$。
• 高度为$h$的$m$叉树至多有$\frac{m^{h}-1}{m-1}$个节点, 第$i$层至多有$m^{i-1}$个节点。

二叉树(Binary Tree) link

graph TB;
subgraph Perfect Binary Tree
  direction TB
  A((0))-->B((1))
  A-->C((2));
  B-->E((3))
  B-->F((4))
  C-->H((5))
  C-->I((6))
end

内部节点都包含两个子节点，叶子节点全部排列在最后一层的树称为完美二叉树(Perfect Binary Tree)。

graph TB
subgraph Full Binary Tree;
  direction TB
  A1((0))-->B1((1))
  A1-->C1((2))
  B1-->E1((3))
  B1-->F1((4))
end

subgraph Complete Binary Tree;
  direction TB
  A2((0))-->B2((1))
  A2-->C2((2))
  B2-->E2((3))
  B2-->F2((4))
  C2-->H2((5))
end

没有只有一个子节点的节点的树称为满二叉树(Full Binary Tree)。除最后一层外每层填充最大元素个数$2^L$，最后一层节点尽可能从左往右填充的树称为完全二叉树(Complete Binary Tree)。

graph TB
subgraph Balanced Binary Tree
  direction TB
  A((3))-->B((9))
  A-->C((20))
  C-->D((15))
  C-->E((7))
end

平衡因子即左右子树高度差的绝对值, 左右子树的平衡因子小于或等于1的树称为平衡二叉树(Balanced Binary Tree)。

二叉树的性质 link

设$n_x$表示带有$x$个子节点的节点的个数，$N$表示节点总数，$H$表示树的高度。
二叉树具有如下性质：

• 二叉树的$L$层级至多$2^L$。
• $n_0=n_2+1$。
• 节点总数$N$的上界为$2^{H}-1$。
• 树的高度$H$的下界为$\log_{2} (N+1)$。
• 树的级别个数的下界为$|\log_{2} n_0|+1$。

完全二叉树被称为所有叶子节点深度相等的真二叉树，它额外具备以下性质：

• $N$为偶数时$n_0=1$，$N$为奇数时$n_0=0$，可根据前一条性质推导出$n_0$和$n_2$。
• $H=\log_2{(N+1)}$
• 若节点的层序编号为$i$，其父节点编号为$\frac{i-1}{2}$(从1开始$\frac{i}{2}$),左子节点编号为$2i+1$(从1开始$2i$)，右子节点编号为$2i+2$(从1开始$2i+1$)

二叉树的遍历 link

二叉树几乎所有的操作都是节点遍历开展的，二叉树的遍历分为前序遍历、中序遍历和后序遍历：

• 前序遍历(pre-order)：先访问当前节点数据，再访问左子树的数据，最后访问右子树的数据。
• 中序遍历(in-order)：先访问左子树的数据，再访问当前节点数据，最后访问右子树的数据。
• 后序遍历(post-order)：先访问左子树的数据，再访问右子树的数据，最后访问当前节点数据。
• 层序遍历(level-order)：自上而下一层层访问，每层从左往右访问节点数据。

graph TB
  A((0))-->B((1))
  A-->C((2));
  B-->E((3))
  B-->F((4))
  C-->H((5))
  C-->I((6))

二叉树的插入和删除 link

往二叉树插入和删除元素不需要考虑对二叉树遍历结果的影响，但要保持二叉树的结构。

• 插入操作即层序遍历树中寻找第一个子节点为空的节点进行插入，按照惯例优先设置左节点。
• 删除操作即使用层序遍历最后一个节点对待删节点进行覆盖后再删除该节点。

二叉树的(反)序列化 link

任何二叉树的中序遍历与前序遍历、后续遍历和层序遍历的任一组合可以完整确定一棵二叉树。

• 若已知先序遍历，先序遍历中的节点的左子树在一定在中序遍历中元素的左边，节点的右子树在一定在中序遍历中元素的右边。

通过层序遍历及各节点父节点索引可以完整确定一棵二叉树，序列化时二叉树有两种表示方法：

• 将二叉树补全为完全二叉树，按完全二叉树的规格遍历节点并保存到数组中，针对补全的节点则使用null进行存储，数组后面连续的null可以忽略。
• 二叉树进行层序遍历并跟踪对应的父节点坐标，最终遍历结果连同父节点坐标保存到数组中。

完全二叉树可以通过层序遍历进行序列化与反序列化。

二叉树的封装 link