BST 트리 구현

 

Binary Search Tree 구현을 해보았다. 

트리 만드는 부분 까지만 되어 있다.

지금은 root부터 insert로 트리를 생성하게 되어 있는데, 첨에는 다르게 해보다가 엄청 고생함.

최적화 된 형태는 아니기 때문에 향후에 업데이트 될 가능성은 크다.

인접리스트로만 구현하려고도 해봤는데, left, right가 [0], [1]로 되어야 해서 좀 어색하고,

특히 parent처리하려면 별도 배열을 쓰거나 node안에 w옆에 넣어야 하는데 좀 어색함

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
struct node { int parent, l, r; };
int root, c, n, u, v;
#define MAX_NODE (1000001)
 
void insert(vector<node>& tree, int n, int v) {
    if (v < n) {
        if (tree[n].l == 0) { tree[n].l = v, tree[v].parent = n; return; }
        insert(tree, tree[n].l, v);
    }
    else {
        if (tree[n].r == 0) { tree[n].r = v, tree[v].parent = n; return; }
        insert(tree, tree[n].r, v);
    }
}
int main()
{
    vector<node> tree(MAX_NODE);
    cin >> root;
    tree[root] = { -1,0,0 };
    while (cin >> n) {
        insert(tree, root, n);
    }
    return 0;
}
 

이걸로 post_order로 순회하는 것까지 구현한게 아래 코드이고, 이 문제에 대한 답안이기도 하다.

#include <bits/stdc++.h>
#include <unistd.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
struct node {int parent,l,r;};
int root,c,n,u,v;
vector<node> tree(1000001);
 
void post_order(int n){
    if(n==0) return;
    post_order(tree[n].l);
    post_order(tree[n].r);
    cout << n << '\n';
}
void insert(int n, int v){
    if(v<n){
        if(tree[n].l==0) {tree[n].l=v,tree[v].parent=n;return;}
        insert(tree[n].l,v);
    } else{
        if(tree[n].r==0) {tree[n].r=v,tree[v].parent=n;return;}
        insert(tree[n].r,v);
    }
 
}
int32_t main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "rt", stdin);
#endif
    cin >> root;
    tree[root] = {-1,0,0};
    while(cin >> n){
        insert(root, n);
    }
    post_order(root);
    int sdf = 1;
    return 0;
}