树¶
📖 章节简介¶
本章将介绍C++的树数据结构，包括二叉树、二叉搜索树和树的遍历算法。
上图展示了二叉搜索树的节点关系及前序/中序/后序遍历输出，便于理解不同遍历策略的访问顺序。
🌳 二叉树¶
1. 二叉树实现¶
C++
// 二叉树
#include <iostream>
using namespace std;
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
class BinaryTree {
private:
TreeNode* root;
public:
BinaryTree() : root(nullptr) {}
~BinaryTree() {
destroyTree(root);
}
void insert(int value) {
root = insertRecursive(root, value);
}
bool search(int value) {
return searchRecursive(root, value);
}
void inorder() {
cout << "中序遍历: ";
inorderRecursive(root);
cout << endl;
}
void preorder() {
cout << "前序遍历: ";
preorderRecursive(root);
cout << endl;
}
void postorder() {
cout << "后序遍历: ";
postorderRecursive(root);
cout << endl;
}
private:
TreeNode* insertRecursive(TreeNode* node, int value) {
if (node == nullptr) {
return new TreeNode(value);
}
if (value < node->data) {
node->left = insertRecursive(node->left, value);
} else {
node->right = insertRecursive(node->right, value);
}
return node;
}
bool searchRecursive(TreeNode* node, int value) {
if (node == nullptr) {
return false;
}
if (value == node->data) {
return true;
} else if (value < node->data) {
return searchRecursive(node->left, value);
} else {
return searchRecursive(node->right, value);
}
}
void inorderRecursive(TreeNode* node) {
if (node == nullptr) {
return;
}
inorderRecursive(node->left);
cout << node->data << " ";
inorderRecursive(node->right);
}
void preorderRecursive(TreeNode* node) {
if (node == nullptr) {
return;
}
cout << node->data << " ";
preorderRecursive(node->left);
preorderRecursive(node->right);
}
void postorderRecursive(TreeNode* node) {
if (node == nullptr) {
return;
}
postorderRecursive(node->left);
postorderRecursive(node->right);
cout << node->data << " ";
}
void destroyTree(TreeNode* node) {
if (node == nullptr) {
return;
}
destroyTree(node->left);
destroyTree(node->right);
delete node;
}
};
int main() {
BinaryTree tree;
// 插入节点
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
tree.insert(60);
tree.insert(80);
// 遍历树
tree.preorder();
tree.inorder();
tree.postorder();
// 查找节点
cout << "\n查找40: " << (tree.search(40) ? "找到" : "未找到") << endl;
cout << "查找90: " << (tree.search(90) ? "找到" : "未找到") << endl;
return 0;
}
2. 二叉搜索树¶
C++
// 二叉搜索树（BST）
#include <iostream>
using namespace std;
struct BSTNode {
int data;
BSTNode* left;
BSTNode* right;
BSTNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
class BinarySearchTree {
private:
BSTNode* root;
public:
BinarySearchTree() : root(nullptr) {}
~BinarySearchTree() {
destroyTree(root);
}
void insert(int value) {
root = insertRecursive(root, value);
}
bool search(int value) {
return searchRecursive(root, value);
}
void remove(int value) {
root = removeRecursive(root, value);
}
void inorder() {
inorderRecursive(root);
cout << endl;
}
private:
BSTNode* insertRecursive(BSTNode* node, int value) {
if (node == nullptr) {
return new BSTNode(value);
}
if (value < node->data) {
node->left = insertRecursive(node->left, value);
} else if (value > node->data) {
node->right = insertRecursive(node->right, value);
}
return node;
}
bool searchRecursive(BSTNode* node, int value) {
if (node == nullptr) {
return false;
}
if (value == node->data) {
return true;
} else if (value < node->data) {
return searchRecursive(node->left, value);
} else {
return searchRecursive(node->right, value);
}
}
BSTNode* removeRecursive(BSTNode* node, int value) {
if (node == nullptr) {
return nullptr;
}
// 在左子树或右子树中递归查找目标节点
if (value < node->data) {
node->left = removeRecursive(node->left, value);
} else if (value > node->data) {
node->right = removeRecursive(node->right, value);
} else {
// 找到要删除的节点，分三种情况处理
// 情况1：无左子树 → 用右子树替代当前节点
if (node->left == nullptr) {
BSTNode* temp = node->right;
delete node;
return temp;
// 情况2：无右子树 → 用左子树替代当前节点
} else if (node->right == nullptr) {
BSTNode* temp = node->left;
delete node;
return temp;
}
// 情况3：有两个子节点 → 找右子树的最小值（中序后继）替代
BSTNode* successor = findMin(node->right);
node->data = successor->data; // 用后继值覆盖当前节点
node->right = removeRecursive(node->right, successor->data); // 递归删除后继
}
return node;
}
// 查找子树中的最小值节点（BST中一直向左走到底即可）
BSTNode* findMin(BSTNode* node) {
while (node->left != nullptr) {
node = node->left;
}
return node;
}
void inorderRecursive(BSTNode* node) {
if (node == nullptr) {
return;
}
inorderRecursive(node->left);
cout << node->data << " ";
inorderRecursive(node->right);
}
void destroyTree(BSTNode* node) {
if (node == nullptr) {
return;
}
destroyTree(node->left);
destroyTree(node->right);
delete node;
}
};
int main() {
BinarySearchTree bst;
// 插入节点
bst.insert(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(40);
bst.insert(60);
bst.insert(80);
// 遍历BST
cout << "中序遍历（排序）：" << endl;
bst.inorder();
// 查找节点
cout << "查找40: " << (bst.search(40) ? "找到" : "未找到") << endl;
// 删除节点
bst.remove(30);
cout << "\n删除30后的中序遍历：" << endl;
bst.inorder();
return 0;
}
📊 层序遍历¶
1. 层序遍历实现¶
C++
// 层序遍历
#include <iostream>
#include <queue>
using namespace std;
// TreeNode 定义（与前面章节相同）
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
// 递归释放树的所有节点
void deleteTree(TreeNode* node) {
if (node == nullptr) return;
deleteTree(node->left);
deleteTree(node->right);
delete node;
}
// 层序遍历（BFS）：利用队列逐层访问节点
void levelOrder(TreeNode* root) {
if (root == nullptr) {
return;
}
queue<TreeNode*> q;
q.push(root); // 根节点入队作为起点
int level = 1;
while (!q.empty()) {
// 当前层的节点数 = 此刻队列中的元素个数
int levelSize = q.size();
cout << "第" << level << "层: ";
// 依次处理当前层的所有节点
for (int i = 0; i < levelSize; i++) {
TreeNode* node = q.front();
q.pop();
cout << node->data << " ";
// 将下一层的子节点入队，保证按层顺序访问
if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->right);
}
}
cout << endl;
level++;
}
}
int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
cout << "层序遍历：" << endl;
levelOrder(root);
// 释放所有节点，避免内存泄漏
deleteTree(root);
return 0;
}
💡 最佳实践¶
1. 内存管理¶
C++
// 内存管理
#include <iostream>
#include <memory>
// 注意：如果单独编译本代码块，需要包含 TreeNode 定义
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
int main() {
// ✅ 好的做法：使用智能指针
std::unique_ptr<TreeNode> root = std::make_unique<TreeNode>(10);
// ❌ 不好的做法：手动管理内存
TreeNode* rawRoot = new TreeNode(10);
// delete rawRoot; // 容易忘记
return 0;
}
2. 异常处理¶
C++
// 异常处理
#include <iostream>
#include <new>
using namespace std;
int main() {
// ✅ 好的做法：处理异常
try {
int* arr = new int[1000000000];
delete[] arr;
} catch (const bad_alloc& e) {
cout << "内存分配失败" << endl;
}
// ❌ 不好的做法：不处理异常
// int* arr = new int[1000000000];
// delete[] arr;
return 0;
}
📝 练习题¶
基础题¶
- 什么是二叉树？
- 如何实现树的遍历？
- 二叉搜索树有什么特点？
进阶题¶
- 实现树的删除操作。
- 计算树的高度和节点数。
- 实现平衡二叉搜索树。
实践题¶
- 创建一个简单的文件系统。
- 实现一个表达式求值器。
- 构建一个简单的数据库索引。
📚 推荐阅读¶
🔗 下一章¶
图 - 学习C++的图数据结构。