두 갈래 검색 트 리 (BST) 에 대한 동작

오늘 은 이 진 트 리 의 삽입, 찾기, 삭제 작업 을 쓰 겠 습 니 다.먼저 노드 의 데이터 구 조 를 제시 합 니 다.

struct node
{
    int data;
    node*l;
    node* r;
};

첫 번 째 는 찾기 동작 입 니 다:

void search(node* root,int x)
{
    if(root==NULL)
    {
        printf("no");
        return;
    }
    if(root->data==x)
    {
        printf("yes");
        return;
    }
    if(x<root->data)
        search(root->l,x);
    else
        search(root->r,x);
}

두 번 째 삽입 동작:

void insert(node* &root,int x)
{
    if(root==NULL)
    {
        root=new node;
        root->data=x;
        return ;
    }
    if(root->data==x)
        return;
    if(x<root->data)
        insert(root->l,x);
    else
        insert(root->r,x);
}

세 번 째 는 삭제 작업 입 니 다. 여기 서 설명 하고 자 하 는 것 은 실제 삭 제 된 작업 은 많은 실현 방식 이 있 고 재 귀 와 비 재 귀 가 있 습 니 다. 여기 서 재 귀 를 사 용 했 습 니 다. 실현 이 간단 하고 실수 하기 쉬 우 며 시험장 과 경기 에서 쓰기 쉽 기 때 문 입 니 다.

node* findPre(node* root)
{
    while(root->r!=NULL)
        root=root->r;
    return root;
}
node*findPost(node* root)
{
    while(root->l!=NULL)
        root=root->l;
    return root;
}
bool deletee(node* root,int x)
{
    if(root==NULL)
        return false;
    if(root->data==x)
    {
        if(root->l==NULL&&root->r==NULL)
        {
            root=NULL;
            return true;
        }
        else
        {
            if(root->l!=NULL)
            {
                node* pre=findPre(root->l);
                root->data=pre->data;
                deletee(root->l,pre->data);
            }
            else
            {
                node* post=findPost(root->r);
                root->data=post->data;
                deletee(root->r,post->data);
            }
        }
    }
    else
    {
        if(x<root->data)
            deletee(root->l,x);
        else
            deletee(root->r,x);         
    }
}

기본적으로 이것 뿐 이지 만 데이터 로 테스트 한 적 이 없 지만 대체적인 사고방식 은 이렇다.