二叉树

定义

二叉树是树的一种，其节点最多只能含有两个孩子节点（左孩子和右孩子）。

术语和分类

严格二叉树（Strict/Proper Binary Tree）：所有节点只含有0个或者2个孩子节点

完全二叉树（Complete Binary Tree）：除了最后一层以外所有层的节点都必须填满，同时最后一层（叶子节点）向左对齐的树为完全二叉树。但是，完全二叉树不一定是严格二叉树。

完美二叉树（Perfect Binary Tree）: 除叶节点以外的所有节点都有两个孩子节点的二叉树称为完美二叉树

平衡二叉树：任意节点的左子树和右子树的高度差不大于 $K$ （通常 $K=1$）的树称为平衡二叉树。

二叉搜索树：一种特殊的二叉树，非常重要。

Attention

• 空树的高度为 $-1$，只有一个节点的树高度为$0$
• 一个节点的左右子树的根节点，是左右孩子，要注意计算左右子树的高度的时候，从左右孩子算起，而不是在自己这里算起。

一些例子

• 只有一个节点的树也是二叉树
• 类似一条边的树也是二叉树（所有非叶节点都只含有左孩子节点或者右孩子节点）
• 下图左一由于其最后一层节点没有左对齐，因此并不是完全二叉树；将节点左对齐可以变成完全二叉树，如中间图片所示；即使再添加一个节点，只要是左对齐的，也是完全二叉树（如下右图所示）

特点

• 第 $i$ 层最多含有 $2^i$ 个节点
• 对于高度为 $h$ 的完美二叉树，其共有 $2^{h+1}-1$ 个节点，即 $2^{\text{\#levels}}-1$ (levels比高度多1，高度是边，层数是节点)
• 对于节点数为 $n$ 的完全二叉树，它的最小高度为 $floor(lo{g}_{2}n)$
• 二叉树的操作成本往往和树的高度有关，因此人们都希望越小越小。

完全二叉树的实现

1. 动态的创建节点指针

class Nodes():
	def __init__(val = 0, left = None: Nodes, right = None: Nodes):
		self.val = val
		self.left = left
		self.right = right

2. 数组 跟堆的实现一样，如下

• 对于一个在 $\text{ind}=i$ 的节点，
  • 其左孩子索引为 ${\text{ind}}_{\text{left}}=2i+1$
  • 其右孩子索引为 ${\text{ind}}_{\text{right}}=2i+2$

Note

数组存储方式只适用于完全二叉树

二叉树的遍历

参见二叉树的遍历

二叉树问题的解题思路

参见 二叉树-解题思路