在 C++ 中实现二叉树数据结构
本文将讲解如何用 C++ 实现二叉树数据结构。
在 C++ 中使用 struct 关键字实现二叉树
树是用于各种基本算法的抽象数据结构。它们通常是层次结构，其中需要有一个根节点及其子节点形成子树。此外，还有多种树结构类型，每种类型都适合特定需求并提供一些权衡。
二叉树是树数据结构的子类之一，它被定义为每个节点最多必须有两个子节点的树，包括指定为 left 和 right 的子节点。在这种情况下，我们使用 struct 函数实现一个二叉树，因为它声明了一个成员默认为 public 的类。二叉树中的一个节点包含两个指向左/右节点的指针以及需要的数据。请注意，我们声明了一个 int 成员来表示存储在节点上的数据，仅用于说明目的。
我们定义了一个构造函数，它接受一个整数作为参数并用它的值初始化 data 成员。然后，它用 nullptr 值初始化双节点指针，这是表示叶子节点的常用方法。示例驱动程序代码构建一个示例图并在每个节点中存储随机整数。二叉树有多种子类型，例如，完整二叉树是一种结构，其中每个节点都有 0 或 2 个子节点。另一种称为完美二叉树，其中所有内部节点都有两个子节点，并且所有叶子节点具有相同的深度。
#include <iostream>
#include <random>
using std::cout;
using std::endl;
struct BinTreeNode {
int data;
struct BinTreeNode *left;
struct BinTreeNode *right;
BinTreeNode() = default;
explicit BinTreeNode(int d) : data(d) {
left = nullptr;
right = nullptr;
}
};
constexpr int MIN = 1;
constexpr int MAX = 10000;
int main() {
std::random_device rd;
std::mt19937 eng(rd());
std::uniform_int_distribution<int> distr(MIN, MAX);
auto root = new BinTreeNode(distr(eng));
root->left = new BinTreeNode(distr(eng));
root->right = new BinTreeNode(distr(eng));
root->right->left = new BinTreeNode(distr(eng));
root->right->right = new BinTreeNode(distr(eng));
return EXIT_SUCCESS;
}
请注意，上面的代码产生了一个完整的二叉树结构，如下图所示。我们使用 new 运算符分配每个节点，并使用伪随机数生成器传递初始化值。
root / left right / \ / nullptr nullptr left right / \ /
nullptr nullptr nullptr nullptr
在 C++ 中实现计算树结构的大小和高度的函数和打印元素的函数
由于树结构是分治算法执行的形式，后一种方法通常用于实现操作其元素的功能。treeSize 函数检索表示所有节点数量的树的大小，包括根。请注意，我们只需要使用简单的递归并返回 root 值的大小（即 1）加上左/右节点的大小。
下一个函数是 treeHeight，它检索树的高度，通常称为从根到叶的最长路径中的节点数量。该函数还通过在两个子节点上调用自身并返回 root 值（即 1）的高度加上先前调用中的较大值来利用递归。
另一方面，printData 函数将每个节点的 data 成员输出到 cout 流。二叉树结构有多种遍历方式：中序遍历、前序遍历和后序遍历。
在下面的例子中，使用了中序遍历方式。该过程首先打印从最左边的叶子节点到右边相同深度的数据，然后移动到上层。下一个代码片段构造一个部分随机的二叉树，然后在其上调用上述每个函数。如果这些函数的递归性质乍一看似乎令人困惑，你应该尝试在较小的树对象上逐步调试它们，并观察每个递归函数调用的行为。
#include <iostream>
#include <random>
using std::cout;
using std::endl;
struct BinTreeNode {
int data;
struct BinTreeNode *left;
struct BinTreeNode *right;
BinTreeNode() = default;
explicit BinTreeNode(int d) : data(d) {
left = nullptr;
right = nullptr;
}
};
int treeSize(BinTreeNode *n) {
if (n == nullptr)
return 0;
else
return 1 + treeSize(n->left) + treeSize(n->right);
}
int treeHeight(BinTreeNode *n) {
int lh, rh;
if (n == nullptr)
return -1;
else {
lh = treeHeight(n->left);
rh = treeHeight(n->right);
return 1 + (lh > rh ? lh : rh);
}
}
void printData(BinTreeNode *n) {
if (n != nullptr) {
printData(n->left);
cout << n->data << "; ";
printData(n->right);
}
}
constexpr int MIN = 1;
constexpr int MAX = 10000;
int main() {
std::random_device rd;
std::mt19937 eng(rd());
std::uniform_int_distribution<int> distr(MIN, MAX);
auto root = new BinTreeNode(distr(eng));
auto tmp = root;
auto iter = 100;
while (iter > 0) {
auto val = distr(eng);
if (val % 5 == 0) {
tmp->left = new BinTreeNode(distr(eng));
tmp = tmp->left;
} else if (val % 4 == 0) {
tmp->right = new BinTreeNode(distr(eng));
tmp = tmp->right;
} else if (val % 6 == 0) {
tmp->left = new BinTreeNode(distr(eng));
} else if (val % 100 == 0) {
tmp = root;
} else if (val % 2 == 0) {
tmp->right = new BinTreeNode(distr(eng));
}
iter -= 1;
}
cout << "size of tree = " << treeSize(root) << endl;
cout << "height of tree = " << treeHeight(root) << endl;
printData(root);
return EXIT_SUCCESS;
}
输出：
size of tree = 45
height of tree = 37
...(elements in the tree)
