tags: DSA C++ BinaryTree Interview
写在前面
总结一下二叉搜索树的实现, 包括直接遍历数组的方法构建, 添加节点, 指定值的搜索, 结点的删除, 插入等操作.
代码见dsa/c_cpp/Binary_Tree at main · Apocaly-pse/dsa (github.com);
这里很奇怪, MacOS下的gcc可以编译但是会segment fault, 但是Clang就不会, 莫非是Apple在削减gcc? 问题应该是出在print_tree了.
二叉搜索树简介
二叉搜索树（英语：Binary Search Tree），也称为二叉查找树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
- 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 任意节点的左、右子树也分别为二叉查找树；
二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为
。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。
因为二叉搜索树很可能退化为链表(时间复杂度为树高, 链表的时候就是了), 这样的话就体现不出二叉搜索树作为一种树结构带来的时间复杂度上的提升了, 所以需要引入一种平衡结构, 称为平衡二叉搜索树, 其实就是树中任一节点的左子树和右子树高度之差不超过1的二叉搜索树.
一些相关的力扣题目:(后面遇到还会提及)
-
98. 验证二叉搜索树 - 力扣（LeetCode）;(性质)
-
108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）;
-
1382. 将二叉搜索树变平衡 - 力扣（LeetCode）;
-
701. 二叉搜索树中的插入操作 - 力扣（LeetCode）;
定义
- 空树是二叉搜索树。
- 若二叉搜索树的左子树不为空，则其左子树上所有点的权值均小于其根节点的值。
- 若二叉搜索树的右子树不为空，则其右子树上所有点的权值均大于其根节点的值。
- 二叉搜索树的左右子树均为二叉搜索树。
性质
- 由二叉搜索树的递归定义可得，二叉搜索树的中序遍历权值的序列为非降的序列。时间复杂度为。
BinarySearchTree类
这部分内容保存为bst.h头文件.
一些用到的头文件:
#include <iostream>
#include <queue> // 层序
#include <stack> // 迭代实现中序遍历, 析构
#include <vector>
#include <tuple> // 输出二叉树用tuple存数据
#include <cmath> // pow()
#include <functional> // 递归lambda
using namespace std;
首先是树节点的结构体定义:
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
// used by remove and insert
TreeNode* parent;
TreeNode() : val(0), left(nullptr), right(nullptr), parent(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr), parent(nullptr) {}
TreeNode(int x, TreeNode* left1, TreeNode* right1)
: val(x), left(left1), right(right1), parent(nullptr) {}
};这里有一个与以往普通二叉树不同的点, 就是父节点指针, 这是为了删除节点操作而定义的.
然后是一个有用的函数, 用来输出数组, 等等.
// 重载<<操作符输出数组
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
if (v.empty()) return os << "[]\n";
os << "[";
for (auto it = v.begin(); it != v.end(); it++) {
os << *it << (it != v.end() - 1 ? ", " : "] \n");
}
return os;
}
下面就是重头戏二叉搜索树的类声明了:
包括二叉搜索树的一些常用API, 在这里介绍具体的实现思路.
class BinarySearchTree {
public:
BinarySearchTree() : root(nullptr) {}
~BinarySearchTree();
// 二叉搜索树通过数组构建
void build_from_array(vector<int>&); // 不会出现不平衡
// 遍历部分
void breadth_travel(); // bfs
void print_tree(); // bfs, 输出二叉树
void in_order_recur(); // 顺序输出
void in_order_iter(); // 顺序输出
// 以结点x为根的树的最大节点, 最小节点
TreeNode* maximum(TreeNode*);
TreeNode* minimum(TreeNode*);
// 整个树的最大值最小值
int MAX();
int MIN();
// 前驱节点, 后继结点
TreeNode* predecessor(TreeNode*);
TreeNode* successor(TreeNode*);
// 树结点的查找
TreeNode* search(int);
// 插入节点
void insert(int);
// 删除节点(冗余代码)
void remove_1(TreeNode*);
// 删除(精简代码)
void remove(TreeNode*);
private:
TreeNode* root;
TreeNode* _search(TreeNode*, int);
void transplant(TreeNode*, TreeNode*);
};这部分我给出了很多API, 后面会一一实现.
API函数实现
这部分内容保存为bst.cpp.
#include "bst.h"
可视化输出二叉树
ASCII格式化输出二叉树: (这部分之前写过, 输出效果还不错)
void BinarySearchTree::print_tree() {
queue<TreeNode*> q;
q.push(root);
int m = 0;
while (!q.empty()) {
for (int i = 0; i < q.size(); i++) {
auto cur = q.front();
q.pop();
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
m++;
}
int n = (1 << m) - 1;
vector<vector<string>> ans(m, vector<string>(n, " "));
vector<vector<string>> branch(m, vector<string>(n, " "));
queue<tuple<int, int, TreeNode*, string>> bq;
bq.push({0, (n - 1) / 2, root, ""s});
while (!bq.empty()) {
for (int i = 0; i < bq.size(); i++) {
auto& [r, c, cur, slash] = bq.front();
bq.pop();
if (!cur->val) continue;
ans[r][c] = to_string(cur->val);
if (r == m - 1) {
branch[r][c] = slash;
} else {
if (slash == "/"s)
branch[r][c + 1] = slash;
else
branch[r][c - 1] = slash;
}
if (cur->left)
bq.push({r + 1, c - pow(2, m - r - 2), cur->left, "/"s});
if (cur->right)
bq.push({r + 1, c + pow(2, m - r - 2), cur->right, "\\"s});
}
}
for (int i = 0; i < m; i++) {
for (auto& s : branch[i]) cout << s;
cout << endl;
for (auto& s : ans[i]) cout << s;
cout << endl;
}
}析构
这部分之前在二叉树部分介绍过, 现在拿出来复习一下:
BinarySearchTree::~BinarySearchTree() {
function<void(TreeNode*)> f = [&](TreeNode* node) {
TreeNode* Left_Tree = node->left;
TreeNode* Right_Tree = node->right;
cout << node->val << " ";
delete node;
if (Left_Tree) f(Left_Tree);
if (Right_Tree) f(Right_Tree);
};
f(root);
cout << " deleted..\n";
}递归lambda实现.
广度(层序)遍历
void BinarySearchTree::breadth_travel() {
if (!root) return;
queue<TreeNode*> que;
que.push(root);
vector<int> ret;
while (!que.empty()) {
TreeNode* cur = que.front();
que.pop();
ret.emplace_back(cur->val);
if (cur->left) que.push(cur->left);
if (cur->right) que.push(cur->right);
}
cout << ret;
}中序遍历
void BinarySearchTree::in_order_recur() {
vector<int> ret;
function<void(TreeNode*)> f = [&](TreeNode* node) {
if (!node) return;
f(node->left);
ret.emplace_back(node->val);
f(node->right);
};
f(root);
cout << ret;
}
void BinarySearchTree::in_order_iter() {
if (!root) return;
vector<int> ret;
stack<TreeNode*> st;
auto cur = root;
while (!st.empty() || cur) {
if (cur) {
st.push(cur);
cur = cur->left;
} else {
cur = st.top();
st.pop();
ret.emplace_back(cur->val);
cur = cur->right;
}
}
cout << ret;
}从数组构建
108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）;
这里其实是一个力扣原题, 递归很好想, 迭代重点是三个队列的模拟.
因为数组已经有序了, 那么只需要每次找中间节点然后建树即可.
void BinarySearchTree::build_from_array(vector<int>& items) {
// 有序数组构建二叉搜索树
sort(items.begin(), items.end());
function<TreeNode*(int, int)> f = [&](int l, int r) {
if (l > r) return (TreeNode*)nullptr;
int mid = l + (r - l) / 2;
return new TreeNode(items[mid], f(l, mid - 1), f(mid + 1, r));
};
// 迭代
function<TreeNode*(void)> g = [&]() {
if (items.empty()) return (TreeNode*)nullptr;
TreeNode* tmp_root = new TreeNode();
queue<TreeNode*> nodeQue;
queue<int> leftQue, rightQue;
nodeQue.push(tmp_root);
leftQue.push(0);
rightQue.push(items.size() - 1);
while (!nodeQue.empty()) {
auto cur = nodeQue.front();
nodeQue.pop();
int L = leftQue.front();
leftQue.pop();
int R = rightQue.front();
rightQue.pop();
int mid = L + (R - L) / 2;
cur->val = items[mid]; // 赋值
if (L < mid) {
cur->left = new TreeNode();
nodeQue.push(cur->left);
leftQue.push(L);
rightQue.push(mid - 1);
}
if (R > mid) {
cur->right = new TreeNode();
nodeQue.push(cur->right);
leftQue.push(mid + 1);
rightQue.push(R);
}
}
return tmp_root;
};
/* root = f(0, items.size() - 1); */
root = g();
}给出了递归和迭代两种实现, 迭代的代码参考代码随想录.
插入节点
这里需要分情况讨论一下.
力扣原题:
701. 二叉搜索树中的插入操作 - 力扣（LeetCode）;
定义 insert(item) 为在二叉搜索树root(root代表根节点)中插入一个值为 item 的新节点。
分类讨论如下：
- 若 root 为空，直接返回一个值为 item 的新节点。
- 若 root 的权值大于 item，在 root 的左子树中插入权值为 item 的节点。
- 若 root 的权值小于 item，在 root 的右子树中插入权值为 item 的节点。
时间复杂度为 , 为树高。
需要注意parent指针的使用, 这也是添加节点时候的一个难点, 与力扣原题不一样.
void BinarySearchTree::insert(int item) {
// 循环插入结点构建二叉搜索树, 但是容易退化成链表(不具备平衡性)
TreeNode *y{}, *x = root, *z = new TreeNode(item);
while (x) {
y = x;
if (item < x->val)
x = x->left;
else
x = x->right;
}
z->parent = y;
if (!y)
root = z;
else if (item < y->val)
y->left = z;
else
y->right = z;
}查找
这里我给出了两个API, 分别是针对数字和针对节点指针.
注释部分是递归实现.
TreeNode* BinarySearchTree::_search(TreeNode* x, int target) {
/* if (!x || target == x->val) return x; */
/* if (target < x->val) */
/* return _search(x->left, target); */
/* else */
/* return _search(x->right, target); */
while (x && target != x->val)
if (target < x->val)
x = x->left;
else
x = x->right;
return x;
}
TreeNode* BinarySearchTree::search(int target) { return _search(root, target); }最大最小值
TreeNode* BinarySearchTree::maximum(TreeNode* x) {
while (x->right) x = x->right;
return x;
}
TreeNode* BinarySearchTree::minimum(TreeNode* x) {
while (x->left) x = x->left;
return x;
}
int BinarySearchTree::MAX() { return maximum(root)->val; }
int BinarySearchTree::MIN() { return minimum(root)->val; }前驱后继结点
TreeNode* BinarySearchTree::successor(TreeNode* x) {
// 如果结点x的右子树非空, 则x后继结点就是其右子树的最左节点(minimum)
if (x->right) return minimum(x->right);
TreeNode* y = x->parent;
// 如果x右子树为空且其后继结点存在, 则其后继就是x的有左孩子的最底层祖先
while (y && x == y->right) x = y, y = y->parent;
return y;
}
TreeNode* BinarySearchTree::predecessor(TreeNode* x) {
if (x->left) return maximum(x->left);
TreeNode* y = x->parent;
while (y && x == y->left) x = y, y = y->parent;
return y;
}删除节点
这块是比较复杂的, 下面来看看, 分为四种情况(中间两种可以合并).
case 1: node没有子树
// case 1: 无子树
if (!node->left && !node->right) {
auto parent = node->parent;
if (!parent) {
delete root;
root = nullptr;
return;
}
if (node == parent->left) {
delete parent->left;
parent->left = nullptr;
return;
} else if (node == parent->right) {
delete parent->right;
parent->right = nullptr;
return;
}
}
注意这里的删除操作, 需要在delete之后进行空指针的赋值(下同), 否则被释放内存的节点指针成为空悬指针(dangling pointer), 会影响之后使用该指针. (不过这个程序里面不会有影响, 这里就是提供一种比较规范的内存管理方法)
CPPprimer5ed, 12.1, pp411.
当我们delete一个指针后, 指针的值变为无效. 虽然指针无效, 但是在很多机器上指针仍然保存着(已经释放了的)动态内存的地址. 在delete之后, 指针就变成空悬指针, 即指向一块曾经保存数据对象但是现在已经无效的内存的指针.
未经初始化的指针的所有缺点, 空悬指针也都有. 有一种方法可以避免空悬指针的问题, 即:
在指针即将要离开起作用域之前, 释放掉其关联的内存.
这样, 在指针关联的内存被释放掉之后, 就没有机会继续使用指针了. 如果需要保留指针, 可以在delete之后将nullptr赋予指针, 这样就清楚指出指针不指向任何对象.
case 2: node有左子树
// case 2: 只有左子树
if (node->left && !node->right) {
auto cur = node->left;
auto val = cur->val;
node->left = cur->left;
node->right = cur->right;
node->val = val;
// 修正parent
if (node->left) node->left->parent = node;
if (node->right) node->right->parent = node;
// 删除cur
delete cur;
cur = nullptr;
return;
}
case 3: node只有右子树
// case 3: 只有右子树
if (!node->left && node->right) {
auto cur = node->right;
auto val = cur->val;
node->left = cur->left;
node->right = cur->right;
node->val = val;
// 修正parent
if (node->left) node->left->parent = node;
if (node->right) node->right->parent = node;
// 删除cur
delete cur;
cur = nullptr;
return ;
}
case 4: node有左子树和右子树
// case 4: 左右子树都存在且不为空
if (node->left && node->right) {
auto pre = node->left;
while (pre->right) pre = pre->right;
node->val = pre->val;
// 递归, 最后一定能删除到前面三种情况, 此时结束递归
remove(pre);
}
这里用了递归, 参考了:
easy-cs/红黑树杀人事件始末.md at main · allentofight/easy-cs (github.com);
很棒的文章(代码是Java)
合并代码
整体实现会合并这些情况, 使代码更加简洁(参考算法导论).
void BinarySearchTree::transplant(TreeNode* u, TreeNode* v) {
// 用以v为根的子树替换以u为根的子树
// 允许v空
if (!u->parent)
// 处理u是BST根节点的情况
root = v;
else if (u == u->parent->left)
// u是其父节点的左孩子
u->parent->left = v;
else
// u是其父节点的右孩子
u->parent->right = v;
// v非空, 更新父节点指针
if (v) v->parent = u->parent;
}
void BinarySearchTree::remove(TreeNode* z) {
if (!z->left) // 没有左子树, 右子树可有可无
transplant(z, z->right);
else if (!z->right) // 没有右子树, 有左子树
transplant(z, z->left);
else { // 左右子树均存在且不为空
// 查找z的后继
/*因为z右子树非空, 所以后继一定是该子树的最小节点*/
auto y = minimum(z->right);
if (y->parent != z) {
transplant(y, y->right);
y->right = z->right;
y->right->parent = y;
}
transplant(z, y);
y->left = z->left;
y->left->parent = y;
delete z;
z = nullptr;
}
}相当经典的技巧, 通过定义子函数transplant来完成删除节点的操作.
代码示例
void t0() {
BinarySearchTree tree;
vector<int> nodes{15, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9};
// 方法一
// 严格递增序列, 这样构建的树一定是高度为n-1的一条链
// 退化成链表, 所以需要有平衡性的限制(AVL, RBT)
/* sort(nodes.begin(), nodes.end()); */
for (int i : nodes) tree.insert(i);
/* for (int i{1}; i < 8; ++i) tree.insert(i); */
// 方法二: 数组构建二叉搜索树, 这种方法出来的一定是平衡的
// 但是没有处理父节点指针
/* vector<int> arr = {1, 2, 3, 4, 5, 6, 7}; */
/* tree.build_from_array(nodes); */
tree.breadth_travel();
cout << "BST is :\n";
tree.in_order_recur();
cout << "MAX of the BST is " << tree.MAX() << endl;
cout << "MIN of the BST is " << tree.MIN() << endl;
auto n1 = tree.search(6);
cout << "maximum in tree(6) is " << tree.maximum(n1)->val << endl;
cout << "minimum in tree(6) is " << tree.minimum(n1)->val << endl;
auto node = tree.search(13);
int suc = tree.successor(node)->val;
int pre = tree.predecessor(node)->val;
cout << "suc of 13 is " << suc << endl;
cout << "pre of 13 is " << pre << endl;
/* [15, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9] */
/* BST is : */
/* [2, 3, 4, 6, 7, 9, 13, 15, 17, 18, 20] */
/* MAX of the BST is 20 */
/* MIN of the BST is 2 */
/* maximum in tree(6) is 13 */
/* minimum in tree(6) is 2 */
/* suc of 13 is 15 */
/* pre of 13 is 9 */
/* 15 6 3 2 4 7 13 9 18 17 20 deleted.. */
}
int main(int argc, char const* argv[]) {
/* t0(); */
t1();
return 0;
}删除部分的测试:
void t1() {
BinarySearchTree tree;
vector<int> nodes{15, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9};
for (int i : nodes) tree.insert(i);
cout << "breadth_travel: \n";
tree.print_tree();
int node1{15};
cout << "delete node: " << node1 << endl;
tree.remove_1(tree.search(node1));
/* tree.remove(tree.search(4)); */
/* tree.remove(tree.search(3)); */
tree.print_tree();
}输出结果:
breadth_travel:
15
/ \
6 18
/ \ / \
3 7 17 20
/ \ \
2 4 13
/
9
delete node: 15
13
/ \
6 18
/ \ / \
3 7 17 20
/ \ \
2 4 9
13 6 3 2 4 7 9 18 17 20 deleted..
./Binary_Search_Tree.out 0.03s user 0.10s system 64% cpu 0.202 total
[Process exited 0]
如果用合并过的代码, 会发现删除之后修改的是右子树.
breadth_travel:
15
/ \
6 18
/ \ / \
3 7 17 20
/ \ \
2 4 13
/
9
delete node: 15
17
/ \
6 18
/ \ \
3 7 20
/ \ \
2 4 13
/
9
17 6 3 2 4 7 13 9 18 20 deleted..
./Binary_Search_Tree.out 0.03s user 0.10s system 73% cpu 0.171 total
[Process exited 0]
二叉搜索树示例来自算法导论.
