Binary Search Tree二叉搜索树

定义

二叉搜索树是这样的一颗二叉树，如果左子树不空，则左子树上的所有结点都比根结点小。如果右子树不空，则右子树上的所有结点都比根结点大。左子树和右子树也是一颗二叉搜索树。

构建

插入结点x,比较x和根结点的值，如果x大，则把x插入右子树，x小，则把x插入左子树。

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
};

TreeNode* BSTInsert(TreeNode* root, int value) {
    if (root == nullptr) {
        root = (TreeNode*)malloc(sizeof(TreeNode));
        return root;
    }
    if (root->value > value) {
        root->left = BSTInsert(root->left,value);
    }
    else if (root->value < value) {
        root->right = BSTInsert(root->right,value);
    }
    return root;
}

查找

查找某个值，和根结点比较，如果大于根结点，则继续到右子树查找，如果小于根结点，则继续到左子树查找，如果刚好等于，则找到了。

TreeNode* searchInBST(TreeNode* t,int value) {
    if (t == nullptr) {
        return t;
    }
    if (t->value == value) {
        return t;
    }
    if (t->value > value) {
        return searchInBST(t->left,value);
    }
    return searchInBST(t->right,value);
}

删除

删除情况复杂些，因为删除某个结点，可能导致二叉搜索树可能不再是一颗二叉搜索树。如果待删除结点是叶子结点，直接删除，没有影响。如果只有一颗子树，则用子树代替当前结点。如果有两棵子树，则需要找到左子树的最大值或右子树的最小值来代替待删除结点，然后删掉左子树的最大值或者右子树的最小值。

TreeNode* maxValueNode(TreeNode* root) {
    TreeNode* current = root;
    while (current && current->right != nullptr) {
        current = current->right;
    }
    return current;
}

TreeNode* deleteNodeFromBST(TreeNode* t, int value) {
    if (t == nullptr) {
        return t;
    }
    if (value < t->value) {
        t->left = deleteNodeFromBST(t->left, value);
    }
    else if (value > t->value) {
        t->right = deleteNodeFromBST(t->right, value);
    }
    else {
        if (t->left == nullptr && t->right == nullptr) {
            free(t);
            return nullptr;
        }
        else if (t->left == nullptr && t->right != nullptr) {
            TreeNode* tmpT = t->right;
            free(t);
            return tmpT;
        }
        else if (t->right == nullptr && t->left != nullptr) {
            TreeNode* tmpT = t->left;
            free(t);
            return tmpT;
        }
        else {
            TreeNode* maxNode = maxValueNode(t->left);
            t->value = maxNode->value;
            t->left = deleteNodeFromBST(t->left, maxNode->value);
        }
    }
    return t;
}