树结构算法总结(5) 二叉查找树BST

Posted by SkyHigh on October 6, 2016

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;
        }
    }