[알고리즘] 이진트리 만들기

 프로그래머스 문제를 풀다보면, 간혹 이진트리를 만들어 풀어야하는 경우가 있다. 깊이우선 탐색, 너비우선 탐색, 힙 정렬 등이 있다.

(힙 같은 경우 배열로 할 수 있다.)

갑자기 이진트리를 만드려고 하니, 순간 머리가 멍해지는 느낌이 있어서, 아무래도 한번쯤 정리해야겠다는 생각을 하게 됐다.

 

struct Node{
    int value = 0;
    Node* left = nullptr;
    Node* right = nullptr;
    Node* parent = nullptr;    
};

 

 우선 노드는 위와 같다. 왼쪽, 오른쪽 그리고 부모를 가르키는 포인터를 두었다.(사실 부모를 가르키는 것은 안둬도 된다.)

 

 

void addNode(queue<Node*>& add_queue, int value)
{
    //큐에서 노드를 꺼낸다.(제거하지 않고 꺼낸다.)
    Node* node = add_queue.front();
    if(node->left == nullptr)
    {
        //왼쪽이 비었을 경우,
        node->left = new Node();
        node->left->value = value;
        node->left->parent = node;
        add_queue.push(node->left);
    }
    else
    {
        //오른쪽이 비었을 경우,
        node->right = new Node();
        node->right->value = value;
        node->right->parent = node;
        add_queue.push(node->right);
    }
    
    //왼쪽 오른쪽이 모두 가득 찬 경우, 큐에서 제거한다.
    if(node->left != nullptr && node->right != nullptr)
        add_queue.pop();
}

 알고리즘 문제에서, 완전 이진트리로 만드는 경우가 많은데, 그 경우 큐를 활용 해야 한다. 큐에 생성한 노드를 넣고, 새 노드를 추가 할 때,

큐에 추가한 순서대로, 자식 노드가 비었는지 확인 후 넣으면 된다. (너비우선 탐색할 때도, 큐를 이용하면 된다.)

 

//make bianry tree
queue<Node*> add_queue;    
Node* root = new Node();    
add_queue.push(root);

int i = 1;
int add_count = 0;
for(auto& num : numbers)
{
    add_count = pow(2,i++);
    for(int j = 0 ; j < add_count ; j++)
        addNode(add_queue, j%2 == 0 ? num : -num);
}

 

 위 코드는 프로그래머스 문제 해결 중, 트리를 만드는 과정의 코드이다. 루트 노드를 하나 만들고, 그 후, 노드들을 추가했다.

 

void search(Node* node)
{
    //노드 값 출력
    printf("%d", node->value);
    if(node->left == nullptr && node->right == nullptr)
    {
		//가장자리 노드에 왔을 때,
    }
    else        
    {
        //재귀적으로 왼쪽 탐색
        search(node->left, sum+node->value, target);
        
        //재귀적으로 오른쪽 탐색
        search(node->right, sum+node->value, target);
    }
}

 

 위 코드로 깊이 우선 탐색(DFS) 해, 값을 출력하도록 했다. 너비우선탐색(BFS)는 재귀적으로 동작하지 않는다. 큐를 이용해, 방문했던 노드를 넣고, 순서대로 동작시켜야 한다.