C 언어 - 이 진 트 리 검색

성질: x 를 이 진 트 리 의 노드 로 설정 합 니 다. y 가 x 의 왼쪽 트 리 의 노드 라면 y. key < = x. key 가 있 습 니 다.Y 가 x 의 오른쪽 트 리 에 있 는 노드 라면 y. key > x. key 가 있 습 니 다.
이 진 트 리 의 노드 에서 이 진 트 리 를 삭제 하 는 노드 z 삭 제 는 크게 세 가지 상황 으로 나 눌 수 있다. 1. z 에 하위 노드 가 없 으 면 z 를 간단하게 삭제 하고 z 부모 노드 를 수정 하 며 z 를 부모 노드 라 고 부 르 는 아이 2. z 에 아이 노드 c 가 있 으 면 c 로 z 를 대체 할 수 있다.3. z 는 두 아이의 노드 가 있 으 면 z 의 후계 노드 를 찾 아야 한다.z 의 후계 노드 는 반드시 z 의 오른쪽 서브 트 리 에 위치 하고 오른쪽 서브 트 리 의 최소 키워드 노드 이다.

#include
#include

/******************************************************
 *                   
 ******************************************************/

/******************************************************
 * data structure and definition
 ******************************************************/

typedef int ElemType;

typedef struct TNode
{
    ElemType key;
    struct TNode *parent;
    struct TNode *left;
    struct TNode *right;
}TNode,*Tree;

typedef enum{
    OK = 0,
    ERROR = -1
}Status;

/******************************************************
 * function     : tree_destroy
 * description  :      T        
 * input        : Tree *T
 * output       : Tree *T
 * return value : Status(OK/ERROR)
 * author       : HanyoungXue
 * date         : 2018-04-22
 *******************************************************/

Status tree_destroy(Tree *T){
    if (*T){
        TNode* left = (*T)->left;
        TNode* right = (*T)->right;
        free(*T);
        *T = NULL;
        tree_destroy(&left);
        tree_destroy(&right);
        return OK;
    }
    return ERROR;
}

/******************************************************
 * function     : tree_search
 * description  :        key   
 * input        : Tree T,ElemType key
 * output       : N/A
 * return value : TNode* T
 * author       : HanyoungXue
 * date         : 2018-04-22
 ******************************************************/

TNode* tree_search(Tree T,ElemType key){
    if(T==NULL || key==T->key){
        return T; 
    }
    if(keykey){
        return tree_search(T->left,key);
    }else{
        return tree_search(T->right,key);
    }
}

/*******************************************************
 * function     : tree_in_order_traverse
 * description  :          T      
 * input        : Tree T
 * output       : N/A
 * return value : Status(OK/ERROR)
 * author       : HanyoungXue
 * date         : 2018-04-22
 *******************************************************/
Status tree_in_order_traverse(Tree T){
    if(T!=NULL){
        tree_in_order_traverse(T->left);
        printf("%d\t",T->key );
        tree_in_order_traverse(T->right);
        return OK;
    }
    return ERROR;
}

/************************************************************
 * function     : tree_min
 * description  :      T                  
 * input        : Tree T
 * output       : N/A
 * return value : TNode* T
 * author       : HanyoungXue
 * date         : 2018-04-22
 ************************************************************/


TNode* tree_min(Tree T){

    while(T->left){
        T = T->left;
    }
    return T;
}


/************************************************************
 * function     : tree_max
 * description  :      T                  
 * input        : Tree T
 * output       : N/A
 * return value : TNode* T
 * author       : HanyoungXue
 * date         : 2018-04-22
 ************************************************************/
TNode* tree_max(Tree T){
    while (T->right){
        T = T->right;
    }
    return T;
}

/************************************************************
 * function     : tree_successor
 * description  :     T     
 * input        : TNode* T
 * output       : N/A
 * return value : TNode* y
 * author       : HanyoungXue
 * date         : 2018-04-22
 ************************************************************/
TNode* tree_successor(TNode* T){
    if(T->right){
        return tree_min(T->right);
    }

    TNode* y = T->parent;
    while(y&&y->right == T){
        T = y->right;
        y = T->parent;
    }
    return y;
}

/************************************************************
 * function     : tree_insert
 * description  :       key   
 * input        : Tree *T,ElemType key
 * output       : N/A
 * return value : Status(OK/ERROR)
 * author       : HanyoungXue
 * date         : 2018-04-22
 ************************************************************/
Status tree_insert(Tree *T,ElemType key){
    TNode *z = (TNode *)malloc(sizeof(TNode));
    z->key = key;
    z->left = NULL;
    z->right = NULL;

    TNode *y = NULL;
    TNode *x = *T;

    while(x){
        y = x;
        if(z->key < x->key){
            x = x->left;
        }else{
            x = x->right;
        }
    }

    z->parent = y;

    if(!y){
        *T = z;
    }else if(z->key < y->key){
        y->left = z;
    }else{
        y->right = z;
    }

    return OK;
}

/***********************************************************
 * function     : tree_translate
 * description  :             
 * input        : Tree *T,TNode *u,TNode *v
 * output       : Tree *T
 * return value : N/A
 * author       : HanyoungXue
 * date         : 2018-04-22
 ***********************************************************/

void tree_translate(Tree *T,TNode *u,TNode *v){
    if(!(u->parent)){
        *T = v;
    }else if(u==u->parent->left){
        u->parent->left = v;
    }else{
        u->parent->right = v;
    }
    if(v){
        v->parent = u->parent;
    }
}

/*********************************************************
 * function     : tree_delete
 * description  :    T     z
 * input        : Tree *T,TNode *z
 * output       : Tree *T,TNode *z
 * return value : N/A
 * author       : HanyoungXue
 * date         : 2018-04-22
 *********************************************************/

void tree_delete(Tree *T,TNode *z){
    if(!(z->left)){
        tree_translate(T,z,z->right);
    }else if(!(z->right)){
        tree_translate(T,z,z->left);
    }else{
        TNode *y = tree_min(z->right);
        if(y->parent!=z){
            tree_translate(T,y,y->right);
            y->right = z->right;
            y->right->parent = y;
        }
        tree_translate(T,z,y);
        y->left = z->left;
        y->left->parent = y;
        tree_destroy(&z);
    }
}

int main(int argc, char const *argv[])
{
    Tree T;
    int n;
    scanf("%d",&n);

    for (int i = 0; i < n; ++i){
        ElemType key = rand()%100;
        tree_insert(&T,key);
    }

    tree_in_order_traverse(T);
    printf("
");

    // printf("%d
", tree_successor(tree_min(T))->key);

    tree_delete(&T,tree_min(T));

    tree_in_order_traverse(T);
    printf("
");

    tree_delete(&T,tree_search(T,78));

    tree_in_order_traverse(T);
    printf("
");
    // tree_destroy(&T);

    // tree_in_order_traverse(T);
    return 0;
}