二叉查找树

1. 定义

二叉查找树的递归定义：

• 二叉查找树是一棵空树
• 或者二叉查找树由根节点、左子树、右子树组成，其中左子树和右子树都是二叉查找树，且左子树所有节点的数据域均小于或等于根节点的数据域，左子树所有节点的数据域均大于根节点的数据域。

2. 基本操作

2.1. 查找元素

void search(node* root, int x){
    if(root=NULL){
        printf("search failed\n");
        return;
    }
    if(x==root->data) printf("%d\n",root->data);
    else if(x<root->data) search(root->lchild,x);
    else search(root->right,x);
}

2.2. 插入元素

void insert(node* &root, int x){
    if(root==NULL){
        root=newNode(x);
        return;
    }
    if(x==root->data) return; // 节点已存在
    else if(x<root->data) insert(root->lchild,x);
    else insert(root->right,x);
}

2.3. 建立二叉查找树

node* Create(int data[], int n){
    node* root=NULL;
    for(int i=0;i<n;i++){
        insert(root,data[i]);
    }
    return root;
}

2.4. 删除节点

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->data=pre->data;
            deleteNode(root->lchild,pre->data);
        }else{
            node* next=findMin(root->right);
            root->data=next->data;
            deleteNode(root->rchild,next->data);
        }
    }
    else if(root->data>x) deleteNode(root->lchild,x);
    else deleteNode(root->right,x);
}