데이터 구조 와 알고리즘 의 두 갈래 검색 트 리

링크 와 달리 나 무 는 비 선형 데이터 구조 이다.나무 에서 가장 많이 사용 되 는 것 은 이 진 트 리 이다. 이 진 트 리 는 나무의 수량 을 제한 했다. 즉, 각 노드 의 나무 가 2 개 까지 많 고 이 두 개의 나 무 는 순서 가 있다.한편, 이 진 트 리 (이 진 트 리 찾기, 이 진 트 리 정렬) 는 뿌리 노드 의 키 워드 는 왼쪽 트 리 보다 크 고 오른쪽 트 리 보다 작 으 며 좌우 트 리 도 이 진 트 리 를 검색 하 는 것 을 말한다.즉, 중간 순서 로 두 갈래 검색 트 리 를 옮 겨 다 니 며 출력 은 어 릴 때 부터 큰 순서 로 정렬 된 것 이다.
일반적인 이 진 트 리 외 에 도 변형 에 관 한 것 이 많다.
이 진 밸 런 스 검색 트 리, 즉 이 진 밸 런 스 트 리 이자 검색 트 리 입 니 다. 밸 런 스 트 리 는 임의의 노드 의 왼쪽 트 리 높이 와 오른쪽 트 리 의 높이 차이 가 절대 1 보다 크 지 않 습 니 다.
붉 은 검 은 나무 도 특수 한 이 진 트 리 로 나 무 를 찾 는 특징 을 가지 고 있 을 뿐만 아니 라 모든 노드 에 붉 은 색 과 검 은 색 을 기록 하 는 요소 도 있다.
여기 서 우 리 는 주로 일반적인 이 진 트 리 를 토론 한다.
두 갈래 검색 트 리 는 사실 특수 한 나무 로 나무 에 적용 되 는 모든 알고리즘 은 두 갈래 검색 트 리 에 적용 된다.물론 그림 이기 도 하고 그림 에 적용 되 는 모든 알고리즘 도 이 진 검색 트 리 에 적용 된다.그림 의 깊이 우선 검색 (DFS) 은 트 리 의 앞 순 서 를 옮 겨 다 니 는 것 이 고, 넓이 우선 검색 (BFS) 은 트 리 의 층 차 를 옮 겨 다 니 는 것 입 니 다.물론 그림 에는 나무 에 도 적용 되 는 다른 알고리즘 이 많다.
1. 이 진 트 리 의 데이터 구조

typedef struct binSrcTreeNode{
    int element;
    struct binSrcTreeNode *pLeft;
    struct binSrcTreeNode *pRight;
}BSTNode;

2. 동적 으로 이 진 트 리 의 결산 점 을 분배 합 니 다.

BSTNode* allocNode(int element){
    BATNode *pNode = (BSTNode*)malloc(sizeof(BSTNode));
    if(NULL != pNode){
        pNode->element = element;
        pNode->pLeft = NULL;
        pNode->pRight = NULL;
    }
    return pNode;
}

3. 이 진 트 리 찾기
이 진 트 리 는 정렬 된 이 진 트 리 이기 때문에 2 분 검색 을 통 해 검색 할 수 있 습 니 다.먼저 뿌리 노드 와 같은 지 여 부 를 판단 하고 뿌리 노드 보다 큰 키 워드 를 사용 하면 오른쪽 트 리 를 검색 하고 뿌리 노드 보다 작은 키 워드 를 검색 하여 왼쪽 트 리 를 검색 합 니 다.

bool searchInBSTree(const BSTNode *pRoot,int element,BSTNode **pNode){
    if(NULL == pRoot)
        return false;
    *pNode = pRoot;
    if(pRoot->element == element){
        return true;
    }
    else if(pRoot->element > element)
        return searchInBSTree(pRoot->pLeft,element,pNode);
    else
        return searchInBSTree(pRoot->pRight,element,pNode);
}

4. 두 갈래 검색 트 리 의 삽입
먼저 이 진 트 리 에 이 요소 가 존재 하 는 지 찾 습 니 다. false 로 돌아 가 는 것 이 존재 한다 면;존재 하지 않 으 면 이 노드 를 삽입 하고 뿌리 노드 보다 요 소 를 삽입 하면 오른쪽 트 리 를 삽입 합 니 다. 그렇지 않 으 면 왼쪽 트 리 에 삽입 합 니 다.

bool insertIntoBSTree(BSTNode **pRoot,int element){
    if(NULL == pRoot)
        return false;
    if(NULL == *pRoot){
        *pRoot = allocNode(element);
        return NULL==*pRoot?false:true;
    }
    BSTNode **pSrc = NULL;
    if(searchInBSTree(pRoot,element,pSrc))
        return false;
    BSTNode *pNode = allocNode(element);
    if(element < *pSrc->element)
        *pSrc->pLeft = pNode;
    else
        *pSrc->pRight = pNode;
    return true;
}

5. 두 갈래 검색 트 리 의 삭제
두 갈래 검색 트 리 의 삭 제 는 세 가지 상황 으로 나 뉜 다.
(1) 결점 을 잎 결점 으로 삭제 하고 이 결점 을 직접 삭제 한 다음 에 아버지 결점 의 지침 을 수정 합 니 다 (주의 점 은 뿌리 결점 과 뿌리 노드 가 아 닙 니 다).
(2) 결점 을 한 개의 결점 으로 삭제 합 니 다 (즉, 왼쪽 나무 나 오른쪽 나무 만 있 습 니 다).
(3) 결점 을 삭제 한 왼쪽 트 리 와 오른쪽 트 리 가 모두 비어 있 지 않다.

bool deleteFromBSTree(BSTNode **pRoot,int element){
    if(NULL == pRoot || NULL == *pRoot)
        return false;
    BSTNode **pSrc = NULL;
    BSTNode **pParent = NULL;
    if(searchInBSTree(*pRoot,element,pParent,pSrc)){
        if(NULL == *pSrc->pLeft && NULL == *pSrc->pRight){
            free(*pSrc);
            *pSrc = NULL;
            return true;
        }
        else if(NULL == *pSrc->pLeft){
            if(*pSrc == *pParent->pLeft)
                *pParent->pLeft = *pSrc->pRight;
            else if(*pSrc == *pParent->pRight)
                *pParent->pRight = *pSrc->pRight;
            free(*pSrc);
            return true;
        }
        else if(NULL == *pSrc->pRight){
            if(*pSrc == *pParent->pLeft)
                *pParent->pLeft = *pSrc->pLeft;
            else if(*pSrc == *pParent->pRight)
                *pParent->pRight = *pSrc->pLeft;
            free(*pSrc);
            return true;
        }
        else{
            BSTNode *pNode = *pSrc;
            BSTNode *pChild = *pSrc->pLeft;
            while(pChild->pRight){
                pNode = pChild;
                pChild = pChild->pRight;
            }
            if(pNode == *pSrc) pNode->pLeft = pChild->pLeft;
            else pNode->pRight = pChild->pLeft;
            
            if(*pSrc == *pParent->pLeft) *pParent->pLeft = pChild;
            else *pParent->pRight = pChild;
            
            pChild->pLeft = *pSrc->pLeft;
            pChild->pRight = *pSrc->pRight;
            
            return true;
        }
    }
    
    return false;
}

6. 두 갈래 검색 트 리 의 앞 순서, 뒤 순서 옮 겨 다 니 기

/* preOrder to traverse the binarySearchTree.*/
void preOrderBinarySearchTree(const BSTNode *pRoot){
    if(NULL == pRoot)
        return ;
    printf("%d ",pRoot->element);
    preOrderBinarySearchTree(pRoot->pLeft);
    preOrderBinarySearchTree(pRoot->pRight);
}

/* inOrder to traverse the binarySearchTree.*/
void inOrderBinarySearchTree(const BSTNode *pRoot){
    if(NULL == pRoot)
        return ;
    inOrderBinarySearchTree(pRoot->pLeft);
    printf("%d ",pRoot->element);
    inOrderBinarySearchTree(pRoot->pRight);
}

/* posOrder to traverse the binarySearchTree.*/
void posOrderBinarySearchTree(const BSTNode *pRoot){
    if(NULL == pRoot)
        return ;
    posOrderBinarySearchTree(pRoot->pLeft);
    posOrderBinarySearchTree(pRoot->pRight);
    printf("%d ",pRoot->element);
}

 
7. 결산 점 방출

void freeBinarySearchTree(BSTNode *pRoot){
    if(NULL == pRoot)
        return ;
    freeBinarySearchTree(pRoot->pLeft);
    freeBinarySearchTree(pRoot->pRight);
    free(pRoot);
}

 
전체 코드 참조: https://github.com/whc2uestc/DataStructure-Algorithm/tree/master/tree