### 二叉树

二叉树是一种基础的数据结构，因其简单性和应用的广泛性，深入理解二叉树是掌握许多高级数据结构和算法的基础。以下是对二叉树及其相关知识的更深入讲解。

#### 1. 二叉树的基本性质

- **节点的度（Degree of a Node）**: 节点的度是该节点的子节点数。在二叉树中，每个节点的度最多为2。
  
- **树的深度（Depth of a Tree）**: 树的深度是指从树的根节点到最深叶子节点的最长路径上边的数量。

- **层次（Level）**: 树中某个节点的层次由根节点开始计算，根节点的层次为1，其子节点的层次为2，以此类推。

- **叶子节点（Leaf Node）**: 叶子节点是没有子节点的节点。在许多算法中，叶子节点的处理通常是终止条件之一。

- **满二叉树（Full Binary Tree）**: 所有节点的度要么是0（叶子节点），要么是2。

- **完全二叉树（Complete Binary Tree）**: 完全二叉树是一种特殊的二叉树，其中每一层除了最后一层之外都是满的，并且最后一层的所有节点尽可能地集中在最左边。

```markdown
完全二叉树的示例：
```

```plaintext
        1
       / \
      2   3
     / \  /
    4  5 6
```

#### 2. 二叉树的表示方式

- **链式表示（Linked Representation）**: 每个节点包含数据元素和指向其左、右子节点的指针。它非常灵活，可以处理动态增长的树。

```cpp
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
```

- **顺序表示（Sequential Representation）**: 使用数组存储二叉树节点。对于节点在数组中的位置`i`，其左子节点在位置`2*i + 1`，右子节点在位置`2*i + 2`。

```markdown
顺序表示的示例：
```

```plaintext
       1
      / \
     2   3
    / \   \
   4   5   6

数组表示：[1, 2, 3, 4, 5, null, 6]
```

#### 3. 二叉树的遍历

遍历是指按照某种顺序访问二叉树的所有节点。遍历方式分为深度优先遍历（DFS）和广度优先遍历（BFS）。

- **深度优先遍历（DFS）**: 包括前序、中序、后序遍历，它们的区别在于根节点的访问顺序。
  
  - **前序遍历（Preorder Traversal）**: 根 → 左子树 → 右子树。
  
  - **中序遍历（Inorder Traversal）**: 左子树 → 根 → 右子树。

  - **后序遍历（Postorder Traversal）**: 左子树 → 右子树 → 根。

- **广度优先遍历（BFS）**: 层序遍历是一种广度优先遍历方法，它逐层访问树的节点。

```markdown
树的层序遍历：
```

```plaintext
        1
       / \
      2   3
     / \   \
    4   5   6

层序遍历顺序：[1, 2, 3, 4, 5, 6]
```

#### 4. 二叉搜索树（BST）

二叉搜索树（Binary Search Tree）是一种特殊的二叉树，它具有以下性质：
- 对于每个节点，左子树中所有节点的值小于该节点的值，而右子树中所有节点的值大于该节点的值。
- 中序遍历BST会得到一个递增的有序序列。

##### 二叉搜索树的基本操作

1. **查找（Search）**: 从根节点开始，如果目标值小于当前节点值，进入左子树；如果目标值大于当前节点值，进入右子树；如果目标值等于当前节点值，则查找成功。

2. **插入（Insert）**: 从根节点开始，根据值的大小决定插入位置。插入的新节点始终是叶子节点。

```cpp
TreeNode* insert(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val < root->val) 
        root->left = insert(root->left, val);
    else 
        root->right = insert(root->right, val);
    return root;
}
```

3. **删除（Delete）**: 删除节点后，需要调整树的结构以保持BST的性质。删除节点有三种情况：
   - 叶子节点：直接删除。
   - 有一个子节点：用该子节点代替删除的节点。
   - 有两个子节点：找到右子树中的最小节点，替换要删除的节点，然后删除该最小节点。

```cpp
TreeNode* deleteNode(TreeNode* root, int val) {
    if (!root) return nullptr;
    if (val < root->val) 
        root->left = deleteNode(root->left, val);
    else if (val > root->val) 
        root->right = deleteNode(root->right, val);
    else {
        if (!root->left) return root->right;
        if (!root->right) return root->left;
        TreeNode* minNode = findMin(root->right);
        root->val = minNode->val;
        root->right = deleteNode(root->right, minNode->val);
    }
    return root;
}

TreeNode* findMin(TreeNode* root) {
    while (root->left) root = root->left;
    return root;
}
```

#### 5. 平衡二叉树（Balanced Binary Tree）

平衡二叉树是一种特殊的二叉搜索树，左右子树的高度差不超过1。常见的平衡二叉树包括以下几种：

- **AVL树**: 通过旋转操作来保持平衡的二叉搜索树。插入和删除操作后，AVL树会进行调整，使得任意节点的左右子树高度差不超过1。

- **红黑树**: 一种自平衡二叉搜索树，具有五条性质：
  1. 节点是红色或黑色。
  2. 根节点是黑色。
  3. 所有叶子节点（`null`节点）是黑色。
  4. 如果一个节点是红色，那么它的两个子节点都是黑色（即不能有两个连续的红色节点）。
  5. 从任一节点到其每个叶子的所有路径包含相同数目的黑色节点。

#### 6. 二叉树的高级应用

- **表达式树（Expression Tree）**: 使用二叉树表示算术表达式。叶子节点表示操作数，内部节点表示操作符。可以通过树的遍历顺序来实现表达式的前缀、中缀和后缀表示。

```markdown
表达式：((a + b) * (c - d)) 可以表示为：
```

```plaintext
        *
       / \
      +   -
     / \ / \
    a  b c  d
```

- **霍夫曼树（Huffman Tree）**: 霍夫曼树是一种用于数据压缩的二叉树。它是一棵加权路径长度最短的二叉树，通常用于霍夫曼编码。

- **二叉堆（Binary Heap）**: 一种完全二叉树，通常用来实现优先队列。最常见的是最大堆（Max Heap）和最小堆（Min Heap），其中最大堆的每个节点都大于等于其子节点，最小堆则相反。

#### 7. 二叉树的存储与实现

二叉树可以通过链式存储和顺序存储来实现。链式存储适用于一般的二叉树和动态数据结构，顺序存储则更适合完全二叉树。

##### 链式存储实现

```cpp
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
```

##### 顺序存储实现

```cpp
// 顺序存储的数组表示
vector<int> binaryTree = {1, 2, 3, 4, 5, 6, 7};
```