이진탐색트리(BST : binary search tree)는 다음과 같은 속성이 있는 이진트리 자료구조이다.

* 각 노드에는 값이 있다.

* 루트가 있는 이진트리이다.

* 노드의 왼쪽서브트리는 노드의 값보다 작은 값들로 이루어진다.

* 노드의 오른쪽서브트리는 노드의 값보다 큰 값들로 이루어진다.

* 트리의 모든 서브트리는 이진탐색트리이다.

트리에서 노드의 레벨(level)은 루트로부터의 거리 + 1이다. 따라서 루트의 레벨은 1이다.

아래는 이진탐색트리와 노드의 레벨을 설명한 그림이다.

[문제]

이진탐색트리를 생성하고 노드를 추가, 탐색, 삭제하려 한다.

추가, 탐색, 삭제를 위한 명령수는 최대 1만이다.

노드에 저장되는 수의 범위는 -1,000,000 ~ 1,000,000 이다.

사용자 프로그램(user.cpp)은 아래 api 함수를 완성 해야 한다.

사용자 프로그램은 헤더파일을 추가할 수 없다.

필요한 함수와 변수를 추가하여 작성할 수 있으며 제출시에 함께 제출한다.

/// === user.cpp ===
 
#ifndef NULL
#define NULL 0
#endif
const int SIZE = 100010;
struct Node{
    int data;
    Node *lch, *rch;
    Node*alloc(int nd){
        data = nd, lch = rch = NULL;
        return this;
    }
}buf[SIZE];
int bcnt;
 
struct Tree{
    Node*root;
    int nodeCnt;
}tree;
 
Tree* newTree(){
    bcnt = 0;
    tree = Tree();
    return &tree;
}
 
void delTree(Tree*tree){
    tree = NULL;
}
 
// 트리의 노드수를 반환한다.
int getTreeSize(Tree*tree){
    return 0;
}
 
// 트리에 data가 있다면 1을 없다면 0을 반환한다.
int search(int data){
    return 0;
}
 
// 트리에 data가 존재한다면 아무일도 하지 않는다.
// 그렇지 않은경우 트리에 data를 추가한다.
void insert(int data){
 
}
 
// data를 찾을 수 없다면 아무일도 하지 않는다.
// 트리에서 data를 찾아 삭제한다.
// [노드 now를 삭제하는  프로세스]
// 1. child 노드가 없다면 삭제한다.
// 2. child가 하나뿐이라면 now자리를 child가 대신한다.
// 3. child가 lch, rch 두 개라면 now->data보다 크고
//    now->data에 가장 가까운 노드(이를 target이라 하자)를 삭제하고
//    target->data가 now->data 자리를 채운다.
void erase(int data){
 
}
 
// tree를 전위순회한 결과를 arr에 담는다.
void preorder(Tree*tree, int*arr){
 
}
 
// tree를 중위순회한 결과를 arr에 담는다.
void inorder(Tree*tree, int*arr){
 
}
 
// tree를 후위순회한 결과를 arr에 담는다.
void postorder(Tree*tree, int*arr){
 
}
 
/// === main.cpp ===
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
 
typedef struct Node Node;
typedef struct Tree Tree;
 
extern Tree* newTree();
extern void delTree(Tree*);
 
extern int getTreeSize(Tree*);
extern void insert(int);
extern int search(int);
extern void erase(int);
extern void preorder(Tree*, int*);
extern void inorder(Tree*, int*);
extern void postorder(Tree*, int*);
 
typedef enum{
    INIT, INSERT, SEARCH, ERASE, PREORDER, INORDER, POSTORDER
}ORDER;
 
static int len, arr[10004] = {0};
static void output(){
    for(int i=0;i<len;++i) printf("%d ", arr[i]);
    puts("");
}
 
static void run(){
    Tree* tree = newTree();
    int N, cmd;
    int num, i;
 
    scanf("%d", &N);
    for(i=0;i<N;++i){
        scanf("%d", &cmd);
        switch(cmd){
        case INSERT:
            scanf("%d", &num);
            insert(num);
            break;
        case SEARCH:
            scanf("%d", &num);
            printf("%d\n", search(num));
            break;
        case ERASE:
            scanf("%d", &num);
            erase(num);
            break;
        case PREORDER:
            len = getTreeSize(tree);
            preorder(tree, arr);
            output();
            break;
        case INORDER:
            len = getTreeSize(tree);
            inorder(tree, arr);
            output();
            break;
        case POSTORDER:
            len = getTreeSize(tree);
            postorder(tree, arr);
            output();
            break;
        }
    }
    delTree(tree);
}
int main(){
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
 
    setbuf(stdout, NULL);
    run();
    return 0;
}

#4320 upload 1430 done 493 how_to_reg 417 component_exchange Interactive

이진탐색트리(binary search tree) 2 timer 3s memory 256MB

#4320
Interactive

이진탐색트리(binary search tree) 2 3s 256MB