Previous
树结构算法总结(1) 二叉树的遍历
树结构算法总结(2) 线段树Segment Tree
树结构算法总结(3) 字典树Trie Tree
树结构算法总结(4) 堆Heap
树结构算法总结(5) 二叉查找树BST
二叉查找树的概念
二叉查找树定义为：
空树或者具有如下特征的树：
- 若左子树非空，则左子树上所有节点值均小于根节点值
- 若右子树非空，则右子树上所有节点值均大于根节点值
- 左子树和右子树也分别是BST
若树的高度差小于等于1，并且左右子树也是平衡的，那么该树为平衡二叉树。
我们定义树节点结构如下：
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
插入
思路
使用递归，如果插入的值比根节点值小，则插入到左边，否则插入到右边。
代码
TreeNode* insertNode(TreeNode* &root, TreeNode* &node) {
// write your code here
if(!root)
return node;
recursive(root, node);
return root;
}
void recursive(TreeNode*& r, TreeNode* node){
if(r){
if(r->val>node->val)
recursive(r->left, node);
else
recursive(r->right, node);
}
else
r = node;
}
创建二叉树
思路
使用上述插入方法即可。
代码
void Create(TreeNode* &root, vector<int> r) {
// write your code here
int n = r.size();
for(int i=0;i<n;i++){
TreeNode* cur = new TreeNode(r[i]);
insertNode(root, cur);
}
}
查找
思路
递归查找。
代码
TreeNode* Search(TreeNode* root, int val) {
// write your code here
if(!root)return NULL;
else if(root->val>val)return Search(root->left, val)
else if(root->val==val)return root;
else return Search(root->right, val);
}
迭代器
思路
结合中序遍历和栈来实现。
代码
class BSTIterator {
public:
stack<TreeNode*> s;
//param root: The root of binary tree.
BSTIterator(TreeNode *root) {
// write your code here
while(root){
s.push(root);
root = root->left;
}
}
//return: True if there has next node, or false
bool hasNext() {
// write your code here
return !s.empty();
}
//return: return next node
TreeNode* next() {
// write your code here
TreeNode* cur = s.top();
s.pop();
TreeNode* tmp = cur;
tmp = tmp->right;
while(tmp){
s.push(tmp);
tmp = tmp->left;
}
return cur;
}
};
删除
思路
考虑被删除节点的以下几种情况：
- 如果为叶子节点，则直接删除；
- 如果只有左子树或右子树，则删除该节点，并把该节点的左（右）子树连到删除节点的父节点上；
- 如果有双子树，则寻找该节点的前驱节点（在该节点的左孩子节点上的右分支最后一个节点上，即
r->left->right->right->right...，或者在该节点的右孩子节点上的左分支最后一个节点上，即r->right->left->left->left...）。
下面我们在找前驱的时候只考虑左子树上的前驱。
代码
TreeNode* removeNode(TreeNode* root, int value) {
// write your code here
removeBST(root, value);
return root;
}
void removeBST(TreeNode* &root, int value){
if(root){
if(root->val==value)remove(root);
else if(root->val>value)removeBST(root->left, value);
else removeBST(root->right, value);
}
}
void remove(TreeNode* &r){
TreeNode* tmp;
# 不存在左孩子，说明可能是只有右孩子或者为叶子节点
if(!r->left){
tmp = r;
r = r->right;
delete tmp;
}
# 只有左孩子
else if(!r->right){
tmp = r;
r = r->left;
delete tmp;
}
# 有双孩子
else{
TreeNode* pre = r;
tmp = r->left;
while(tmp->right){
pre = tmp;
tmp = tmp->right;
}
r->val = tmp->val;
if(pre!=r)
pre->right = tmp->left;
else
pre->left = tmp->left;
delete tmp;
}
}