doc/二叉树.md at master

6.6 KiB

Raw Permalink Blame History

二叉树

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

1. 二叉树的基本性质

节点的度（Degree of a Node）: 节点的度是该节点的子节点数。在二叉树中，每个节点的度最多为2。
树的深度（Depth of a Tree）: 树的深度是指从树的根节点到最深叶子节点的最长路径上边的数量。
层次（Level）: 树中某个节点的层次由根节点开始计算，根节点的层次为1，其子节点的层次为2，以此类推。
叶子节点（Leaf Node）: 叶子节点是没有子节点的节点。在许多算法中，叶子节点的处理通常是终止条件之一。
满二叉树（Full Binary Tree）: 所有节点的度要么是0（叶子节点），要么是2。
完全二叉树（Complete Binary Tree）: 完全二叉树是一种特殊的二叉树，其中每一层除了最后一层之外都是满的，并且最后一层的所有节点尽可能地集中在最左边。

完全二叉树的示例：

2. 二叉树的表示方式

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

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。

顺序表示的示例：

       1
      / \
     2   3
    / \   \
   4   5   6

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

3. 二叉树的遍历

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

深度优先遍历（DFS）: 包括前序、中序、后序遍历，它们的区别在于根节点的访问顺序。
- 前序遍历（Preorder Traversal）: 根 → 左子树 → 右子树。
- 中序遍历（Inorder Traversal）: 左子树 → 根 → 右子树。
- 后序遍历（Postorder Traversal）: 左子树 → 右子树 → 根。
广度优先遍历（BFS）: 层序遍历是一种广度优先遍历方法，它逐层访问树的节点。

树的层序遍历：

        1
       / \
      2   3
     / \   \
    4   5   6

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

4. 二叉搜索树（BST）

二叉搜索树（Binary Search Tree）是一种特殊的二叉树，它具有以下性质：

对于每个节点，左子树中所有节点的值小于该节点的值，而右子树中所有节点的值大于该节点的值。
中序遍历BST会得到一个递增的有序序列。

二叉搜索树的基本操作

查找（Search）: 从根节点开始，如果目标值小于当前节点值，进入左子树；如果目标值大于当前节点值，进入右子树；如果目标值等于当前节点值，则查找成功。
插入（Insert）: 从根节点开始，根据值的大小决定插入位置。插入的新节点始终是叶子节点。

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;
}

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

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

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

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

霍夫曼树（Huffman Tree）: 霍夫曼树是一种用于数据压缩的二叉树。它是一棵加权路径长度最短的二叉树，通常用于霍夫曼编码。
二叉堆（Binary Heap）: 一种完全二叉树，通常用来实现优先队列。最常见的是最大堆（Max Heap）和最小堆（Min Heap），其中最大堆的每个节点都大于等于其子节点，最小堆则相反。

7. 二叉树的存储与实现

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

链式存储实现

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

顺序存储实现

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

6.6 KiB Raw Permalink Blame History Unescape Escape

二叉树