이 진 트 리 의 삽입,삭제,찾기

이 진 트 리 는 다음 과 같은 조건 을 만족 시 키 는 이 진 트 리 입 니 다.1.왼쪽 트 리 의 모든 노드 수 치 는 뿌리 절 점 치보다 작 습 니 다.2.오른쪽 트 리 의 모든 노드 수 치 는 뿌리 절 점 치보다 작 지 않 습 니 다.3.좌우 트 리 도 상기 두 가지 조건 을 만족 시 킵 니 다.
이 진 트 리 의 삽입 과정 은 다음 과 같다.1.현재 이 진 트 리 가 비어 있 으 면 삽 입 된 요 소 는 뿌리 노드 이 고 2.삽 입 된 요소 값 이 뿌리 노드 값 보다 작 으 면 요 소 를 왼쪽 트 리 에 삽입 하고 3.삽 입 된 요소 값 이 뿌리 노드 값 보다 작 지 않 으 면 요 소 를 오른쪽 트 리 에 삽입 합 니 다.
이 진 트 리 의 삭 제 를 찾 고 세 가지 상황 으로 나 누 어 처리 합 니 다.1.p 는 잎 노드 이 고 이 노드 를 직접 삭제 한 다음 에 부모 노드 의 지침(뿌리 노드 와 뿌리 노드 가 아 닌 것 으로 나 누 는 것 을 주의 하 십시오)을 수정 합 니 다.그림 a 와 같 습 니 다.
2.p 는 하나의 노드(즉,왼쪽 나무 나 오른쪽 나무 만 있 음)입 니 다.p 의 하위 트 리 를 p 의 아버지 노드 와 연결 시 키 고 p 를 삭제 하면 됩 니 다.(루트 노드 와 루트 노드 가 아 닌 것 으로 나 누 기;그림 b.
3.p 의 왼쪽 나무 와 오른쪽 나무 가 모두 비어 있 지 않다.p 의 후계 y 를 찾 습 니 다.y 는 왼쪽 트 리 가 없 기 때문에 y 를 삭제 하고 Y 의 아버지 노드 를 y 의 오른쪽 트 리 의 아버지 노드 로 만 들 고 y 의 값 으로 p 의 값 을 대체 할 수 있 습 니 다.또는 방법 두 번 째 는 p 의 전구 x 를 찾 는 것 이다.x 는 오른쪽 나무 가 없 기 때문에 x 를 삭제 하고 x 의 아버지 노드 를 y 의 왼쪽 나무의 아버지 노드 로 만 들 수 있다.그림 c.
  


노드 를 삽입 하 는 코드:

struct node
{
    int val;
    pnode lchild;
    pnode rchild;
};
pnode BT = NULL;

//         
pnode insert(pnode root, int x)
{
    pnode p = (pnode)malloc(LEN);
    p->val = x;
    p->lchild = NULL;
    p->rchild = NULL;
    if(root == NULL){
        root = p;    
    }    
    else if(x < root->val){
        root->lchild = insert(root->lchild, x);    
    }
    else{
        root->rchild = insert(root->rchild, x);    
    }
    return root;
}
//          
void insert_BST(pnode q, int x)
{
    pnode p = (pnode)malloc(LEN);
    p->val = x;
    p->lchild = NULL;
    p->rchild = NULL;
    if(q == NULL){
        BT = p;
        return ;    
    }        
    while(q->lchild != p && q->rchild != p){
        if(x < q->val){
            if(q->lchild){
                q = q->lchild;    
            }    
            else{
                q->lchild = p;
            }        
        }    
        else{
            if(q->rchild){
                q = q->rchild;    
            }    
            else{
                q->rchild = p;    
            }
        }
    }
    return;
} 

노드 의 코드 를 찾 습 니 다

pnode search_BST(pnode p, int x)
{
    bool solve = false;
    while(p && !solve){
        if(x == p->val){
            solve = true;    
        }    
        else if(x < p->val){
            p = p->lchild;    
        }
        else{
            p = p->rchild;    
        }
    }
    if(p == NULL){
        cout << "    " << x << endl;    
    } 
    return p;
}

노드 의 코드 를 삭제 합 니 다

bool delete_BST(pnode p, int x) //      ，           
{
    bool find = false;
    pnode q;
    p = BT;
    while(p && !find){  //       
        if(x == p->val){  //       
            find = true;    
        }    
        else if(x < p->val){ //      
            q = p;
            p = p->lchild;    
        }
        else{   //      
            q = p;
            p = p->rchild;    
        }
    }
    if(p == NULL){   //    
        cout << "    " << x << endl;    
    }

    if(p->lchild == NULL && p->rchild == NULL){  //p      
        if(p == BT){  //p     
            BT = NULL;    
        }
        else if(q->lchild == p){   
            q->lchild = NULL;
        }        
        else{
            q->rchild = NULL;    
        }
        free(p);  //    p 
    }
    else if(p->lchild == NULL || p->rchild == NULL){ //p      
        if(p == BT){  //p     
            if(p->lchild == NULL){
                BT = p->rchild;    
            }    
            else{
                BT = p->lchild;    
            }
        }    
        else{
            if(q->lchild == p && p->lchild){ //p q     p     
                q->lchild = p->lchild;    // p       q      
            }    
            else if(q->lchild == p && p->rchild){
                q->lchild = p->rchild;    
            }
            else if(q->rchild == p && p->lchild){
                q->rchild = p->lchild;    
            }
            else{
                q->rchild = p->rchild;
            }
        }
        free(p);
    }
    else{ //p          
        pnode t = p;
        pnode s = p->lchild;  // p        
        while(s->rchild){  //  p   ， p           
            t = s;   
            s = s->rchild;    
        }
        p->val = s->val;   //   s    p 
        if(t == p){
            p->lchild = s->lchild;    
        }    
        else{
            t->rchild = s->lchild;    
        }
        free(s); 
    }
    return find;
}