BST树称为【二叉搜索树(Binary Search Tree)】或者【二叉排序树(Binary Sort Tree)】，它或者是一颗空树，或者是具有如下性质的二叉树：
- 若左子树不为空，则左子树上所有节点的值均小于它的根节点的值；
- 若右子树不为空，则右子树上所有结点的值均大于它的根结点的值；
- 左右子树也分别满足二叉搜索树的性质；
所有，二叉搜索树的特点是每一个节点都满足：左孩子的值 < 父节点的值 < 右孩子的值，一颗典型的二叉搜索树如下图所示：
1. 代码实现
1.1 插入操作
非递归插入时分为两种情况：
- BST树为空：在 root 处生成新的节点即可
- BST树非空：从根节点开始进行比较，找到合适的位置，生成新的节点，并把新节点的地址写入父节点相应的地址域当中
非递归版本的代码实现如下：
void insert(const T& val) {
if (root_ == nullptr) {
root_ = new Node(val);
return;
}
Node *cur = root_, *parent = nullptr;
while (cur != nullptr) {
if (cur->data_ == val) {
break;
} else if (comp_(cur->data_, val)) {
parent = cur;
cur = cur->right_;
} else {
parent = cur;
cur = cur->left_;
}
}
if (comp_(val, parent->data_)) {
parent->left_ = new Node(val);
} else {
parent->right_ = new Node(val);
}
}
递归版本的插入操作代码如下：
void r_insert(const T& val) {
root_ = r_insert(root_, val);
}
Node* r_insert(Node* node, const T& val) {
if (node == nullptr) return new Node(val);
if (node->data_ == val) {
return node;
} else if (comp_(node->data_, val)) {
node->right_ = r_insert(node->right_, val);
} else {
node->left_ = r_insert(node->left_, val);
}
return node;
}
1.2 删除操作
对于非递归删除操作而言，其分为三种情况：
- 删除没有孩子的节点：父节点的相应地址域置为空
- 删除一个孩子的节点：将被删除节点的孩子节点写入被删除节点的父节点的地址域
- 删除两个孩子的节点：找到待删除节点的前驱节点(或者后继节点)，用前驱节点或者后继节点的值将待删除结点的值覆盖，然后直接删除前驱或者后继节点即可
其中：
- 前驱节点：当前节点在左子树中值最大的节点
- 后继节点：当前节点在右子树中值最小的节点
情况 1 和情况 2 其实可以合并为一种处理方式，对于情况 3 而言，由于前驱节点或者后继节点最多只有一个孩子节点，或者没有孩子节点，所以可以将其转化为情况 1 或者情况 2（如果有两个孩子，则不可能是前驱或者后继节点）。
非递归版本的删除操作代码实现如下：
void remove(const T& val) {
if (root_ == nullptr) return;
Node *parent = nullptr, *cur = root_;
while (cur != nullptr) {
if (cur->data_ == val) {
break;
} else if (comp_(cur->data_, val)) {
parent = cur;
cur = cur->right_;
} else {
parent = cur;
cur = cur->left_;
}
}
// 未找到待删除节点
if (cur == nullptr) return;
// 处理情况3
if (cur->left_ != nullptr && cur->right_ != nullptr) {
parent = cur;
Node* pre = cur->left_;
while (pre->right_ != nullptr) {
parent = pre;
pre = pre->right_;
}
cur->data_ = pre->data_;
cur = pre; // 让cur指向前驱节点 转化为情况1或情况2
}
// 处理情况1或情况2
// cur指向待删除节点 parent指向其父节点
Node* child = cur->left_;
if (child == nullptr) {
child = cur->right_;
}
if (parent == nullptr) {
// 表示删除的是根节点
root_ = child;
} else {
// 将待删除节点写入其父节点的相应地址域
if (parent->left_ == cur) {
parent->left_ = child;
} else {
parent->right_ = child;
}
}
delete cur;
}
递归版本的删除操作代码实现如下：
void r_remove(const T& val) {
root_ = r_remove(root_, val);
}
Node* r_remove(Node* node, const T& val) {
if (node == nullptr) return nullptr;
if (node->data_ == val) {
if (node->left_ != nullptr && node->right_ != nullptr) {
// 情况3
// 找前驱节点
Node* pre = node->left_;
while (pre->right_ != nullptr) {
pre = pre->right_;
}
node->data_ = pre->data_;
// 通过递归删除前驱节点
node->left_ = r_remove(node->left_, pre->data_);
} else {
// 情况1或情况2
if (node->left_ != nullptr) {
Node* left = node->left_;
delete node;
return left;
} else if (node->right_ != nullptr) {
Node* right = node->right_;
delete node;
return right;
} else {
// 删除的是叶子节点
delete node;
return nullptr;
}
}
} else if (comp_(node->data_, val)) {
node->right_ = r_remove(node->right_, val);
} else {
node->left_ = r_remove(node->left_, val);
}
return node;
}
2.1.3 前中后层序遍历
二叉树的遍历一般有如下四种方式：
- 前序遍历：即以 “中-左-右” 的方式先访问根结点的值，然后访问左子树，最后访问右子树
- 中序遍历：即以 “左-中-右” 的方式先访问左子树，然后访问根结点的值，最后访问右子树
- 后序遍历：即以 “左-右-中” 的方式先访问左子树，然后访问右子树，最后访问根结点的值
- 层序遍历：即以 “从上到下，从左到右” 的方式一层一层遍历二叉树
这四种方式的遍历如下图所示：
可以看到，对于 BST 树来说，其中序遍历是一个不断升序的过程。
递归版本的前序、中序、后序、层序遍历的代码如下：
// 递归前序遍历
void preOrder(Node* node) {
if (node == nullptr) return;
cout << node->data_ << " ";
preOrder(node->left_);
preOrder(node->right_);
}
// 递归中序遍历
void inOrder(Node* node) {
if (node == nullptr) return;
inOrder(node->left_);
cout << node->data_ << " ";
inOrder(node->right_);
}
// 递归后序遍历
void postOrder(Node* node) {
if (node == nullptr) return;
postOrder(node->left_);
postOrder(node->right_);
cout << node->data_ << " ";
}
// 递归层序遍历
void levelOrder() {
cout << "[Recursion]Levelorder Traversal: ";
int l = level();
for (int i = 0; i < l; i++) {
levelOrder(root_, i);
}
cout << endl;
}
// 返回二叉树的层数
int level() const {
return level(root_);
}
// 递归层序遍历
void levelOrder(Node* node, int l) {
if (node == nullptr) return;
if (l == 0) {
cout << node->data_ << " ";
return;
}
levelOrder(node->left_, l - 1);
levelOrder(node->right_, l - 1);
}
// 递归求二叉树的层数
int level(Node* node) const {
if (node == nullptr) return 0;
int lcnt = level(node->left_);
int rcnt = level(node->right_);
return max(rcnt, lcnt) + 1;
}
非递归版本的前序、中序、后序、层序的遍历代码如下：
// 非递归前序遍历
void preOrder() {
cout << "[Not Recursion]Preorder Traversal: ";
if (root_ == nullptr) return;
stack<Node*> st;
st.push(root_);
while (!st.empty()) {
Node* top = st.top();
st.pop();
cout << top->data_ << " ";
if (top->right_ != nullptr) st.push(top->right_);
if (top->left_ != nullptr) st.push(top->left_);
}
cout << endl;
}
// 非递归中序遍历
void inOrder() {
cout << "[Not Recursion]Inorder Traversal: ";
if (root_ == nullptr) return;
stack<Node*> st;
Node* cur = root_;
while (cur != nullptr) {
st.push(cur);
cur = cur->left_;
}
while (!st.empty() || cur != nullptr) {
if (cur != nullptr) {
st.push(cur);
cur = cur->left_;
} else {
Node* top = st.top();
st.pop();
cout << top->data_ << " ";
cur = top->right_;
}
}
cout << endl;
}
// 非递归后序遍历
void postOrder() {
cout << "[Not Recursion]Postorder Traversal: ";
if (root_ == nullptr) return;
stack<Node*> st, tmp;
st.push(root_);
while (!st.empty()) {
Node* top = st.top();
st.pop();
tmp.push(top);
if (top->left_ != nullptr) st.push(top->left_);
if (top->right_ != nullptr) st.push(top->right_);
}
while (!tmp.empty()) {
Node* top = tmp.top();
cout << top->data_ << " ";
tmp.pop();
}
cout << endl;
}
// 非递归层序遍历
void levelOrder() {
cout << "[Not Recursion]Levelorder Traversal: ";
if (root_ == nullptr) return;
queue<Node*> qe;
qe.push(root_);
while (!qe.empty()) {
Node* front = qe.front();
if (front->left_ != nullptr) qe.push(front->left_);
if (front->right_ != nullptr) qe.push(front->right_);
qe.pop();
cout << front->data_ << " ";
}
cout << endl;
}
2. 常见的算法问题
2.1 区间元素查找
在 BST 树中查找某个区间内的元素值，可以采用 BST 中序遍历的性质，即其中序遍历是一个升序的序列。同时，在搜索的过程中，可以加入一些优化手段：如果当前元素的值小于等于左边界，那么就无需进入其左子树进行搜索；如果当前元素的值大于等于右边界，那么就无需进入其右子树进行搜索。
其代码实现如下：
// 递归搜索满足区间的元素值
void findValues(Node* node, vector<T>& vec, int i, int j) {
if (node != nullptr) {
if (node->data_ > i) {
// 如果当前节点的值小于等于左边界
// 则当前节点的左子树没有必要去搜索
findValues(node->left_, vec, i, j);
}
if (node->data_ >= i && node->data_ <= j) {
vec.push_back(node->data_);
}
if (node->data_ < j) {
// 如果当前结点的值大于等于右边界
// 则当前节点的右子树没有必要去搜索
findValues(node->right_, vec, i, j);
}
}
}
练习题目: 938. 二叉搜索树的范围和 - 力扣（LeetCode）
2.2 判断一棵树是否为BST树
由于 BST 树左子树的节点一定小于当前节点，而右子树的节点一点大于当前节点，如果我们使用如下代码来判断一棵树是否为 BST 树：
bool isBSTree(Node* node) {
if (node == nullptr) return true;
if (node->left_ != nullptr && comp_(node->data_, node->left_->data_)) {
return false;
}
if (node->right_ != nullptr && comp_(node->data_, node->right_->data_)) {
return false;
}
return isBSTree(node->left_) && isBSTree(node->right_);
}
那么对于如下图所示的二叉树，上述代码依然会将其看成一个 BST 树：
但是，上图所示的二叉树并不是一颗 BST 树，这是因为上述代码仅仅只是在局部对 BST 树的性质进行了判断，但是从全局来看，就会出现问题。
因此，为了判断一棵树是否为 BST 树，依然需要采用其中序遍历的性质来进行判断，代码实现如下：
bool isBSTree(Node* node, Node*& preNode) {
if (node == nullptr) return true;
if (!isBSTree(node->left_, preNode)) {
return false;
}
if (preNode != nullptr) {
if (comp_(node->data_, preNode->data_)) {
return false;
}
}
preNode = node;
return isBSTree(node->right_, preNode);
}
练习题目：98. 验证二叉搜索树 - 力扣（LeetCode）
2.3 子树问题
子树问题即现在有两颗二叉树，判断其中一颗二叉树是否为另一颗二叉树的子树。
我们可以先在父树中找寻与子树根节点的值相同的节点，找到该节点后，通过前序遍历同时遍历父树和子树，如果遍历过程中的结构和值一样，则表示是子树，否则则不是。
其代码实现如下：
bool isChildTree(BSTree<T, Comp>& child) {
// 在当前二叉树上找到子树的根节点
if (child.root_ == nullptr) {
return true;
}
Node* cur = root_;
while (cur != nullptr) {
if (cur->data_ == child.root_->data_) {
break;
} else if (comp_(cur->data_, child.root_->data_)) {
cur = cur->right_;
} else {
cur = cur->left_;
}
}
if (cur == nullptr) return false;
return isChildTree(cur, child.root_);
}
bool isChildTree(Node* father, Node* child) {
if (father == nullptr && child == nullptr) return true;
// 子树有 但是父树没有
if (father == nullptr) return false;
// 子树没有 但是父树有
if (child == nullptr) return true;
if (father->data_ != child->data_) {
return false;
}
return isChildTree(father->left_, child->left_)
&& isChildTree(father->right_, child->right_);
}
练习题目：剑指 Offer 26. 树的子结构 - 力扣（LeetCode）
2.4 最近的公共祖先
对于 BST 树而言，由于其满足左子树的值小于当前结点的值，右子树的值大于当前节点的值，所以可以从根节点开始：
- 如果当前节点的值小于两个所给节点的值，则说明所给的两个节点位于当前节点的右子树，则在当前节点的右子树中进行查找；
- 如果当前节点的值大于两个所给节点的值，则说明所给的两个节点位于当前节点的左子树，则在当前节点的左子树中进行查找；
- 如果当前节点的值大于其中的一个节点而小于另一个节点，则说明当前节点为所给节点的公共祖先；
代码实现如下：
Node* getLCA(Node* node, int val1, int val2) {
if (node == nullptr) return nullptr;
if (comp_(node->data_, val1) && comp_(node->data_, val2)) {
return getLCA(node->right_, val1, val2);
} else if (comp_(val1, node->data_) && comp_(val2, node->data_)) {
return getLCA(node->left_, val1, val2);
} else {
return node;
}
}
练习题目：236. 二叉树的最近公共祖先 - 力扣（LeetCode）
2.5 镜像翻转
镜像翻转一颗二叉树只需前序遍历，然后交换左子树和右子树即可，其代码实现如下：
void invertTree(Node* node) {
if (node == nullptr) return;
Node* tmp = node->left_;
node->left_ = node->right_;
node->right_ = tmp;
invertTree(node->left_);
invertTree(node->right_);
}
练习题目：226. 翻转二叉树 - 力扣（LeetCode）
2.6 对称二叉树
判断一颗二叉树是否为对称树的代码实现如下：
bool isSymmetricTree(Node* node1, Node* node2) {
if (node1 == nullptr && node2 == nullptr) return true;
if (node1 == nullptr || node2 == nullptr) return false;
if (node1->data_ != node2->data_)
return false;
return isSymmetricTree(node1->left_, node2->right_)
&& isSymmetricTree(node1->right_, node2->left_);
}
练习题目：101. 对称二叉树 - 力扣（LeetCode）
2.7 根据前序遍历和中序遍历重建二叉树
例如，现在一颗二叉树的前序遍历和中序遍历的结果分别如下：
- 前序遍历：58 24 0 50 34 41 67 62 60 64 69 78
- 中序遍历：0 5 24 34 41 58 60 62 64 67 69 78
分析可知，前序遍历的第一个元素即为二叉树的根节点，而在中序遍历中，根节点左侧的元素为根节点左子树上的元素，右侧的元素为根节点右子树上的元素，然后就可以在前序遍历中可以找到其左、右子树，且前序遍历中开头的元素即为当前子树的根节点，所以按照上述规律，根据前序遍历和中序遍历重建二叉树的过程如下：
- 查看前序遍历开头元素的值即为当前子树根结点的值；
- 在中序遍历中找到该值所处的位置，那么其左侧即为该节点的左子树，其右侧即为该节点的右子树，分别获取左子树的元素个数 l 和右子树的元素个数 r；
- 在前序遍历中，第一个元素之后的 l 个元素即为左子树，再往后 r 个元素即为右子树；
- 此时，前序遍历中左子树序列的开头元素即为当前子树根结点的值，然后重复上述步骤，即可重建二叉树；
其代码实现如下：
/**
* @brief 根据前序遍历和中序遍历递归构建二叉树
*
* @param preOrderVec 前序序列
* @param inOrderVec 中序序列
* @param preStart 前序序列的起始索引
* @param preEnd 前序序列的结束索引
* @param inStart 中序序列的起始索引
* @param inEnd 中序序列的结束索引
*/
Node* build(const vector<T>& preOrderVec, const vector<T>& inOrderVec,
int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) return nullptr;
// 创建当前子树的根节点
Node* node = new Node(preOrderVec[preStart]);
for (int i = inStart; i <= inEnd; i++) {
// 在中序序列中找寻目标元素 即为当前子树的根节点
if (preOrderVec[preStart] == inOrderVec[i]) {
node->left_ = build(preOrderVec, inOrderVec, preStart + 1,
preStart + (i - inStart), inStart, i - 1);
node->right_ = build(preOrderVec, inOrderVec,
preStart + (i - inStart) + 1, preEnd, i + 1, inEnd);
return node;
}
}
return node;
}
练习题目：105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
2.8 判断二叉树是否为平衡树
要判断一棵二叉树是否为平衡树，由于我们事先无法知道二叉树的深度，因此在递归二叉树的过程中，可以在 “归” 的过程中来求出来左、右子树的高度，判断其是否满足平衡的条件，即采用后序遍历的方式，代码实现如下：
bool isBalanceTree() {
bool res = true;
isBalanceTree(root_, 0, res);
return res;
}
int isBalanceTree(Node* node, int l, bool& flag) {
if (node == nullptr) return l;
int left = isBalanceTree(node->left_, l + 1, flag);
if (!flag) return left;
int right = isBalanceTree(node->right_, l + 1, flag);
if (!flag) return right;
if (abs(left - right) > 1) {
flag = false;
}
return max(left, right);
}
练习题目：110. 平衡二叉树 - 力扣（LeetCode）
2.9 求中序遍历倒数第k个节点
其代码实现如下：
int i = 1;
// 求中序遍历倒数第k个节点
Node* getVal(Node* node, int k) {
if (node == nullptr) return nullptr;
int tmp = i + 1;
Node* right = getVal(node->right_, k);
if (right != nullptr) {
return right;
}
if (i++ == k) {
return node;
}
return getVal(node->left_, k);
}
练习题目：剑指 Offer 54. 二叉搜索树的第k大节点 - 力扣（LeetCode）
完整的 BST 树代码实现见 Kohirus-Github
原文链接: https://www.cnblogs.com/tuilk/p/17056388.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/312476
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
