C++ 实现二叉树深入讲解

二叉树基础概念

二叉树定义

二叉树是一种每个节点最多有两个子节点的树状数据结构。这两个子节点分别被称为左子节点和右子节点。二叉树的节点结构通常包含数据域以及指向左右子节点的指针。在 C++ 中，可以通过结构体或类来定义二叉树节点。以下是一个简单的二叉树节点结构体定义：

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

在上述代码中，TreeNode 结构体包含一个整数类型的数据成员 val 用于存储节点的值，以及两个指针 left 和 right 分别指向左子节点和右子节点。构造函数 TreeNode(int x) 用于初始化节点的值，并将左右子节点指针初始化为 NULL。

二叉树的特殊类型

1. 满二叉树：每一个节点要么有两个子节点，要么没有子节点，即所有的叶子节点都在同一层，并且除叶子节点外每个节点都有两个子节点。例如，深度为 3 的满二叉树如下：

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

2. 完全二叉树：对于一棵具有 n 个节点的二叉树，按层序编号，如果编号为 i（1 <= i <= n）的节点与同样深度的满二叉树中编号为 i 的节点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。例如：

        1
      /   \
     2     3
    / \   /
   4   5 6

此为一棵完全二叉树，而如果节点 6 的位置在节点 5 的右子节点位置，就不是完全二叉树了。

3. 平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的主要目的是为了减少二叉查找树的深度，提高查找效率。例如：

        3
      /   \
     1     5
    / \   / \
   0   2 4   6

这是一棵平衡二叉树，因为每个节点的左右子树高度差的绝对值都不超过 1。

二叉树的遍历

深度优先遍历

1. 前序遍历：先访问根节点，然后递归地前序遍历左子树，最后递归地前序遍历右子树。前序遍历的顺序是根 - 左 - 右。以下是使用 C++ 实现二叉树前序遍历的递归代码：

void preorderTraversal(TreeNode* root) {
    if (root) {
        std::cout << root->val << " ";
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

假设我们有如下二叉树：

        1
      /   \
     2     3
    / \
   4   5

前序遍历的结果将是 1 2 4 5 3。

2. 中序遍历：先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。中序遍历的顺序是左 - 根 - 右。对于二叉查找树，中序遍历会得到一个有序的序列。以下是 C++ 实现代码：

void inorderTraversal(TreeNode* root) {
    if (root) {
        inorderTraversal(root->left);
        std::cout << root->val << " ";
        inorderTraversal(root->right);
    }
}

对于上述二叉树，中序遍历的结果将是 4 2 5 1 3。

3. 后序遍历：先递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问根节点。后序遍历的顺序是左 - 右 - 根。常用于释放二叉树的内存。以下是 C++ 实现代码：

void postorderTraversal(TreeNode* root) {
    if (root) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        std::cout << root->val << " ";
    }
}

对于上述二叉树，后序遍历的结果将是 4 5 2 3 1。

广度优先遍历（层序遍历）

广度优先遍历是按照树的层次依次访问节点。从根节点开始，先访问第一层，再访问第二层，以此类推。通常使用队列来实现层序遍历。以下是 C++ 实现代码：

#include <queue>
void levelOrderTraversal(TreeNode* root) {
    if (!root) return;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        std::cout << node->val << " ";
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

对于前面的二叉树，层序遍历的结果将是 1 2 3 4 5。

二叉树的操作

创建二叉树

可以通过多种方式创建二叉树，常见的是根据前序遍历和中序遍历的结果来创建二叉树。前序遍历的第一个元素是根节点的值，在中序遍历中找到这个值，其左边的元素是左子树的中序遍历结果，右边的元素是右子树的中序遍历结果。然后根据左子树和右子树中序遍历结果的长度，可以确定前序遍历中左子树和右子树的前序遍历部分。以下是实现代码：

TreeNode* buildTree(std::vector<int>& preorder, std::vector<int>& inorder) {
    if (preorder.empty() || inorder.empty()) return nullptr;
    int rootVal = preorder[0];
    TreeNode* root = new TreeNode(rootVal);
    int inorderIndex = 0;
    for (; inorderIndex < inorder.size(); ++inorderIndex) {
        if (inorder[inorderIndex] == rootVal) break;
    }
    std::vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + inorderIndex + 1);
    std::vector<int> leftInorder(inorder.begin(), inorder.begin() + inorderIndex);
    std::vector<int> rightPreorder(preorder.begin() + inorderIndex + 1, preorder.end());
    std::vector<int> rightInorder(inorder.begin() + inorderIndex + 1, inorder.end());
    root->left = buildTree(leftPreorder, leftInorder);
    root->right = buildTree(rightPreorder, rightInorder);
    return root;
}

计算二叉树的高度

二叉树的高度是从根节点到最远叶子节点的最长路径上的节点数。可以通过递归的方式计算。如果根节点为空，高度为 0，否则高度为左子树高度和右子树高度的最大值加 1。以下是 C++ 实现代码：

int treeHeight(TreeNode* root) {
    if (!root) return 0;
    int leftHeight = treeHeight(root->left);
    int rightHeight = treeHeight(root->right);
    return std::max(leftHeight, rightHeight) + 1;
}

判断二叉树是否平衡

根据平衡二叉树的定义，我们可以通过计算每个节点的左右子树高度差来判断二叉树是否平衡。如果任意节点的左右子树高度差的绝对值超过 1，则二叉树不平衡。为了提高效率，我们可以在计算高度的同时判断是否平衡。以下是实现代码：

bool isBalanced(TreeNode* root, int& height) {
    if (!root) {
        height = 0;
        return true;
    }
    int leftHeight, rightHeight;
    bool leftBalanced = isBalanced(root->left, leftHeight);
    bool rightBalanced = isBalanced(root->right, rightHeight);
    height = std::max(leftHeight, rightHeight) + 1;
    return leftBalanced && rightBalanced && std::abs(leftHeight - rightHeight) <= 1;
}
bool isBalanced(TreeNode* root) {
    int height;
    return isBalanced(root, height);
}

查找二叉树中的节点

在二叉树中查找特定值的节点，可以使用递归的方式。从根节点开始，如果根节点的值等于要查找的值，则返回根节点；否则，分别在左子树和右子树中查找。以下是 C++ 实现代码：

TreeNode* findNode(TreeNode* root, int target) {
    if (!root) return nullptr;
    if (root->val == target) return root;
    TreeNode* leftResult = findNode(root->left, target);
    if (leftResult) return leftResult;
    return findNode(root->right, target);
}

二叉树的删除

删除二叉树中的节点相对复杂。首先要找到要删除的节点，然后根据节点的不同情况进行处理：

1. 如果要删除的节点是叶子节点，直接删除该节点。
2. 如果要删除的节点只有一个子节点，将该节点的父节点指向其子节点。
3. 如果要删除的节点有两个子节点，可以用其右子树的最小节点（即右子树最左节点）或左子树的最大节点（即左子树最右节点）代替该节点，然后删除替代节点。以下是实现代码：

TreeNode* findMin(TreeNode* node) {
    while (node->left) {
        node = node->left;
    }
    return node;
}
TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return root;
    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    } else {
        if (!root->left) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        } else if (!root->right) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        } else {
            TreeNode* temp = findMin(root->right);
            root->val = temp->val;
            root->right = deleteNode(root->right, temp->val);
        }
    }
    return root;
}

二叉查找树（BST）

二叉查找树定义

二叉查找树是一种特殊的二叉树，对于树中的每个节点 x，其左子树中的所有键值都小于 x 的键值，而其右子树中的所有键值都大于 x 的键值。这一性质使得二叉查找树在查找、插入和删除操作上具有较好的性能。例如：

        5
      /   \
     3     7
    / \   / \
   2   4 6   8

这是一棵二叉查找树，每个节点都满足上述性质。

二叉查找树的操作

1. 插入操作：从根节点开始，如果插入值小于当前节点值，则向当前节点的左子树插入；如果大于当前节点值，则向当前节点的右子树插入。如果遇到空节点，则在该位置插入新节点。以下是 C++ 实现代码：

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

2. 查找操作：从根节点开始，如果查找值等于当前节点值，则找到；如果小于当前节点值，则在左子树查找；如果大于当前节点值，则在右子树查找。如果遍历到空节点还未找到，则表示不存在该值。以下是 C++ 实现代码：

bool search(TreeNode* root, int val) {
    if (!root) return false;
    if (root->val == val) return true;
    if (val < root->val) return search(root->left, val);
    return search(root->right, val);
}

3. 删除操作：与普通二叉树删除操作类似，但利用二叉查找树的性质可以更高效地实现。首先找到要删除的节点，如果该节点是叶子节点，直接删除；如果只有一个子节点，将其父节点指向其子节点；如果有两个子节点，用其右子树的最小节点（或左子树的最大节点）代替它，然后删除替代节点。以下是 C++ 实现代码：

TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return root;
    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    } else {
        if (!root->left) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        } else if (!root->right) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        } else {
            TreeNode* temp = findMin(root->right);
            root->val = temp->val;
            root->right = deleteNode(root->right, temp->val);
        }
    }
    return root;
}

二叉树的应用

表达式树

表达式树是一种用于表示数学表达式的二叉树。运算符作为内部节点，操作数作为叶子节点。例如，表达式 (3 + 4) * 2 可以表示为如下表达式树：

          *
        /   \
       +     2
      / \
     3   4

通过遍历表达式树可以实现表达式的求值。例如，后序遍历表达式树可以得到后缀表达式（逆波兰表达式），从而方便地进行求值。以下是一个简单的表达式树求值示例代码：

int evaluateExpressionTree(TreeNode* root) {
    if (!root->left &&!root->right) {
        return root->val;
    }
    int leftVal = evaluateExpressionTree(root->left);
    int rightVal = evaluateExpressionTree(root->right);
    if (root->val == '+') return leftVal + rightVal;
    if (root->val == '-') return leftVal - rightVal;
    if (root->val == '*') return leftVal * rightVal;
    if (root->val == '/') return leftVal / rightVal;
    return 0;
}

霍夫曼树

霍夫曼树是一种带权路径长度最短的二叉树，常用于数据压缩。给定一组字符及其出现的频率，霍夫曼树通过合并频率最小的节点来构建。具体步骤如下：

1. 将每个字符及其频率作为一个单独的节点。
2. 选择频率最小的两个节点，合并成一个新节点，其频率为这两个节点频率之和。
3. 将新节点放回节点集合，重复步骤 2，直到只剩下一个节点，即霍夫曼树的根节点。 以下是一个简单的霍夫曼树构建示例代码（简化实现，仅演示原理）：

struct HuffmanNode {
    char data;
    int freq;
    HuffmanNode* left;
    HuffmanNode* right;
    HuffmanNode(char c, int f) : data(c), freq(f), left(nullptr), right(nullptr) {}
};
struct CompareNodes {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    }
};
HuffmanNode* buildHuffmanTree(std::vector<char>& chars, std::vector<int>& freqs) {
    std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, CompareNodes> pq;
    for (size_t i = 0; i < chars.size(); ++i) {
        pq.push(new HuffmanNode(chars[i], freqs[i]));
    }
    while (pq.size() > 1) {
        HuffmanNode* left = pq.top(); pq.pop();
        HuffmanNode* right = pq.top(); pq.pop();
        HuffmanNode* parent = new HuffmanNode('\0', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    return pq.top();
}

二叉堆

二叉堆是一种特殊的完全二叉树，分为最大堆和最小堆。最大堆中每个节点的值都大于或等于其子节点的值，最小堆中每个节点的值都小于或等于其子节点的值。二叉堆常用于实现优先队列。以下是一个简单的最大堆实现代码：

class MaxHeap {
private:
    std::vector<int> heap;
    void heapify(int index) {
        int largest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        if (left < heap.size() && heap[left] > heap[largest]) {
            largest = left;
        }
        if (right < heap.size() && heap[right] > heap[largest]) {
            largest = right;
        }
        if (largest != index) {
            std::swap(heap[index], heap[largest]);
            heapify(largest);
        }
    }
public:
    void push(int val) {
        heap.push_back(val);
        int index = heap.size() - 1;
        while (index > 0 && heap[(index - 1) / 2] < heap[index]) {
            std::swap(heap[(index - 1) / 2], heap[index]);
            index = (index - 1) / 2;
        }
    }
    int pop() {
        if (heap.empty()) return -1;
        int top = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        heapify(0);
        return top;
    }
};

二叉树的优化与扩展

平衡二叉树的优化

1. AVL 树：AVL 树是一种高度平衡的二叉查找树，它在插入和删除操作后通过旋转操作来保持平衡。旋转操作分为左旋、右旋、左右旋和右左旋。例如，当插入节点导致某个节点的左右子树高度差为 2 时，根据不同情况进行相应的旋转操作。以下是 AVL 树插入操作的部分代码（仅演示右旋操作）：

TreeNode* rightRotate(TreeNode* y) {
    TreeNode* x = y->left;
    TreeNode* T2 = x->right;
    x->right = y;
    y->left = T2;
    return x;
}
TreeNode* insertAVL(TreeNode* root, int key) {
    if (!root) return new TreeNode(key);
    if (key < root->val) {
        root->left = insertAVL(root->left, key);
    } else {
        root->right = insertAVL(root->right, key);
    }
    int balance = getBalance(root);
    if (balance > 1 && key < root->left->val) {
        return rightRotate(root);
    }
    // 其他旋转情况类似处理
    return root;
}

2. 红黑树：红黑树也是一种自平衡二叉查找树，它通过节点颜色标记和一些规则来保持平衡。红黑树的节点有两种颜色：红色或黑色，并且满足以下规则：
   • 每个节点要么是红色，要么是黑色。
   • 根节点是黑色。
   • 每个叶子节点（NIL 节点，空节点）是黑色。
   • 如果一个节点是红色，那么它的两个子节点都是黑色。
   • 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。 红黑树在插入和删除操作后的调整相对复杂，但整体性能较为稳定，常用于实现 C++ 的 std::map 和 std::set 等数据结构。

多路查找树

1. B 树：B 树是一种多路平衡查找树，常用于文件系统和数据库索引。B 树的每个节点可以有多个子节点和多个键值。与二叉查找树不同，B 树的节点可以存储多个数据元素，并且子节点数量也相应增加。例如，一个 m 阶 B 树，每个非叶子节点至少有 ceil(m/2) 个子节点，最多有 m 个子节点。B 树的插入和删除操作涉及节点的分裂和合并，以保持树的平衡。
2. B+ 树：B+ 树是 B 树的一种变体，主要用于数据库系统。B+ 树的所有数据都存储在叶子节点，内部节点仅用于索引。叶子节点之间通过双向链表连接，这使得范围查询更加高效。例如，在数据库的索引结构中，B+ 树可以快速定位到某个范围内的数据记录。

通过以上对 C++ 实现二叉树的深入讲解，涵盖了二叉树的基本概念、遍历、操作、特殊类型以及应用和优化扩展等方面，希望能帮助读者全面掌握二叉树相关知识及其在 C++ 中的实现。