[자료구조](13)[이진트리의 구현 2]

 

BST의 구현

기본 골조는 이진트리랑 비슷하지만 BST의 특성을 살려야 함

 

기본 골조 (일반적인 이진트리)

typedef struct Treenode {
    int data; //int형 데이터 담음
    struct Treenode* left; //node를 가리키는 포인터 선언
    struct Treenode* right;
} TreeNode;

TreeNode* makeTreeNode(int data){
    Node* newNode = (Node*)malloc(sizeof(TreeNode));
    newNode->data = data;
    newNode->left = NULL;  
    newNode->right = NULL; 
    return newNode;
}

 

insertBST

BST의 특성 (작은건 왼쪽, 큰건 오른쪽)을 만족하며 노드를 삽입해야 함.

TreeNode* insertBST(TreeNode* root, int data){
    if (root == NULL){
        return makeTreeNode(data);
    }
    if (data < root->data){
        root->left = insertBst(root->left, data);
    }
    else if (data > root->data){
        root->right = insertBST(root->right, data);
    }
    return root; //삽입한 트리의 루트 노드를 반환함
}

 

searchBST

이것도 저번의 find와 마찬가지로 재귀적으로 찾는다

TreeNode* searchBST(TreeNode* root, int target){
    if (root == NULL || root->data == target){
        return root;
    }
    else if (target < root->data){
        return searchBST(root->left, target);
    }
    else (target > root->data){
        return searchBST(root->right, target);
    }
}

 

deleteBST

BST에서 노드를 지우는 규칙에 따라 노드 삭제
어떤 서브트리의 루트 노드가 지워졌다면
    왼쪽 서브트리의 가장 큰 노드를 루트로 올리거나
    오른쪽 서브트리의 가장 작은 노드를 루트로 올리거나

TreeNode* deleteBST(TreeNode* root, int target){
    if (root == NULL){
        return root; //안 지우고 걍 반환
    }
    else if (target < root->data){
        root->left = deleteBST(root->left, target);
    }
    else if(target > root->data){
        root->right = deleteBST(root->right, target);
    }
    else{ //타겟을 찾음
        // 왼쪽 자식이 없음: 오른쪽 자식을 root로
        if (root->left == NULL) {
            TreeNode* tmp = root->right;
            free(root);
            return tmp;
        }
        // 오른쪽 자식이 없음: 왼쪽 자식을 root로
        else if (root->right == NULL) {
            TreeNode* tmp = root->left;
            free(root);
            return tmp;
        }
        // 양쪽 다 자식이 있음: 오른쪽에서 가장 작은 놈으로 대체
        TreeNode* tmp = root->right;
        while (tmp->left != NULL) {
            tmp = tmp->left;
        }
        root->data = tmp->data;
        root->right = deleteBST(root->right, tmp->data);
    }
    return root;
}