Binary Search Tree(BST) 바이러니 서치 트리

Binary Search Tree(BST)
바이러니 서치 트리


[-] Collapse

#include<stdio.h>
#include<iostream>
#include<cstring>
using namespace std;

class BST{
private:
    int cnt;
    struct node{
        int v;
        int idx;
        node* parent;
        node* l_child;
        node* r_child;
        node(){
            parent = l_child = r_child = NULL;
        }
    }node[1000];

public:
    BST(){
        cnt = 0;
    }
    bool insert(int v){
        if (cnt >= 1000) return false;
        else{
            node[cnt].idx = cnt;
            node[cnt].v = v;
            int here = 0; //root start
            int parent = 0;
            while (1){
                if (node[here].v <= v){
                    if (node[here].r_child == NULL){
                        node[cnt].parent = &node[here];
                        if (here != cnt)
                            node[here].r_child = &node[cnt];
                        break;
                    }
                    else{
                        parent = here;
                        here = node[here].r_child->idx;
                    }

                }
                else{
                    if (node[here].l_child == NULL){
                        node[cnt].parent = &node[here];
                        if (here != cnt)
                            node[here].l_child = &node[cnt];
                        break;
                    }
                    else{
                        parent = here;
                        here = node[here].l_child->idx;
                    }
                }
            }
            cnt++;
        }
    }
    bool find(int v){
        int here = 0;
        if (cnt == 0) return false;
        else{
            while (1){
                if (node[here].v == v){
                    return true;
                }
                else if(node[here].v < v){
                    if (node[here].r_child == NULL)
                        return false;
                    else
                        here = node[here].r_child->idx;
                }
                else if(node[here].v > v){
                    if (node[here].l_child == NULL)
                        return false;
                    else
                        here = node[here].l_child->idx;
                }
            }
        }
    }
    void prev(int here){
        printf("%d ", node[here].v); //visit
        if (node[here].l_child != NULL)
            prev(node[here].l_child->idx);
        if (node[here].r_child != NULL)
            prev(node[here].r_child->idx);
    }
    void in(int here){
        if (node[here].l_child != NULL)
            in(node[here].l_child->idx);
  &nnbsp;     printf("%d ", node[here].v); //visit
        if (node[here].r_child != NULL)
            in(node[here].r_child->idx);
    }
    void post(int here){
        if (node[here].l_child != NULL)
            post(node[here].l_child->idx);
        if (node[here].r_child != NULL)
            post(node[here].r_child->idx);
        printf("%d ", node[here].v); //visit
    }
};


int main(){
    freopen("input.txt", "r", stdin);
    BST my_bst;
    int n; scanf("%d", &n);
    for (int i = 0; i < n; i++){
        int val; scanf("%d", &val);
        my_bst.insert(val);
    }
    printf("pre order traversal\n");
    my_bst.prev(0);
    puts("");
    printf("in order traversal\n");
    my_bst.in(0);
    puts("");
    printf("post order traversal\n");
    my_bst.post(0);
    puts("");
    if (my_bst.find(0)) printf("Find!!\n");
    else printf("Can't Find!!\n");
    if (my_bst.find(10000)) printf("Find!!\n");
    else printf("Can't Find!!\n");
    return 0;
}