[자료구조] Program to find the nodes which are at the maximum distance in a Binary Tree

원문 링크

https://www.javatpoint.com/program-to-find-the-nodes-which-are-at-the-maximum-distance-in-a-binary-tree

Program to Find the Nodes Which are at the Maximum Distance in a Binary Tree - javatpoint

가장 거리가 먼 두 노드들을 찾는 알고리즘을 만드는 문제입니다.

위의 사진을 예로들면 Tree에서 (4,9), (5,9)를 찾는 것이 목표입니다.

 

핵심 : root를 기준으로 left, right subtree의 leafs들을 찾으면 된다.

 

알고리즘 구상(algorithm)

exception

        if root Is NULL

        if there is only one node in Tree

        also need to handle the case that one of the subtree is not exist.

1. find a max depth for each right and left subtree of root

2. get the nodes that are in the max depth in each subtree of root

3. these are the nodes that are at the maximum distance in a BT

4. Maximum distance is sum of max depth of each subtree of root

 

specific algorithm

struct node *current

 

get leafs of left subtree

1. current = root->left

2. enqueue(current)

3. NodeInlevel = size of queue

4. current = dequeue() NodeInlevel--

5. if(current->left!=NULL) then enqueue(current->left)

6. if(current->right!=NULL) then enqueue(current->right)

7. repeat step 4~6 while nodeInlevel > 0

8. return the nodes of last level of each right and left subtree

 

and get leafs of right subtree (vice versa)

 

header code

#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* getleafs(struct node *temp) {
    int nodeInlevel = 0;
    int* subtree;
    subtree = (int*)malloc(sizeof(int) * 1);
    int subsize = 0;
    struct node * current = NULL;
 
    if (temp == NULL) {
        subtree[0] = root->data;
        return subtree;
    }
 
    current = temp;
    enqueue(current);
    while (size > 0) {
        nodeInlevel = size;
        subsize = 0;
        while (nodeInlevel > 0) {
            current = dequeue();
            if (current->left == NULL && current->right == NULL) {
                subtree = realloc(subtree, sizeof(int)*(subsize + 2));
                subtree[subsize] = current->data;
                subsize++;
            }
            else {
                if (current->left != NULL) {
                    enqueue(current->left);
                }
                if (current->right != NULL) {
                    enqueue(current->right);
                }
            }
            nodeInlevel--;
        }
    }
    return subtree;
}
 
void nodesAtMaxDistance(struct node* temp) {
    int *left;
    int *right;
 
    if (root == NULL) {
        printf("Tree is empty\n");
        return;
    }
    else if(root->left == NULL && root->right == NULL) {
        printf("Tree has only one node\n");
        return;
    }
    else {
        left = getleafs(root->left);
        right = getleafs(root->right);
 
        printf("Nodes which are at maximum distance :\n");
        for (int i = 0; left[i] > 0; i++) {
            for (int j = 0; right[j] > 0; j++) {
                printf("( %d, %d )\n", left[i], right[j]);
            }
        }
    }
    return;
}
 
 
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->right = createNode(6);
    
    nodesAtMaxDistance(root);
 
    return 0;
}

각 subtree의 leaf level의 모든 nodes에 접근하기 위해 queue 자료구조를 이용했다.

leaf nodes를 저장할 배열은 int pointer를 활용하여 동적할당했고, 데이터를 추가할 때마다 int data를 2칸 더 저장할 수 있게 memory reallocation을 하게 설계했다.

 

To approach every nodes on leaf level, I used Queue data structure.

Array that would store leaf nodes are allocated dynamically by using int pointer as you can see in the source code row 3~4.

As soon as data is sorted to the array, array get two more int spaces due to memory reallocation (code row 21).

 

 

원문 소스코드랑 비교해봤을 때 나의 코드가 더 심플한 것 같다. (complexity를 의미하는 것은 아님)

(원문코드 너무 길어서 첨부하지 않았음, 링크를 타고 들어가면 볼 수 있음)

연산 측면이나 시스템 체계 측면에서는 어떤 것이 더 나은지 판단이 어렵다. 고수분이 계시다면 피드백 부탁드립니다.

 

알게된점

함수안에서 특정 변수이름으로 배열을 선언하여 return한다고 했을 때, 이 함수를 두 번 이용하게 되면 배열이 참조형 자료형이기 때문에 두 번째 함수 call 이 되었을 때 데이터가 수정되면서 첫 번째 return된 값에도 영향을 주게 된다.

배열을 포인터로 동적할당하여 선언하게 되면 두번째 함수 call이 첫번째 함수 return 값에 영향을 주는 이 문제를 해결할 수 있다.

아마 동일한 이름으로 배열을 선언하게되면 저장되는 메모리주소가 fix되는 것 같다.

pointer로 동적할당하게되면 이미 allocated된 메모리를 제외한 곳에 메모리가 할당되는 것 같다. 그렇기에 두 작업이 겹치는 것을 방지할 수 있다.

 

궁금한 점이 있으면 댓글로 남겨주시면 친절히 답변드리겠습니다. ㅎㅎ 같은 공부하시는 분들의 코드리뷰나 피드백은 언제나 환영입니다. ㅎㅎ