[자료구조] Program to find maximum width of a binary tree

원문 링크 : https://www.javatpoint.com/program-to-find-maximum-width-of-a-binary-tree

Program to Find Maximum Width of a Binary Tree - javatpoint

 

여기서 width란 한 level의 node의 수를 의미한다. 따라서 maximum width라 함은, 한 level에 있는 node의 수 중 가장 많은 수를 의미한다.

 

같은 level에 있는 node들에 접근하기 위해서는 queue를 이용하는 것이 합리적이다.

tree의 node를 담을 수 있는 queue를 선언하고 이를 이용한다.

단순히 pointer만을 이용해서 같은 level에 접근하려고 하면 구조적으로 복잡하기 때문이다.

상상해보라 (4)node에 접근한 다음 (5),(6),(7)node에 접근하는 알고리즘은 단순하게 pointer를 이용하여 어떻게 짤 것인가?

 

나는 아래와 같이 알고리즘을 짰다.

변수 선언 int width, int t_width, int nodeInlevel

1. queue에 root를 enqueue한다.

nodeInlevel = size;

t_width = 0;

2. queue를 dequeue한다.

nodeInleve--;

t_width+;

3. dequeue된 node의 child를 enqueue한다.

4. 2~3step을 nodeInlevel이 0이 될 때까지 진행한다.

(이전 레벨의 node를 다 털어낼 때까지 진행한다.)

 

#include <stdio.h>
#include <stdlib.h>
 
 
struct node {
    int data;
    struct node *left;
    struct node *right;
};
 
struct node *root = NULL;
struct node *queue[100];
int front = -1;
int rear = 0;
int size = 0;
 
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;
}
 
void enqueue(struct node *temp) {
    queue[rear++] = temp;
    size++;
}
 
struct node *dequeue() {
    size--;
    return queue[++front];
}
 
int maxWidth(struct node* node) {
    int width = 0;
    int t_width = 0;
    int nodeInlevel = 0;
 
    if (root == NULL) {
        printf("The tree is empty");
        return;
    }
    
    enqueue(node);
    while (size > 0) {
        nodeInlevel = size;
        t_width = 0;
        while (nodeInlevel > 0) {
            struct node *current = dequeue();
            t_width++;
            nodeInlevel--;
            if (current->left != NULL) {
                enqueue(current->left);
            }
            if (current->right != NULL) {
                enqueue(current->right);
            }
        }
        if (t_width > width) {
            width = t_width;
        }
    }
    return width;
}
 
int main() {
    root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    root->left->left->left = createNode(8);
 
    printf("Maximum width of the binary tree : %d", maxWidth(root));
 
 
 
    return 0;
}

이해를 돕기 위해 queue가 이용되는 과정을 벤다이어그램으로 표현해보았다.

tree의 node가 dequeue되고 enqueue되는 과정을 표현했다.

queue의 size와 nodeInlevel변수를 이용해서 node의 level을 switch한다.

while문 밖에서 nodeInlevel을 size로 초기화하고, while문 안에서 dequeue를 하고 nodeInlevel을 1++, t_width를 1--한다.

그리고 dequeue된 node의 child를 enqueue한다.

이를 nodeInlevel이 0이 될 때까지 즉 한 level의 node들이 자신들의 child를 모두 enqueue할 때까지 진행한다.

이후 t_width와 width를 비교하고 큰 값을 width에 저장한다.

 

원문의 코드와는 딱 한가지 다른 점이 있다. 

int findMaximumWidth() {  
    int maxWidth = 0;  
    int nodesInLevel = 0;  
  
    if(root == NULL) {  
        printf("Tree is empty\n");  
        return 0;  
    }  
    else {  
        enqueue(root);  
          
        while(size != 0) {  
            nodesInLevel = size;  
              
            maxWidth = (maxWidth < nodesInLevel) ? nodesInLevel : maxWidth;  
   
            while(nodesInLevel > 0) {  
                      
                struct node *current = dequeue();  
                if(current->left != NULL){  
                    enqueue(current->left);      
                }  
                  
                if(current->right != NULL) {  
                    enqueue(current->right);      
                }  
                nodesInLevel--;  
            }  
        }  
    return maxWidth;  
    }  
}

int t_width를 따로 선언하지 않고 nodeInlevel을 바로 width와 비교한다.

한 level의 nodes가 queue에 모두 담겨있을 때 size로 초기화된 nodeInlevel과 width를 비교한다.

 

원문 코드와 비교하면 내 코드는 불필요한 작업을 하는 셈이다. nodes가 이미 모두 담겨져있을 때 size 값으로 구할 수 있는 level에 있는 node의 수를 굳이 dequeue한 번 할 때 1씩 증가시켜서 얻는 셈이 된 것이기 때문이다.

이는 메모리 사용측면이나 불필요한 연산측면이나 열등하다.

조금 더 생각해서 효율적인 코드를 짜자.

 

이번 알고리즘 문제에서의 핵심은 tree의 같은 level의 node에 접근하는 데에 queue 자료구조를 사용한 점이다. 문제에서 주어지는 상황에 따라서 어떤 자료구조를 사용할 것인지 판단하는 능력을 키우는 것이 중요한 것 같다. 기억하자.