二叉搜索树

性质

• 左子树 < 根节点
• 右子树 > 根节点
• 树的结构与插入顺序有关，树型结构不稳定（时间复杂度不稳定），可能退化为链表
• 插入 删除 查找 的 时间复杂度：O(h) ~ O(lgh)，与树的高度成正比，最好情况时间复杂度是以2为底的对数。
• 中序遍历有序，有序输出节点
• 能解决范围性查找
• 能找到最大最小值
• 能找到第k大的节点

用途

• 解决与排名相关的检索需求

删除操作

• 删除叶子节点：直接删除
• 删除出度为1的节点：删除出度为1的节点得调整树的结构
• 删除出度为2的节点：找到 以该节点为根节点的子树 的 前驱节点 或者 后继节点，交换他们，最后 问题转化为 删除出度为1的节点了

基础版

/*
二叉查找树 

*/


#include <stdio.h>
#include <stdlib.h>
#include <time.h>



/***********结构定义***********/ 

typedef struct Node{
    int value; //节点存储值
    struct Node *left, *right; 
}Node;





/***********结构操作 ***********/ 

//开辟一个节点 
Node *getNewNode(int key) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->value = key;
    p->left = p->right = NULL;
    return p;
}

Node *insertNode(Node *root, int target) {
    if (root == NULL) return getNewNode(target);
    if (root->value == target) return root;
    if (root->value > target) {
        root->left = insertNode(root->left, target);
    } else {
        root->right = insertNode(root->right, target);
    }
    return root;
}


void clear(Node *root) {
    if (root == NULL) return ;
    clear(root->left);
    clear(root->right);
    free(root);
    return ;
}


// 查找 
int search(Node *root, int target) {
    if (root == NULL) return 0;
    if (root->value == target) return 1;
    if (root->value > target) {
        return search(root->left, target);
    }
    return search(root->right, target);
}


// precursor 前驱 
// predecessor 前任 
// 找到前驱节点 
Node *precursor(Node *root) {
    Node *p = root->left;
    while (p != NULL && p->right != NULL) {
        p = p->right;
    }
    return p;
}

// Successor后继
// 找到后继节点 
Node *successor(Node *root) {
    Node *p = root->right;
    while (p != NULL && p->left != NULL) {
        p = p->left;
    }
    return p;
} 


// 删除节点 
// root表示树的根节点 
Node *erase(Node *root, int target) {
    if (root == NULL) return root;
    if (root->value > target) {
        root->left = erase(root->left, target);
    } else if (root->value < target) {
        root->right = erase(root->right, target);
    } else { // 找到删除的节点 
        /*if (root->right == NULL && root->left == NULL) { //删除的节点 的 出度为0 
            free(root);
            return NULL;
        } else */if (root->right == NULL || root->left == NULL) { // 删除的节点 的 出度为1 
            Node *tmp = (root->left ? root->left : root->right);
            free(root);
            return tmp;
        } else { //出度2 
            //转化问题 把 删除出度为2的节点问题 转化到 删除出度为1的节点的问题 
            // 前驱 或者 后继 节点的出度都为1 
            Node *tmp = precursor(root); //找到前驱节点
            root->value = tmp->value;  //把前驱节点的值赋值给需要删除的节点 
            root->left = erase(root->left, tmp->value); //转化为删除前驱节点（出度为1） 
        }
    }
    return root;
}




void in_order(Node *root) {
    if (root == NULL) return ;
    in_order(root->left);
    printf("%d ", root->value);
    in_order(root->right);
    return ;
}

int main() {
    srand(time(NULL));
    
    int n;
    scanf("%d", &n);
    Node *root = NULL;
    for (int i = 0; i < n; i++) {
        int num = rand() % 100;
        printf("%d ", num);
        root = insertNode(root, num);
    } 
    printf("\n-------------------------\n");
    in_order(root); putchar(10);
    
    while (scanf("%d", &n) != EOF) {
        printf("delete node is %d\n", n);
        root = erase(root, n);
        in_order(root); putchar(10);
    }
    
    return 0;
}

升级版

/*
二叉查找树 
升级版 
*/


#include <stdio.h>
#include <stdlib.h>
#include <time.h>



/***********结构定义***********/ 

typedef struct Node{
    int value; //节点存储值
    int size; //表示 当前节点 + 左右子树的节点个数之和 
    struct Node *left, *right; 
}Node;

Node __NIL; //哨兵节点
#define NIL (&__NIL)
//初始化，在main之前初始化
__attribute__((constructor))
void init_INL() {
    NIL->value = -1;
    NIL->size = 0;
    NIL->left = NIL->right = NIL;
}

 



/***********结构操作 ***********/ 

//开辟一个节点 
Node *getNewNode(int key) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->value = key;
    p->left = p->right = NIL;
    p->size = 1;
    return p;
}

void update_size(Node *root) {
    root->size = root->left->size + root->right->size + 1;
    return ;
}

Node *insertNode(Node *root, int target) {
    if (root == NIL) return getNewNode(target);
    if (root->value == target) return root;
    if (root->value > target) {
        root->left = insertNode(root->left, target);
    } else {
        root->right = insertNode(root->right, target);
    }
    /*
    root->size = 0;
    if (root->left != NULL) root->size += root->left->size;
    if (root->right != NULL) root->size += root->right->size;
    */
    
    update_size(root);
    
    return root;
}


void clear(Node *root) {
    if (root == NIL) return ;
    clear(root->left);
    clear(root->right);
    free(root);
    return ;
}


// 查找 
int search(Node *root, int target) {
    if (root == NIL) return 0; //不存在 
    if (root->value == target) return 1; // 存在 
    if (root->value > target) {
        return search(root->left, target);
    }
    return search(root->right, target);
}


// precursor 前驱 
// predecessor 前任 
// 找到前驱节点 
Node *precursor(Node *root) {
    Node *p = root->left;
    while (p != NIL && p->right != NIL) {
        p = p->right;
    }
    return p;
}

// Successor后继
// 找到后继节点 
Node *successor(Node *root) {
    Node *p = root->right;
    while (p != NIL && p->left != NIL) {
        p = p->left;
    }
    return p;
} 


// 删除节点 
// root表示树的根节点 
Node *erase(Node *root, int target) {
    if (root == NIL) return root;
    if (root->value > target) {
        root->left = erase(root->left, target);
    } else if (root->value < target) {
        root->right = erase(root->right, target);
    } else { // 找到删除的节点 
        /*if (root->right == NULL && root->left == NULL) { //删除的节点 的 出度为0 
            free(root);
            return NULL;
        } else */if (root->right == NIL || root->left == NIL) { // 删除的节点 的 出度为1 
            Node *tmp = (root->left != NIL ? root->left : root->right);
            free(root);
            return tmp;
        } else { //出度2 
            //转化问题 把 删除出度为2的节点问题 转化到 删除出度为1的节点的问题 
            // 前驱 或者 后继 节点的出度都为1 
            Node *tmp = precursor(root); //找到前驱节点
            root->value = tmp->value;  //把前驱节点的值赋值给需要删除的节点 
            root->left = erase(root->left, tmp->value); //转化为删除前驱节点（出度为1） 
        }
    }
    update_size(root);
    return root;
}


//查找第k大 
int find_k(Node *root, int k) {
    
    //printf("root->value : %d, k : %d, left size : %d, right size : %d\n", root->value, k, root->left->size, root->right->size);
    if (root == NIL) return root->value; 
    if (root->right->size >= k) {
        return find_k(root->right, k);
    } 
    //右子树节点数量 + 自己 == k 
    if (root->right->size + 1 == k) { //当前节点符合条件 
        return root->value;
    }
    return find_k(root->left, k - (root->right->size + 1) ); //+1代表root本身 
}


void in_order(Node *root) {
    if (root == NIL) return ;
    in_order(root->left);
    printf("%d ", root->value);
    in_order(root->right);
    return ;
}

int main() {
    srand(time(NULL));
    
    int n;
    scanf("%d", &n);
    Node *root = NIL;
    for (int i = 0; i < n; i++) {
        int num = rand() % 100;
        printf("%d ", num);
        root = insertNode(root, num);
    } 
    printf("\n-------------------------\n");
    in_order(root); putchar(10);
    
//    while (scanf("%d", &n) != EOF) {
//        printf("delete node is %d\n", n);
//        root = erase(root, n);
//        in_order(root); putchar(10);
//        printf("delete is success\n"); 
//    }

    while (scanf("%d", &n) != EOF) {
        printf("select node is %d\n", n);
        n = find_k(root, n);
        in_order(root); putchar(10);
        printf("value : %d\n", n);
    }
    
    return 0;
}

刷题

110. 平衡二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int getHigth(TreeNode *root) {
        if (root == nullptr) return 0;
        return 1 + max(getHigth(root->left), getHigth(root->right));
    }

    int getHigth1(TreeNode *root) {
        if (root == nullptr) return 0;
        int lh = getHigth1(root->left);
        int rh = getHigth1(root->right);
        if (lh == -1 || rh == -1) return -1;
        if (abs(lh - rh) > 1) return -1;
        return 1 + max(lh, rh);
    }


    bool isBalanced(TreeNode* root) {
        return getHigth1(root) >= 0;

        if (root == nullptr) return true;
        int lh = getHigth(root->left);
        int rh = getHigth(root->right);
        if (abs(lh - rh) > 1) return false;
        return isBalanced(root->left) & isBalanced(root->right);
    }
};

剑指 Offer 54. 二叉搜索树的第k大节点

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    void in_order(const TreeNode *root, int& k, int& ans) {
        if (root->right != nullptr && k > 0) {
            in_order(root->right, k, ans);
        }
        
        if (--k == 0) {
            ans = root->val;
            return ;
        }
        if (root->left && k > 0) {
            in_order(root->left, k, ans);
        }
        return ;
    }

    int kthLargest(TreeNode* root, int k) {
        if (root == nullptr) return 0;
        int ans;
        in_order(root, k, ans);
        return ans;
    }
};

450. 删除二叉搜索树中的节点

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode *find_succ(TreeNode *root) {
        while (root->left) {
            root = root->left;
        }
        return root;
    }
    TreeNode* deleteNode(TreeNode* root, int& key) {
        if (root == nullptr) return root;
        if (root->val == key) {
            if (root->left == nullptr || root->right == nullptr) {
                TreeNode *tmp = root->left ? root->left : root->right;
                return tmp;
            }
            TreeNode *succ = find_succ(root->right);
            root->val = succ->val;
            root->right = deleteNode(root->right, succ->val);
            
        } else if (root->val > key) {
            root->left = deleteNode(root->left, key);
        } else {
            root->right = deleteNode(root->right, key);
        }
        return root;
    }
};

669. 修剪二叉搜索树

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == nullptr) return nullptr;
        if (root->val < low) return trimBST(root->right, low, high);
        if (root->val > high) return trimBST(root->left, low, high);
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        return root;
    }
};

235. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
        if (root == NULL) return NULL;
        //二分，排除一半
        if ( (root->val > p->val) && (root->val > q->val) ) {
            return lowestCommonAncestor(root->left, p, q);
        }
        if ( (root->val < p->val) && (root->val < q->val) ) {
            return lowestCommonAncestor(root->right, p, q);
        }
        // p、q分别在当前节点的左右子树，当前节点就是最近公共祖先
        return root;
}

501. 二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

• 结点左子树中所含节点的值 小于等于 当前节点的值
• 结点右子树中所含节点的值 大于等于 当前节点的值
• 左子树和右子树都是二叉搜索树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void in_order(TreeNode *root, int& val, int& valsize, int& maxsize, vector<int>& ret) {
        if (root->left) in_order(root->left, val, valsize, maxsize, ret);
        if (val == root->val) {
            ++valsize;
        } else {
            val = root->val;
            valsize = 1;
        }

        if (valsize == maxsize) {
            ret.push_back(val);
            maxsize = valsize;
        } else if (valsize > maxsize) {
            while (!ret.empty()) ret.pop_back();
            ret.push_back(val);
            maxsize = valsize;
        }
        if (root->right) in_order(root->right, val, valsize, maxsize, ret);
        return ;
    }
    vector<int> findMode(TreeNode* root) {
        vector<int> ret;
        if (root == nullptr) return ret;
        int val = 1e6, valsize = 1, maxsize = 1;
        in_order(root, val, valsize, maxsize, ret);
        return ret;
    }
};