考研笔记

板子：BST 的查找和插入

比根小去左子树，比根大去右子树。插入就是一次失败的查找：走到空位置，就在那里挂上新结点。

代码

BiTNode *BST_Search(BiTree T, int key) {     // 非递归查找；找不到返回 NULL
    while (T != NULL && key != T->data) {    // 树空了，或者找到了，就停
        if (key < T->data) T = T->lchild;    // 小于根：去左子树找
        else T = T->rchild;                  // 大于根：去右子树找
    }
    return T;
}
 
int BST_Insert(BiTree &T, int k) {           // 插入成功返回 1；已经有 k 返回 0
    if (T == NULL) {                         // 走到空位置：新结点就挂在这里
        T = (BiTNode *)malloc(sizeof(BiTNode));
        T->data = k;
        T->lchild = T->rchild = NULL;
        return 1;
    }
    if (k == T->data) return 0;              // 不允许重复关键字：插入失败
    if (k < T->data) return BST_Insert(T->lchild, k);
    return BST_Insert(T->rchild, k);
}
 
void Creat_BST(BiTree &T, int str[], int n) {   // 依次插入 n 个关键字，构造 BST
    T = NULL;                                // 从空树开始
    for (int i = 0; i < n; i++) BST_Insert(T, str[i]);
}
 
void printGE(BiTree T, int k) {              // 变形：从大到小输出所有 >= k 的关键字
    if (T == NULL) return;
    printGE(T->rchild, k);                   // 右 → 根 → 左，就是从大到小
    if (T->data < k) return;                 // 根比 k 小：左子树更小，不用再看
    printf("%d ", T->data);
    printGE(T->lchild, k);
}

复杂度：查找、插入的时间都是 ，平均 ，最坏退化成单支树时是 。非递归查找空间 ，递归插入空间 。

例：教材构造用的序列是 {45, 24, 53, 45, 12, 24}，重复的 45 和 24 插入失败，最后树里只有 4 个结点。

关键边界

位置为什么
BiTree &T 是引用走到空位置时要修改的是双亲的 lchild 或 rchild 指针本身。不写 &，新结点就挂不到树上。这是 408 算法题里最容易漏写的一个符号
查找的循环条件 T != NULL && key != T->data先判空再访问 T->data，&& 的顺序不能反
相等时返回 0教材的 BST 不允许重复关键字，相等时既不往左也不往右，直接插入失败
printGE 里先右后左BST 的中序是从小到大，反过来「右 → 根 → 左」就是从大到小

易错点

  • 新插入的结点一定是叶结点，是查找失败时路径上最后一个结点的孩子。
  • 删除结点只考手算，分三种情况，见 7.3.1 BST 删除。
  • 按有序序列依次插入会得到单支树，这时 ASL ，选择题常考。

链接

反向链接