掌握顺序查找、折半查找；二叉排序树的创建、查找、插入、删除。

一、顺序查找（线性查找）

顺序查找是一种基本的查找方法，也称为线性查找。它的基本思想是从表的一端开始，顺序扫描线性表，逐个将其关键字与给定值k相比较，直到找到关键字等于k的数据元素或者扫描结束也没有找到，这时查找过程结束。因此，顺序查找的时间复杂度为O(n)，其中n为线性表的长度。代码实现如下：

int SequentialSearch(int a[], int n, int key) {
    for (int i = 0; i < n; ++i) {
        if (a[i] == key) {
            return i; // 返回关键字在数组中的下标
        }
    }
    return -1; // 关键字不存在
}

二、折半查找（二分查找）

折半查找是一种基于有序序列进行查找的算法，也称为二分查找。它的基本思想是将有序序列分成两部分，取中间位置的记录与查找值进行比较，如果相等，则查找成功；否则，根据中间位置记录的大小关系，将待查记录限定到前半部分或后半部分，继续按照此方法进行查找，直到找到关键字或者查找区间为空为止。因此，折半查找的时间复杂度为O(logn)，其中n为有序序列的长度。代码实现如下：

int BinarySearch(int a[], int n, int key) {
    int left = 0, right = n - 1, mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (a[mid] == key) {
            return mid; // 返回关键字在数组中的下标
        }
        else if (a[mid] < key) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return -1; // 关键字不存在
}

三、二叉排序树

二叉排序树是一种特殊的二叉树，它的每个节点都包含一个关键字，并且左子树中所有节点的关键字都比根节点的关键字小，右子树中所有节点的关键字都比根节点的关键字大。因此，二叉排序树的中序遍历结果是一个递增的有序序列。

1. 二叉排序树的创建

二叉排序树的创建可以使用递归方式实现。对于给定的一组关键字，首先将第一个关键字作为根节点，然后将剩余的关键字分别插入到左子树或右子树中，直到所有关键字都被插入到二叉排序树中为止。

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

void insert(TreeNode **root, int val) {
    if (*root == NULL) {
        *root = (TreeNode *)malloc(sizeof(TreeNode)); // 创建一个新节点
        (*root)->val = val;
        (*root)->left = (*root)->right = NULL;
    }
    else if (val < (*root)->val) {
        insert(&(*root)->left, val); // 插入到左子树中
    }
    else if (val > (*root)->val) {
        insert(&(*root)->right, val); // 插入到右子树中
    }
}

2. 二叉排序树的查找

二叉排序树的查找也可以使用递归方式实现。对于给定的关键字，首先将其与根节点的关键字进行比较，如果相等，则查找成功；否则，根据关键字的大小关系，分别在左子树或右子树中继续进行查找。

TreeNode *search(TreeNode *root, int val) {
    if (root == NULL || root->val == val) {
        return root;
    }
    else if (val < root->val) {
        return search(root->left, val); // 在左子树中查找
    }
    else {
        return search(root->right, val); // 在右子树中查找
    }
}

3. 二叉排序树的插入

二叉排序树的插入操作与创建操作类似，只是需要注意插入的关键字不能与已有的关键字相同。

void insert(TreeNode **root, int val) {
    if (*root == NULL) {
        *root = (TreeNode *)malloc(sizeof(TreeNode)); // 创建一个新节点
        (*root)->val = val;
        (*root)->left = (*root)->right = NULL;
    }
    else if (val < (*root)->val) {
        insert(&(*root)->left, val); // 插入到左子树中
    }
    else if (val > (*root)->val) {
        insert(&(*root)->right, val); // 插入到右子树中
    }
    else {
        printf("The key already exists!\n"); // 关键字已经存在
    }
}

4. 二叉排序树的删除

二叉排序树的删除操作比较复杂，需要考虑多种情况。具体步骤如下：

- 如果待删除节点是叶子节点，则直接删除即可。
- 如果待删除节点只有一个孩子节点，则将其孩子节点连接到待删除节点的父节点上即可。
- 如果待删除节点有两个孩子节点，则将其右子树中的最小节点（或左子树中的最大节点）替换到待删除节点的位置上，并将该最小节点（或最大节点）删除。

TreeNode *delete(TreeNode *root, int val) {
    if (root == NULL) {
        return NULL; // 待删除节点不存在
    }
    if (val < root->val) {
        root->left = delete(root->left, val); // 在左子树中删除
    }
    else if (val > root->val) {
        root->right = delete(root->right, val); // 在右子树中删除
    }
    else {
        if (root->left == NULL && root->right == NULL) {
            free(root); // 叶子节点直接删除
            root = NULL;
        }
        else if (root->left == NULL) {
            TreeNode *temp = root;
            root = root->right; // 只有右孩子，则右孩子顶替删除节点
            free(temp);
        }
        else if (root->right == NULL) {
            TreeNode *temp = root;
            root = root->left; // 只有左孩子，则左孩子顶替删除节点
            free(temp);
        }
        else {
            TreeNode *temp = findMin(root->right); // 在右子树中查找最小节点
            root->val = temp->val; // 最小节点替换待删除节点
            root->right = delete(root->right, temp->val); // 删除最小节点
        }
    }
    return root;
}

其中，findMin函数用于查找某个节点子树中的最小节点。

TreeNode *findMin(TreeNode *root) {
    if (root == NULL) {
        return NULL;
    }
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}