二叉树

定义

二叉树（Binary Tree）是一种树形数据结构，其中每个节点最多有两个子节点，通常被称为左子节点和右子节点。

基本术语

1. 根节点（Root Node）：二叉树的起始节点。

2. 子节点（Child Node）：每个节点可以有两个子节点，分别是左子节点和右子节点。

3. 父节点（Parent Node）：一个节点的直接上层节点。

4. 兄弟节点（Sibling Nodes）：具有相同父节点的节点。

5. 叶子节点（Leaf Node）：没有子节点的节点，也称为终端节点。

6. 内部节点（Internal Node）：不是叶子节点的节点，至少有一个子节点。

7. 深度（Depth）：从根节点到某个节点的最长路径上的节点数（根节点的深度为1）。

8. 高度（Height）：从根节点到最远叶子节点的最长路径上的节点数减一（根节点的高度为0，如果树为空，高度为-1）。

性质

1. 递归定义：二叉树本身可以递归地定义为由一个根节点、左子树和右子树组成，其中左子树和右子树也是二叉树。

2. 唯一性：对于给定的节点序列，如果以不同的方式插入节点，可能会形成不同的二叉树结构。

类型

1. 完全二叉树（Complete Binary Tree）：除了最后一层外，每一层都是满的，且最后一层的节点都靠左对齐。

2. 满二叉树（Full Binary Tree）：除了叶子节点外，每个节点都有两个子节点。满二叉树一定是完全二叉树。

3. 平衡二叉树（Balanced Binary Tree）：一个二叉树，其中任意节点的两个子树的高度差最多为1。

4. 搜索二叉树（Binary Search Tree, BST）：满足以下性质的二叉树：对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值，其右子树中的所有节点的值都大于该节点的值。