HOWTO · C++
在 C++ 中实现二叉树数据结构
本文演示了如何用 C++ 实现二叉树数据结构。
本页内容
在 C++ 中，可以用包含一个值和两个子节点链接的 struct 表示二叉树。下面的示例会构建一棵小型二叉树，统计节点数，按边数计算树高，并通过中序遍历打印节点值。
使用节点 struct 表示二叉树
二叉树节点最多有两个子节点，通常称为 left 和 right。struct 是一种类类型，其成员默认公开，因此适合用于这种小型数据结构。每个节点存储一个整数，并通过 std::unique_ptr 拥有其子节点；空指针表示缺少对应的子节点链接。空指针本身并不意味着该节点是叶节点：左右两个子节点链接都为空的节点才是叶节点。
满二叉树的每个节点要么没有子节点，要么有两个子节点。完美二叉树既是满二叉树，也要求所有叶节点位于同一深度。下面构建的示例是满二叉树，但不是完全二叉树：最后一层前面有一个空位，后面才有节点。这些术语描述的是不同的树形，不能混为一谈。
构建一棵小型二叉树
程序会创建如下确定的树形，所选数值便于跟踪遍历过程：8 (left: 3, right: 10 (left: 9, right: 14))。
std::make_unique 会创建节点并返回拥有该节点的指针。将指针移动到子节点成员中会转移所有权，因此根节点拥有整棵树；根节点离开作用域时，所有节点都会自动释放。这样就不必像使用 new 进行裸分配时那样手动清理。
运行以下示例。由于代码块保持原样，其中的输出标签仍为英文：
#include <iostream>
#include <memory>
struct BinTreeNode {
int data;
std::unique_ptr<BinTreeNode> left;
std::unique_ptr<BinTreeNode> right;
explicit BinTreeNode(int value) : data(value) {}
};
int treeSize(const BinTreeNode* node) {
if (node == nullptr) {
return 0;
}
return 1 + treeSize(node->left.get()) + treeSize(node->right.get());
}
int treeHeight(const BinTreeNode* node) {
if (node == nullptr) {
return -1;
}
const int leftHeight = treeHeight(node->left.get());
const int rightHeight = treeHeight(node->right.get());
return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}
void printData(const BinTreeNode* node) {
if (node == nullptr) {
return;
}
printData(node->left.get());
std::cout << node->data << ' ';
printData(node->right.get());
}
int main() {
auto root = std::make_unique<BinTreeNode>(8);
root->left = std::make_unique<BinTreeNode>(3);
root->right = std::make_unique<BinTreeNode>(10);
root->right->left = std::make_unique<BinTreeNode>(9);
root->right->right = std::make_unique<BinTreeNode>(14);
std::cout << "size = " << treeSize(root.get()) << '\n';
std::cout << "height = " << treeHeight(root.get()) << '\n';
std::cout << "inorder = ";
printData(root.get());
std::cout << '\n';
}
这些函数接收节点指针，但不会取得所有权。用 root.get() 调用它们，可以让函数访问这棵树，同时仍由拥有对象的 unique_ptr 负责其生命周期。同样的递归定义适用于任意树形。
统计节点数并计算树高
treeSize 遇到缺失的子树时返回零；否则，它会统计当前节点，并加上左右子树的节点数。treeHeight 遇到缺失的子树时返回 -1，然后在较高的子树高度上加一。按照这种约定，树高是根到叶最长路径所包含的边数：叶节点的树高为 0，上面的示例树高为 2。有些定义统计的是节点数，因此叶节点的树高为 1；选择一种约定并始终保持一致。
使用中序遍历打印节点
printData 会先访问左子树，再打印当前值，最后访问右子树。这就是中序遍历；对于二叉搜索树，它会按排序顺序打印值，而对于一般二叉树，它只按这种遍历顺序访问节点。更多详情请参阅中序遍历指南。
要跟踪递归过程，可以观察函数在每个节点上的执行顺序：它先向左深入，直到没有子节点；返回父节点时打印值，然后处理右子树。因此，示例中的值会按 3 8 9 10 14 的顺序出现。这棵树有五个节点，按边数计算的树高为二。程序是一个完整的独立示例；你可以调整节点值的类型或添加操作，同时明确所有权管理方式和所采用的树高约定。
