C++实现二叉树及堆的示例代码

前言

二叉树和堆经常被放在同一章讲，因为它们都呈现「一个节点最多两个孩子」的形状，但两者的约束完全不同。二叉树只要求每个节点至多两个子节点，节点之间没有大小关系；堆在此之上还要求「父节点不大于（或不小于）两个孩子」，并且整棵树必须是完全二叉树，这样才能用数组紧凑存储。堆不是二叉搜索树，兄弟节点之间没有顺序，中序遍历也不会得到有序序列。

另一个常见误解是把std::priority_queue当成堆本身。它只是基于堆操作的一套容器适配器，底层默认用std::vector，默认是大顶堆。要理解它的行为，还是得先知道push_heap、pop_heap、make_heap这几个算法各自做了什么。

本文用一份代码实现两个结构：链式存储的二叉搜索树，负责有序插入与查找；数组存储的小顶堆，负责快速取最小值。前者演示节点与指针，后者演示下标运算。示例以 C++17 为准。

一、两种结构的约束对照

这张表说明了一个选型原则：需要按值查找、需要有序遍历，用二叉搜索树或平衡树；只需要反复取最大或最小，用堆。堆的优势在于完全二叉树可以用数组表示，没有指针开销，内存局部性更好。

二、链式二叉树：插入与查找

二叉树节点持有值和两个独占指针，树的类持有根指针。插入和查找都用循环完成，不需要递归：插入时用一个「指向指针的指针」沿着分支走，直到找到空槽；查找时用裸指针沿分支下行。

插入的关键是只比较当前节点的值，决定往左还是往右，遇到相等值直接返回，避免重复键。这样建出来的树满足二叉搜索树性质，但高度取决于插入顺序：按升序插入会退化成一条右斜链，查找退化为线性。真正需要稳定对数高度时，应该用 AVL 树或红黑树，而不是普通 BST。

遍历这里用显式栈做中序，避免深树递归。中序的迭代写法是：一路向左把节点压栈，弹出时访问，然后转向右子树，重复这个过程。

三、数组堆：下标映射与两个核心操作

完全二叉树按层序放进数组后，下标关系非常整齐。以 0 为起点：

如果误用从 1 开始的公式（父节点i / 2、左孩子2 * i），在 0 起点的数组上会整体错位，根节点的左孩子会指回自己。

堆只有两个核心操作。上浮（sift up）用于插入：新元素放到数组末尾，然后不断与父节点比较，比父节点更优先就交换，直到满足堆序或到达根。下沉（sift down）用于删除堆顶：把末尾元素搬到根，删除末尾，然后不断与两个孩子中更优先的那个比较并交换，直到满足堆序或成为叶子。

建堆有两条路。其一是逐个push，每次上浮，总代价 O(n log n)。其二是把整个数组放好，从最后一个非叶节点开始向前对每个节点下沉。后者是 O(n)：大部分节点都在底层，下沉距离很短，把所有节点的高度求和得到的是线性量级，而不是 n 乘 log n。

四、完整示例

// 适用于 C++17
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <memory>
#include <stdexcept>
#include <vector>

// ---------- 链式二叉搜索树 ----------
struct TreeNode {
int value;
std::unique_ptr<TreeNode> left;
std::unique_ptr<TreeNode> right;
explicit TreeNode(int v) : value(v) {}
};

class BinarySearchTree {
public:
void insert(int value) {
std::unique_ptr<TreeNode>* slot = &root_;
while (*slot) {
if (value < (*slot)->value) {
slot = &(*slot)->left;
} else if (value > (*slot)->value) {
slot = &(*slot)->right;
} else {
return; // 重复键忽略
}
}
*slot = std::make_unique<TreeNode>(value);
}

bool contains(int value) const {
const TreeNode* cur = root_.get();
while (cur) {
if (value == cur->value) return true;
cur = (value < cur->value) ? cur->left.get() : cur->right.get();
}
return false;
}

void printInOrder() const {
std::vector<const TreeNode*> st;
const TreeNode* cur = root_.get();
while (cur || !st.empty()) {
while (cur) {
st.push_back(cur);
cur = cur->left.get();
}
cur = st.back();
st.pop_back();
std::cout << cur->value << ' ';
cur = cur->right.get();
}
std::cout << '\n';
}

private:
std::unique_ptr<TreeNode> root_;
};

// ---------- 数组小顶堆 ----------
class MinHeap {
public:
void push(int value) {
data_.push_back(value);
siftUp(data_.size() - 1);
}

int pop() {
if (data_.empty()) throw std::out_of_range("pop on empty heap");
int top = data_.front();
data_.front() = data_.back();
data_.pop_back();
if (!data_.empty()) siftDown(0);
return top;
}

const int& top() const {
if (data_.empty()) throw std::out_of_range("top on empty heap");
return data_.front();
}

bool empty() const noexcept { return data_.empty(); }
std::size_t size() const noexcept { return data_.size(); }

// 从无序数组原地建堆，复杂度 O(n)
void build(const std::vector<int>& values) {
data_ = values;
if (data_.size() < 2) return;
for (std::size_t i = data_.size() / 2; i-- > 0; ) {
siftDown(i);
}
}

private:
void siftUp(std::size_t i) {
while (i > 0) {
std::size_t parent = (i - 1) / 2;
if (data_[parent] <= data_[i]) break;
std::swap(data_[parent], data_[i]);
i = parent;
}
}

void siftDown(std::size_t i) {
const std::size_t n = data_.size();
while (true) {
std::size_t left = 2 * i + 1;
std::size_t right = left + 1;
std::size_t smallest = i;

if (left < n && data_[left] < data_[smallest]) smallest = left;
if (right < n && data_[right] < data_[smallest]) smallest = right;

if (smallest == i) break;
std::swap(data_[i], data_[smallest]);
i = smallest;
}
}

std::vector<int> data_;
};

int main() {
BinarySearchTree bst;
for (int v : {8, 3, 10, 1, 6, 14, 4, 7, 13}) {
bst.insert(v);
}
bst.printInOrder();
std::cout << std::boolalpha
<< bst.contains(7) << ' '
<< bst.contains(9) << '\n';

MinHeap heap;
for (int v : {5, 1, 9, 3, 7, 2}) heap.push(v);
std::cout << "top=" << heap.top() << '\n';
while (!heap.empty()) std::cout << heap.pop() << ' ';
std::cout << '\n';

MinHeap built;
built.build({4, 8, 1, 9, 2, 6});
std::cout << "built top=" << built.top() << '\n';
return 0;
}

按标准语义推演这段代码。BST 依次插入 8、3、10、1、6、14、4、7、13，中序应当是 1 3 4 6 7 8 10 13 14。插入 4 时路径是 8 左到 3、右到 6、左为空，正好挂在 6 的左孩子上；插入 13 时路径是 8 右到 10、右到 14、左为空。

堆的部分，依次插入 5、1、9、3、7、2，每次上浮后根始终是最小值，所以top()为 1。连续pop会按 1、2、3、5、7、9 的顺序输出；pop先把末尾元素搬到根再下沉，搬动的是值而不是节点，堆序靠交换恢复。

build的循环写法for (std::size_t i = data_.size() / 2; i-- > 0; )需要单独解释：条件i-- > 0先比较再自减，所以循环体第一次拿到的下标是size / 2 - 1，也就是最后一个非叶节点；之后依次减一，直到 0 也执行一次。这里必须用无符号类型配合这种写法，若用int且条件写成i >= 0，i 为 0 后再减一会变成 -1，循环不终止。

五、与标准库堆算法的对应关系

标准库在<algorithm>里提供了std::make_heap、std::push_heap、std::pop_heap，它们只负责调整顺序，不负责容器大小：

std::priority_queue把这三步封装起来，默认是最大堆。想要最小堆，需要传比较器std::greater<int>，并包含<functional>。它的top()返回 const 引用，pop()返回 void，取值和删除必须分两步。

常见坑点

坑点一：0 起点数组套用 1 起点的下标公式。

❌parent = i / 2; left = 2 * i; right = 2 * i + 1;，根节点的左孩子下标仍是 0，指回自己。

✅parent = (i - 1) / 2; left = 2 * i + 1; right = 2 * i + 2;。

坑点二：以为pop_heap会删除元素。

❌ 调用std::pop_heap(v.begin(), v.end());后就认为堆顶没了，容器大小其实没变。

✅std::pop_heap之后紧跟v.pop_back();。

坑点三：priority_queue默认不是小顶堆。

❌std::priority_queue<int> q;期待top()给出最小值。

✅std::priority_queue<int, std::vector<int>, std::greater<int>> q;，并包含<functional>。

坑点四：下沉时只看左孩子。

❌ 只比较data_[left]与当前节点，右孩子更小时不动，堆序被破坏。

✅ 先选出左右孩子中更优先的那个，再与当前节点比较。

坑点五：对空堆调用top或pop。

❌ 不检查empty()直接取堆顶，data_.front()在空容器上是未定义行为。

✅ 先判断非空，或在函数内部抛std::out_of_range。

坑点六：把堆当成二叉搜索树查找。

❌ 在堆里用「小于往左、大于往右」的方式查找任意值。

✅ 堆只保证堆顶极值，查找任意值需要遍历，或改用 BST、哈希表。

坑点七：下标变量用有符号类型导致回绕。

❌for (int i = n / 2; i >= 0; --i)，i 减到 -1 后条件仍成立，越界访问。

✅ 用std::size_t配合i-- > 0的写法，或显式在 0 处 break。

总结

二叉树和堆的代码都不长，难的是把约束记清楚：BST 的有序性来自「左小右大」，堆的极值性来自「父不大于孩子」，两者不能互相替代。实现堆时只要下标公式、下沉时的孩子选择、删除后容器大小这三处不出错，剩下的就是机械的交换。