二叉搜索樹 並查集

二叉搜索樹 並查集

BST：二叉搜索樹

二叉搜索樹的特點：左孩子<根節點<右孩子 二叉搜索樹可以有效的管理數的集合

（1）查找

查找數值，大於根節點向右查找，小於根節點向做查找，遞歸直到找到或者找不到為止。

（2）插入

類似於查找，找到相應的位置之後，將那個位置插入新的節點即可。

（3）刪除

刪除就稍微的復雜一點： 需要刪除的點沒有左孩子，直接將右孩子提上去 需要刪除的點的左孩子沒有右孩子，直接將左孩子提上去 除此之外，將左孩子的子孫的最大節點提上去。 代碼實現：

struct node{
    int data;
    node* lch,*rch;
};
node* insert(node* p,int x){
    if(p==NULL){
        node* q = new node;
        q->data = x;
        q->lch = q->rch = NULL;
        return q;
    }else{
        if(xlch = (p->lch,x);
        else p->rch = insert(p->rch,x);
        return p;
    }
}
bool find(node* p,int x){
    if(p==NULL) return false;
    if(xdata) return find(p->lch,x);
    else if(x==p->data) return true;
    else return find(p->rch,x);
}
node* remove(node* p,int x){
    //分三種情況考慮
    if(p==NULL) return NULL;
    else if(xdata) p->lch = remove(p->lch,x);
    else if(x>p->data) p->rch = remove(p->rch,x);
    else if(p->lch == NULL){
        node* q = p->rch;
        delete p;
        return q;
    }else if(p->lch->rch == NULL){
        node * q = p->lch;//直接將左孩子提上去，將新節點的右孩子就是原來刪除節點的右孩子。
        q->rch = p->rch;
        delete p;
        return q;
    }else{
         node* q;
         for(q=p->lch;q->rch->rch!=NULL;q=q->rch);
         node* r = q->rch;
         q->rch =r->lch;
         r->lch = p->lch;
         r->rch = p->rch;
         delete p;
         return r;
    }
}

並查集

並查集是一種高效管理元素分組的一種數據結構，並查集可以進行合並操作，但是不能進行分割操作。並查集的每一組代表著一棵樹。 進行的操作： 查詢元素是否是同一個組； 合並不同組的元素。 （1）初始化: 最開始的時候，准備n個點表示n個元素，一開始不存在邊。 （2）從一組的根向另一個組的根連邊，合並一起（記錄樹的高度（rank），rank小的向大的連邊） （3）查詢倆個元素是否是同一個組，就是查找倆個元素的根是否相同。相同：是一組； 不同：不是一組 代碼實現：

#include 

using namespace std;
const int MAX = 100;
int par[MAX],rank[MAX];

void init(int n){
    for(int i=0;i