PTA甲级

Binary Search Tree | 二叉查找树

2019-08-02  本文已影响0人  zilla

参考书:胡凡、曾磊《算法笔记》

二叉查找树BST

递归定义
性质

BST的中序遍历结果是有序的。

BST的基本操作

查找

区别于普通二叉树的查找(递归遍历左右子树),BST的查找是每次选择一棵子树查找,是从树根到查找结点的一条路径
最坏复杂度 O(h),h是二叉查找树的高度。
void search(Node* root, int x)

插入

先查找, 查找成功,结点已存在,不用插入;查找失败,root == NULL,在此处插入
复杂度O(h),h是二叉查找树的高度。
⚠️可能改变树的结构,故要传引用!!!
void insert(Node* &root, int x)

建BST

Node* CreateBST(int data[], int nn)
一组相同的数字,仅仅插入顺序不同,生成的二叉树结构也可能不同。

删除

void delete(Node* &root, int x)
⚠️ 传引用
要保证删除操作后仍然是二叉查找树。
复杂度O(h),h是二叉查找树的高度。

  1. root == NULL,不存在权值为x的结点
  2. root->data == x
  1. root->data > x,在左子树中递归
  2. root->data < x,在右子树中递归
重要概念

前驱 — BST中比结点权值小的最大结点
后继 — BST中比结点权值大的最小结点

图源:巴特曼@cnblogs
总是优先删除前驱/后继,容易使树的左右子树高度极度不平衡,甚至使BST退化为一条链。

Solution:

  1. 交替删除前驱、后继
  2. 记录子树高度,从较高子树删除结点

例题

1043 Is It a Binary Search Tree (25 分)
给定二叉树的插入序列s,问序列s是否是该二叉树或该二叉树左右子树对调后二叉树的先序遍历序列。若是,输出对应的后序遍历序列。
⚠️允许插入key相同的结点(右子树结点key >= 根结点的key)
⚠️插入时,必须有root->lchild = NULL, root->rchild = NULL;

#include <cstdio>
#include <vector>

using namespace std;
struct Node {
    int key;
    Node *lchild, *rchild;
};
int nn, cnt1 = 0, cnt2 = 0;
vector<int> seq;

void insertNode(Node *&root, int x) {
    if (root == NULL) {
        root = new Node;
        root->key = x;
        root->lchild = NULL, root->rchild = NULL;
    } else {
        if (x < root->key) {
            insertNode(root->lchild, x);
        } else insertNode(root->rchild, x);
    }
}

void pre_order(Node *root) {
    if (root->key == seq[cnt1]) cnt1++;
    else return;
    if (root->lchild) pre_order(root->lchild);
    if (root->rchild) pre_order(root->rchild);
}

void mirror_pre_order(Node *root) {
    if (root->key == seq[cnt2]) cnt2++;
    else return;
    if (root->rchild) mirror_pre_order(root->rchild);
    if (root->lchild) mirror_pre_order(root->lchild);
}

void post_order(Node *root) {
    if (root == NULL) return;
    if (root->lchild) post_order(root->lchild);
    if (root->rchild) post_order(root->rchild);
    printf("%d", root->key);
    cnt1--;
    if (cnt1 > 0) printf(" ");
}

void mirror_post_order(Node *root) {
    if (root == NULL) return;
    if (root->rchild) mirror_post_order(root->rchild);
    if (root->lchild) mirror_post_order(root->lchild);
    printf("%d", root->key);
    cnt2--;
    if (cnt2 > 0) printf(" ");
}

int main() {
    Node *root = NULL;
    scanf("%d", &nn);
    int temp;
    for (int i = 0; i < nn; ++i) {
        scanf("%d", &temp);
        seq.emplace_back(temp);
        insertNode(root, temp);
    }
    pre_order(root);
    if (cnt1 == nn) {
        puts("YES");
        post_order(root);
    } else {
        mirror_pre_order(root);
        if (cnt2 == nn) {
            puts("YES");
            mirror_post_order(root);
        } else puts("NO");
    }
    return 0;
}
上一篇 下一篇

猜你喜欢

热点阅读