二叉树及其性质

二叉树是一种非常重要的树形数据结构，它的特点是每个节点最多有两个子节点。这两个子节点分别被称为 左子节点和 右子节点。二叉树被广泛应用于算法、数据存储和操作中，比如查找、排序和表达式解析等。

二叉树的定义

1. 节点：二叉树由一组节点组成。每个节点包含以下三部分：

   • 数据域：存储数据的部分。
   • 左子节点指针：指向当前节点的左子节点（如果没有左子节点，则为null）。
   • 右子节点指针：指向当前节点的右子节点（如果没有右子节点，则为null）。

2. 根节点：二叉树的最顶端节点称为根节点（Root）。每棵二叉树有且仅有一个根节点。

3. 空二叉树：如果一棵二叉树没有任何节点，则称为空二叉树。

4. 子树：对于二叉树中的任意一个节点，其左子节点可以看作是一个独立的二叉树，称为左子树；同理，右子节点是右子树。

二叉树的分类

1. 满二叉树：每一层的节点数都达到了最大值，即每个节点要么是叶子节点，要么有两个子节点。
2. 完全二叉树：除了最后一层，所有层的节点数都达到最大值，且最后一层的节点必须从左到右依次排列。
3. 二叉搜索树（BST）：对于任意一个节点，左子树的所有节点值小于当前节点值，右子树的所有节点值大于当前节点值。

二叉树的性质

• 性质1： 在二叉树的第 $i$ 层上至多有 $2^{i-1}$ （ $i\ge 1$ ） 个节点
• 性质2： 深度为 $k$ 的二叉树至多有 $2^k-1$ （ $k\ge 1$ ）个结点
• 性质3： 对任何一棵非空二叉树 $T$ ，如果其终端结点（叶子节点）数为 $n_0$ ，度为 $2$ 的结点数为 $n_2$ ，则 $n_0=n_2+1$
• 性质4： 具有 $n$ 个结点的完全二叉树的深度为 $\lfloor lo{g}_{2}n\rfloor +1$
• 性质5： 如果对一棵有 $n$ 个结点的完全二叉树（其深度为 $\lfloor lo{g}_{2}n\rfloor +1$ ）的结点按层序编号（从第 $1$ 层到第 $\lfloor lo{g}_{2}n\rfloor +1$ 层，每层从左到右），则对任一结点 $i$ （ $1\le i\le n$ ） ，以下结论成立：
  • 如果 $i=1$ ，则结点 $i$ 是二叉树的根，无双亲；如果 $i>1$ ，则其双亲 PARENT( $i$ ) 是结点 $\lfloor i/2\rfloor$
  • 如果 $2i>n$ ，则结点 $i$ 无左孩子(结点 $i$ 为叶子结点)；否则其左孩子LCHILD( $i$ )是结点 $2i$
  • 如果 $2i+1>n$ ，则结点 $i$ 无右孩子；否则其右孩子RCHILD( $i$ )是结点 $2i+1$

二叉树可视化示例

下面是一个简单的二叉树示例：

      1/ \2   3/ \   \4   5   6

• 节点1是根节点。
• 节点2是节点1的左子节点，节点3是节点1的右子节点。
• 节点4、5和6是叶子节点，因为它们没有子节点。