<5639번> 이진 검색 트리

https://www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

#include<iostream>
//#include<cstdio>
using namespace std;

typedef struct node{
    int data;
    struct node* right;
    struct node* left;
}node;

node* preorder(node * root,int input){
    if(!root)
    {
        root = new node();
        root->data = input;
        root->left = root->right=NULL;
    }
    else if(root->data > input)
        root->left=preorder(root->left,input);
    else
        root->right=preorder(root->right,input); 
    return root;
}
void postorder(node *root)
{
    if(root)
    {
        postorder(root->left);
        postorder(root->right);
        cout<<root->data<<"\n";
    }
}
int main(){

    int input;
    node* root=NULL;
    while(cin>>input)
        root=preorder(root,input);
    postorder(root);
    return 0;
}

이진 검색 트리를 생성할 때는 전위 순회를, 출력할 때는 후위 순회를 하는 문제이다.

 

이 문제를 풀면서 했던 오류는 먼저 트리를 배열을 이용해서 만들고자 했던 것이다. 최대로 들어오는 input의 개수가 10000개라 배열로 해야겠다는 잘못된 생각을 했다.

 

이진 검색 트리의 경우 생성시에 최대 트리의 높이가 O(n) 일 수 있기 때문에 최악의 경우에 10000번째 들어오는 노드에 해당하는 인덱스가 2^9999 일 수 있다는 것이다. 이렇게 하면 무조건 터질 수밖에 없다.

 

따라서 노드를 구조체를 이용해서 만들어 트리를 구현하였다.

여기서 했던 실수는 함수 내부에서 new 연산을 통해서 새로운 메모리를 할당해 온 뒤 루트에 연결하지 않고 재귀적으로 함수를 실행 했던 것이었다.