二叉查找树

二叉查找树的基本操作

#include <cstdio>

const int maxn = 1010;

struct Node {
    int data;
    struct Node *lchild, *rchild;
} nodes[maxn];

//查找
void search(Node *root, int x) {
    if (x == root->data) {
        printf("%d\n", root->data);
    } else if (x < root->data) {
        search(root->lchild, x);
    } else {
        search(root->rchild, x);
    }
}

//插入
void insert(Node *&root, int x) {
    if (root == NULL) {
        root = new Node;
        root->data = x;
        root->lchild = root->rchild = NULL;
        return;
    }
    if (x < root->data) {
        insert(root->lchild, x);
    } else {
        insert(root->rchild, x);
    }
}

//建立
Node *create(int data[], int n) {
    Node *root = NULL;
    for (int i = 0; i < n; i++) {
        insert(root, data[i]);
    }
    return root;
}

Node *findMax(Node *root) {
    while (root->rchild != NULL) {
        root = root->rchild;
    }
    return root;
}

Node *findMin(Node *root) {
    while (root->lchild != NULL) {
        root = root->lchild;
    }
    return root;
}

//删除
void deleteNode(Node *&root, int x) {
    if (root == NULL) {
        return;
    }
    if (root->data == x) {
        if (root->lchild == NULL && root->rchild == NULL) {//叶子结点直接删除
            root = NULL;
        } else if (root->lchild != NULL) {
            Node *pre = findMax(root->lchild);//找root前驱
            root->data = pre->data;//前驱覆盖root
            deleteNode(root->lchild, pre->data);//删前驱
        } else {
            Node *next = findMin(root->rchild);
            root->data = next->data;
            deleteNode(root->rchild, next->data);
        }
    } else if (root->data > x) {
        deleteNode(root->lchild, x);
    } else {
        deleteNode(root->rchild, x);
    }
}

对二叉查找树进行中序遍历，遍历的结果是有序的。

1043 Is It a Binary Search Tree

1064 Complete Binary Search Tree

1099 Build A Binary Search Tree