[Data Structure] Binary Tree를 이용한 디렉토리 용량 계산

 이번에도 아주 단순한 코드를 소개한다. 이진트리를 활용해서 디렉토리의 용량을 계산해보자. 사실 말이 안되는게 하위폴더는 최대 2개다. 왜냐하면 우리는 이진트리를 공부해야 하니까.

 폴더의 용량을 계산하기 위해서는 하위 폴더의 모든 용량이 이미 계산되고 자신의 용량까지 더해줘야한다. 그래서 후위(post order) 순회를 사용한다. 후위 순회 코드랑 아주 유사하다. 다만 재귀적으로 폴더의 용량을 리턴한다는 점만 다르다. 원리는 똑같으니 더 이상의 설명은 생략한다.

#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct {
    element data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

int calc_direc_size(TreeNode *root){
    if (root->left == NULL && root->right == NULL)
        return root->data;
    int left = calc_direc_size((TreeNode*)root->left);
    int right = calc_direc_size((TreeNode*)root->right);
    return root->data + left + right;
}

int main(){
    TreeNode n5 = {500,NULL,NULL};
    TreeNode n4 = {200,NULL,NULL};
    TreeNode n3 = {100,&n4 ,&n5 };
    TreeNode n2 = {50 ,NULL,NULL};
    TreeNode n1 = {0  ,&n2 ,&n3 };
    
    printf("디렉토리의 크기 : %d\n",calc_direc_size(&n1));
    return 0;
}