데이터 구조 (제4 장)

트 리 중 하나 입 니 다. 이 진 트 리 (BST, Binary Search Tree) 이 진 트 리 는 이 진 트 리 라 고도 부 릅 니 다.비 어 있 을 때의 성질: 비 어 있 는 왼쪽 트 리 의 모든 키 값 은 루트 노드 의 키 값 보다 작 습 니 다.비 어 있 는 오른쪽 트 리 의 모든 키 값 이 루트 노드 의 키 값 보다 큽 니 다.왼쪽, 오른쪽 나 무 는 모두 두 갈래 로 나 무 를 수색 한다.이 진 에 게 나 무 를 찾 으 라 고 했 으 니 찾 아 보 자!두 갈래 검색 트 리 의 검색 과정: 뿌리 노드 부터 시작 하고 비어 있 으 면 NULL 로 돌아 갑 니 다.비어 있 지 않 으 면 키워드 X 를 비교 해 보 겠 습 니 다.뿌리 노드 의 키 값 보다 작 으 면 왼쪽 트 리 에서 재 귀적 으로 찾 습 니 다. 그렇지 않 으 면 오른쪽 트 리 입 니 다. 이것 은 성질 입 니 다. 같 으 면 이 노드 의 지침 을 되 돌려 줍 니 다.

Position Find(ElementType X,BinTree BST)
{
    if(!BST)//    
    {
        return NULL;
    }
    if(X>BST->data)//  ，        
    {
        return Find(X,BST->Right);
    }
    else if(X<BST->data)//  ，        
    {
        return Find(X,BST->Left);
    }
    else//  ，       
    {
        return BST;
    }
}

개선: 비 귀속 함수 의 집행 효율 이 높 기 때문에 우 리 는 귀속 을 순환 으로 대체 할 수 있다.

Position Find(ElementType X,BinTree BST)
{
    while(BST)
    {
        if(X>BST->data)//  ，        
        {
            BST=BST->Right;
        }
        else if(X<BST->data)//  ，        
        {
           BST=BST->Left;
        }
        else//  ，       
        {
            return BST;
        }
    }
    return NULL;//    
}

최대 원소 와 최소 원 소 를 찾 습 니 다. 성질 때문에 우 리 는 최대 원소 가 반드시 오른쪽 끝 에 있다 는 것 을 쉽게 알 수 있 습 니 다.최소 원 소 는 반드시 맨 왼쪽 에 있 을 것 이다.

Position FindMin(BinTree BST)
{
    if(!BST)//  ，  NULL
    {
        return NULL;
    }
    else if(!BST->Left)//       
    {
        return BST;
    }
    else
    {
        return FindMin(BST->Left);//        
    }
}
Position FindMax(BinTree BST)
{
    if(!BST)//  ，  NULL
    {
        return NULL;
    }
    else if(!BST->Right)//       
    {
        return BST;
    }
    else
    {
        return FindMin(BST->Right);//        
    }
}

이 진 트 리 의 삽입 은 사실 Find 와 비슷 합 니 다. 왜냐하면 우 리 는 먼저 찾 아야 삽입 할 수 있 기 때 문 입 니 다. 그러나 우 리 는 주의해 야 합 니 다. 만약 에 잎 결점 이 라면 우 리 는 주동 적 으로 공간 을 신청 한 다음 에 그 뿌리 결점 과 비교 해서 왼쪽 인지 오른쪽 인지 봐 야 합 니 다.

BinTree Insert(ElementType X,BinTree BST)
{
    if(!BST)//    
    {
        BST=(struct TreeNode *)malloc(sizeof(struct TreeNode));
        BST->data=X;
        BST->Left=BST->Right=NULL;
    }
    else
    {
        if(X<BST->data)
        {
            BST->Left=Insert(X,BST->Left);
        }
        else if(X>BST->data)
        {
            BST->Right=Insert(X,BST->Right);
        }
        else
            return BST;
    }
}

검색, 삽입 을 말 하면 삭제 라 고 해 야 죠. 이 진 트 리 의 삭 제 를 삭제 할 때 우 리 는 매우 조심해 야 합 니 다. 왜냐하면 우리 의 결점 은 세 가지 상태 가 있 기 때 문 입 니 다.엽 결점: 아이 가 없 으 면 우 리 는 잔인하게 삭제 하고 부모 결점 을 수정 하 는 지침 이 비어 있 습 니 다.한 아이의 결점 만 있다. 그의 아버지 결점 을 손자 결점 에 직접 가리 키 고 손 자 는 아들 이 된다.두 아이의 결점 이 있 습 니 다. 결점 을 삭제 하 는 대신 다른 결점 을 사용 합 니 다. 오른쪽 하위 트 리 의 최소 요 소 를 대체 하거나 왼쪽 하위 트 리 의 최대 요 소 를 대체 합 니 다.아이 가 많 으 면 귀찮아!그래서 저희 가 쓰 겠 습 니 다. 전에 쓴 함수!

BinTree Delete(ElementType X,BinTree BST)
{
    Position temp;
    if(!BST)//  
    {
        printf("       ");
    }
    else if(X>BST->data)
    {
        BST->Right=Delete(X,BST->Right);
    }
    else if(X<BST->data)
    {
        BST->Left=Delete(X,BST->Left);
    }
    else
    {
        if(BST->Left&&BST->Right)//     
        {
            temp=FindMin(BST->Right)；
            BST->data=temp->data;
            BST->Right=Delete(BSt->data,BST->Right);
        }
        else
        {
            temp=BST;
            if(!BST->Left)
            {
                BST=BST->Right;
            }
            else if(!BST->Right)
            {
                BST=BST->Left
            }
            free(temp);
        }
    }
    else 
    return BST;
}