二叉树节点结构体
/* 二叉树节点结构体 */
struct TreeNode {
int val; // 节点值
TreeNode *left; // 左子节点指针
TreeNode *right; // 右子节点指针
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} //构建函数
};
常见术语
/* 1.初始化二叉树 */
// 初始化节点
TreeNode* n1 = new TreeNode(1);
TreeNode* n2 = new TreeNode(2);
TreeNode* n3 = new TreeNode(3);
TreeNode* n4 = new TreeNode(4);
TreeNode* n5 = new TreeNode(5);
//构建引用指向（即指针）
n1->left = n2;
n1->right = n3;
n2->left = n4;
n2->right = n5;
/* 2.插入与删除节点 */
TreeNode* P = new TreeNode(0);
// 在 n1 -> n2 中间插入节点 P
n1->left = P;
P->left = n2;
// 删除节点 P
n1->left = n2;
/*3.前序遍历 */
void preOrder(TreeNode *root) {
if (root == nullptr)
return;
// 访问优先级：根节点 -> 左子树 -> 右子树
vec.push_back(root->val);
preOrder(root->left);
preOrder(root->right);
}
/* 4.中序遍历 */
void inOrder(TreeNode *root) {
if (root == nullptr)
return;
// 访问优先级：左子树 -> 根节点 -> 右子树
inOrder(root->left);
vec.push_back(root->val);
inOrder(root->right);
}
/* 5.后序遍历 */
void postOrder(TreeNode *root) {
if (root == nullptr)
return;
// 访问优先级：左子树 -> 右子树 -> 根节点
postOrder(root->left);
postOrder(root->right);
vec.push_back(root->val);
}
/* 二叉树的数组表示 */
// 使用 int 最大值 INT_MAX 标记空位
vector<int> tree = {1, 2, 3, 4, INT_MAX, 6, 7, 8, 9, INT_MAX, INT_MAX, 12, INT_MAX, INT_MAX, 15};
以下代码实现了一个基于数组表示的二叉树
/* 数组表示下的二叉树类 */
class ArrayBinaryTree {
public:
/* 构造方法 */
ArrayBinaryTree(vector<int> arr) { tree = arr; }
/* 节点数量 */
int size() {
return tree.size();
}
/* 获取索引为 i 节点的值 */
int val(int i) {
// 若索引越界，则返回 INT_MAX ，代表空位
if (i < 0 || i >= size())
return INT_MAX;
return tree[i];
}
/* 获取索引为 i 节点的左子节点的索引 */
int left(int i) {
return 2 * i + 1;
}
/* 获取索引为 i 节点的右子节点的索引 */
int right(int i) {
return 2 * i + 2;
}
/* 获取索引为 i 节点的父节点的索引 */
int parent(int i) {
return (i - 1) / 2;
}
/* 层序遍历 */
vector<int> levelOrder() {
vector<int> res;
// 直接遍历数组
for (int i = 0; i < size(); i++) {
if (val(i) != INT_MAX)
res.push_back(val(i));
}
return res;
}
/* 前序遍历 */
vector<int> preOrder() {
vector<int> res;
dfs(0, "pre", res);
return res;
}
/* 中序遍历 */
vector<int> inOrder() {
vector<int> res;
dfs(0, "in", res);
return res;
}
/* 后序遍历 */
vector<int> postOrder() {
vector<int> res;
dfs(0, "post", res);
return res;
}
private:
vector<int> tree;
/* 深度优先遍历 deep first search */
void dfs(int i, string order, vector<int> &res) {
// 若为空位，则返回
if (val(i) == INT_MAX)
return;
// 前序遍历
if (order == "pre")
res.push_back(val(i));
dfs(left(i), order, res);
// 中序遍历
if (order == "in")
res.push_back(val(i));
dfs(right(i), order, res);
// 后序遍历
if (order == "post")
res.push_back(val(i));
}
};
二叉树的数组表示主要有以下优点：
然而，数组表示也存在一些局限性：
ArrayBinaryTree ，并声明一个成员变量 root ，指向树的根节点。给定要查找的目标节点值 num ，可以根据二叉搜索树的性质来查找。先声明一个节点 cur ，从二叉树的根节点 root 出发，循环比较节点值 cur.val 和 num 之间的大小关系：
二叉搜索树的查找操作与二分查找算法的工作原理一致，都是每轮排除一半情况。循环次数最多为二叉树的 高度，当二叉树平衡时，使用 𝑂(log 𝑛) 时间。
/* 查找节点 */
TreeNode *search(int num) {
TreeNode *cur = root;
// 循环查找，越过叶节点后跳出
while (cur != nullptr) {
// 目标节点在 cur 的右子树中
if (cur->val < num)
cur = cur->right;
// 目标节点在 cur 的左子树中
else if (cur->val > num)
cur = cur->left;
// 找到目标节点，跳出循环
else
break;
}
// 返回目标节点
return cur;
}
给定一个待插入元素 num ，为了保持二叉搜索树“左子树 < 根节点 < 右子树”的性质，插入操作流程如图所示:
在代码实现中，需要注意以下两点:
/* 插入节点 */
void insert(int num) {
// 若树为空，则初始化根节点
if (root == nullptr) {
root = new TreeNode(num);
return;
}
TreeNode *cur = root, *pre = nullptr;
// 循环查找，越过叶节点后跳出
while (cur != nullptr) {
if (cur->val == num) // 找到重复节点，直接返回
return;
pre = cur;
if (cur->val < num) // 插入位置在 cur 的右子树中
cur = cur->right;
else // 插入位置在 cur 的左子树中
cur = cur->left;
}
// 插入节点
TreeNode *node = new TreeNode(num);
if (pre->val < num)
pre->right = node;
else
pre->left = node;
}
先在二叉树中查找到目标节点，再将其从二叉树中删除。 与插入节点类似，我们需要保证在删除操作完成后，二叉搜索树的性质仍然满足。 因此，我们需要根据目标节点的子节点数量，共分为 0、1 和 2 这三种情况，执行对应的删除节点操作。 如图所示：
当待删除节点的度为 0 时，表示该节点是叶节点，可以直接删除。
当待删除节点的度为 1 时，将待删除节点替换为其子节点即可。
当待删除节点的度为 2 时，我们无法直接删除它，而需要使用一个节点替换该节点。由于要保持二叉搜索树 “左 < 根 < 右”的性质，因此这个节点可以是右子树的最小节点或左子树的最大节点。
假设我们选择右子树的最小节点（即中序遍历的下一个节点），则删除操作流程如下：
找到待删除节点在“中序遍历序列”中的下一个节点，记为 tmp 。
将 tmp 的值覆盖待删除节点的值，并在树中递归删除节点 tmp 。
代码如下：
/* 删除节点 */
void remove(int num) {
if (root == nullptr) // 若树为空，直接提前返回
return;
TreeNode *cur = root, *pre = nullptr;
while (cur != nullptr) { // 循环查找，越过叶节点后跳出
if (cur->val == num) // 找到待删除节点，跳出循环
break;
pre = cur;
if (cur->val < num) // 待删除节点在 cur 的右子树中
cur = cur->right;
else // 待删除节点在 cur 的左子树中
cur = cur->left;
}
if (cur == nullptr) // 若无待删除节点，则直接返回
return;
// 待删除节点的子节点数量 = 0 或 1
if (cur->left == nullptr || cur->right == nullptr) {
// 当子节点数量 = 0 / 1 时， child = nullptr / 该子节点
TreeNode *child = cur->left != nullptr ? cur->left : cur->right;
// 删除节点 cur
if (cur != root) {
if (pre->left == cur)
pre->left = child;
else
pre->right = child;
} else {
root = child; // 若删除节点为根节点，则重新指定根节点
}
// 释放内存
delete cur;
}
else { // 子节点数量 = 2
// 获取中序遍历中 cur 的下一个节点
TreeNode *tmp = cur->right;
while (tmp->left != nullptr) {
tmp = tmp->left;
}
int tmpVal = tmp->val;
// 递归删除节点 tmp
remove(tmp->val);
// 用 tmp 覆盖 cur
cur->val = tmpVal;
}
}
二叉搜索树的各项操作（查找、插入、删除）的时间复杂度都是对数阶，具有稳定且高效的性能表现。但如果我们在二叉搜索树中不断地插入和删除节点，可能导致二叉树退化为链表，这时各种操作的时间复杂度也会退化为 𝑂(𝑛) 。
二叉搜索树常见应用：
二叉搜索树的各项操作（查找、插入、删除）的时间复杂度都是对数阶，具有稳定且高效的性能表现。但如果我们在二叉搜索树中不断地插入和删除节点，可能导致二叉树退化为链表，这时各种操作的时间复杂度也会退化为 𝑂(𝑛) 。
[外链图片转存中…(img-kX4RgCAL-1724514112382)]
二叉搜索树常见应用：