프로그래밍의 귀속

7665 단어
struct TreeNode;
typedef struct TreeNode *Postion;
typedef struct TreeNode *SearchTree;

///  

SearchTree MakeEmpty(SearchTree T);
Postion Find(ElementType X, SearchTree T);
Postion FindMin(SearchTree T);
Postion FindMax(SearchTree T);
SearchTree Insert(ElementType X, SearchTree T);
SearchTree Delete(ElementType X, SearchTree T);
ElementType Retrieve(Postion P);

struct TreeNode
{
    ElementType Element;
    SearchTree Left;
    SearchTree Right;
};

SearchTree MakeEmpty(SearchTree T) {
    if (T != NULL) {

        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }
    return NULL;
}

Postion Find(ElementType X, SearchTree T){
    if (T == NULL) return NULL;
    if (X < T->Element) return Find(X, T-> Left);
    else if (X > T->Element) return Find(X, T->Right);
    else return T;
}

Postion FindMin(SearchTree T){
    if (T == NULL) return NULL;
    else if (T->Left == NULL) return T;
    else return FindMin(T->Left);
}

Postion FindMax(SearchTree T){
    // if (T == NULL) return NULL;
    // else if (T->Right == NULL) return T;
    // else return FindMax(T->Right);
    if (T!= NULL){ //  
        while(T->Right != NULL) {
            T = T->Right;
        }
    }
    return T;
}

SearchTree Insert(ElementType X, SearchTree T){
    if(T == NULL){
        T = malloc(sizeof(struct TreeNode));
        if (T == NULL) FatalError("Out Of Space");
        else {
            T->Element = X;
            T->Left = T->Right = NULL;
        }
    } else if (X < T->Element) {
        T->Left = Insert(X, T->Left);

    } else if (X > T->Element) {
        T->Right = Insert(X, T->Right);
    }
    return T;
}


SearchTree Delete(ElementType X, SearchTree T){ //  
    Postion TmpCell;

    if (T == NULL) {
        Error("Element Not Found")
    } else if (X < T->Element){
        T->Left = Delete(X, T->Left);
    } else if(X > T->Element){
        T->Right = Delete(X, T->Right);
    } else if(T->Left && T->Right){ // Two Chil
        TmpCell = FindMin(T->Right);
        T->Element = TmpCell->Element;
        T->Right = Delete(T->Element, T->Right)
    } else { // one or zero chil
        TmpCell = T;
        if (T->Left == NULL) {
            T = T->Right;
        } else if(T->Right == NULL){
            T = T->Left;
        }
        free(TmpCell);
    }
}

이 두 갈래 찾기 트리의 코드를 저는 개인적으로 특히 좋아합니다. 두 갈래 트리에 귀속되는 것이 그렇게 아름답고 간단하다고 말할 수 밖에 없습니다. 비록 효율은 비귀속적인 것보다 낮지만 읽기 쉽기 때문에nice라고 말할 수 밖에 없습니다.
개인적으로 이 코드는 우리가 배울 만한 몇 가지 부분이 있다고 생각한다.
1. 엄밀하지만 if(T== NULL)를 보면 알 수 있다
2. 단일, 각 함수가 처리하는 것은 직접적이고 목적이 명확하다
3. 간단하면서도 간단하지 않다(귀속), 똑똑한 사람이 비교적 잘하고, 개인이 잘하지 못한다는 것을 나타낸다

좋은 웹페이지 즐겨찾기