[자료구조] Print a Binary Tree in Vertical Order

원문 주소 : https://www.geeksforgeeks.org/print-binary-tree-vertical-order-set-2/

Print a Binary Tree in Vertical Order | Set 2 (Map based Method) - GeeksforGeeks

이진트리를 아래와 같이 수직 순서로 출력하는 알고리즘을 짜는 문제이다.

 

문제를 처음 보고 도출해낸 아이디어는 아래와 같다.

---

1. 트리를 root부터 pre-order traversal을 통해 node 하나하나씩 탐색한다.
2. 수직순서를 인덱스화 한다. 즉 위 그림을 참고하면 A=0, B=1 , C=2,,,~
3. root로 부터 좌측 node 최대 거리를 구한 후 이 정수값을 root의 인덱스로 한다.
4. 각각의 노드를 해당 인덱스의 배열에 저장한다.
5. 하나의 수직 레벨에 여러개의 노드가 존재할 경우 이를 Linked List로 연결한다.

---

위의 아이디어로 코드를 짜고 Test set을 돌려보니 주어진 그림과 동일한 결과가 나왔다.(성공????)

다른 사람들의 의견이 궁금해서 해당 사이트의 댓글들을 읽어봤다.

한 유저가 해당 게시물의 솔루션에 오류가 있다는 점을 지적하는 댓글을 보았고 이 문제는 나의 코드에서도 똑같이 발견할 수 있었다.

 

pre-order traversal로 트리를 탐색하고 노드를 배열에 저장하기때문에 left-subtree의 child가 right-subtree아래로 뻗어나가는 경우 출력순서가 뒤바뀌게 되는 문제가 발생한다. (좌측 sub-tree의 값을 배열에 먼저 저장하기 때문)

즉 오른쪽 테스트셋에서 horizontal level 1 = 2, level 2 = 5, level 3 =3,6 인데 pre-order 탐색을 하게 되면 3보다 6이 먼저 배열의 3인덱스에 저장되고 3은 이후에 6을 저장하고 있는 노드의 next pointer로 연결되기 때문에 출력순서가 뒤바뀌게 된다.

 

 

해결방법이 쉽게 떠오르지 않았다.

고민끝에 두가지 아이디어를 생각해냈다.

1. queue자료구조를 활용하여 level-order traversal을 이용해 같은 레벨에 있는 노드들을 하나씩 배열에 저장한다.

2. node에 depth 즉 깊이 값을 추가하여 저장하고 마지막에 linked list를 depth 기준 오름차순으로 정렬하고 출력한다.

 

두가지 모두 실험해보려고 코드를 짜던 중, 1번 방식의 단점이 많이 발견됐다.

queue와 linked list를 두개 다 사용하게 되면 배열을 두개 선언해야한다는 단점이 있다.

1.초기 node를 vertical level별로 저장할 배열과

2. queue 자료구조 배열

또한 같은 horizontal level에 있는 node들을 순서대로 탐색할 수 있다는 장점이 있지만, 이들의 각각 node에 vertical level을 부여하는 효율적인 방법이 떠오르지 않았다. 

 

따라서 깊이변수 depth을 추가하고 이후 sorting한 후 출력하는 방법을 선택했다.

완성된 코드는 아래와 같다.

 

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node* left;
    struct node* right;
};
 
struct node* createNode(int data) {
    struct node*  newNode = (struct node*)malloc(sizeof(struct node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
 
    return newNode;
}
 
struct node *root = NULL;
 
struct LL {
    int data;
    int depth;
    struct LL* next;
};
 
struct LL* createLL(int data, int depth) {
    struct LL* newLL = (struct LL*)malloc(sizeof(struct LL));
    newLL->data = data;
    newLL->depth = depth;
    newLL->next = NULL;
 
    return newLL;
}
 
struct LL *bucket[100];
 
int getmaxdisLeft(struct node* root) {
    int i = 0;
    while (root->left != NULL) {
        root = root->left;
        i++;
    }
    return i;
}
 
void insert(struct node* node, int hd, int depth) {
    struct LL* temp = createLL(node->data,depth);
    struct LL* current = NULL;
    if (bucket[hd] != NULL) {
        current = bucket[hd];
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = temp;
    }
    else {
        bucket[hd] = temp;
    }
    return;
}
 
void preorderStore(struct node* root, int middle, int depth) {
    insert(root, middle, depth);
    if (root->left != NULL) {
        int i = middle - 1;
        int j = depth + 1;
        preorderStore(root->left, i, j);
    }
    if (root->right != NULL) {
        int i = middle + 1;
        int j = depth + 1;
        preorderStore(root->right, i, j);
    }
}
void LLprint() {
    struct LL* current;
    int i = 0;
    while (bucket[i] != NULL) {
        current = bucket[i];
        printf("line %d => ", i);
        do {
            printf(" %d", current->data);
            current = current->next;
        } while (current != NULL);
        printf("\n");
        i++;
    }
}
 
void sort() {
    int i = 0;
    struct LL* temp_1 = NULL;
    struct LL* temp_2 = NULL;
    struct LL* temp_3 = NULL;
    while (bucket[i] != NULL) {
        if (bucket[i]->next != NULL) {
            if (bucket[i]->depth > bucket[i]->next->depth) {
                temp_1 = bucket[i];
                temp_2 = temp_1->next;
                bucket[i] = temp_2;
                temp_1->next = temp_2->next;
                temp_2->next = temp_1;
                while (temp_1->next != NULL) {
                    temp_3 = temp_1->next;
                    if (temp_1->depth > temp_3->depth) {
                        temp_1->next = temp_3->next;
                        temp_2->next = temp_3;
                        temp_3->next = temp_1;
                        temp_2 = temp_2->next;
                        temp_3 = temp_3->next;
                    }
                }
            }    
        }
        i++;
    }
    
    return;
}
 
int main() {
    root = createNode(10);
    root->right = createNode(3);
    root->left = createNode(2);
    root->left->right = createNode(5);
    root->left->right->right = createNode(6);
    
    int middle = 0;
    middle = getmaxdisLeft(root);
    printf("Vertical order traversal is : \n");
    preorderStore(root, middle, 0);
    sort();
    LLprint();
    
    return 0;
}

코드의 확장성을 위해 tree node struct와 linked list를 최대한 건드리지 않으려고 했다. 끝내 편의를 위해 LL(Linked List)  struct 에 int depth변수를 추가하고 이를 활용했다. 아마 c++에서 라이브러리를 활용해서 (key,value)개념? 등(python의 dictionary같은) 을 이용하면 더욱 쉽게 구현할 수 있을 것 같다.

---

별거 아닌 것 같아 보이는데 혼자 외부도움없이 문제와 씨름하다보니 엄청난 시간을 이 문제에 할애했다. 중간중간에 스트레스를 좀 받긴 했지만 끝내 완성했을 때 느꼈던 쾌감이 좋았다. 

현업에서 일을 할 때 도 많은 문제에 봉착할 것이므로 이를 혼자서 할 수 있는 데까지 해결하려고 하는 연습을 많이 해두는 것이 좋다고 개인적으로 생각한다. 열심히 꾸준히 해야겠다.