후위순회를 이용한 디렉토리 용량 계산

왼쪽자식+오른쪽 자식+루트 순으로 탐색하는 후위순회를 이용해 트리구조처럼 되어있는 컴퓨터의 디렉토리 용량을 계산할 수 있습니다.

단, 이진트리임을 가정하므로 각 디렉토리안에 2개를 초과하는 디렉토리 존재X

루트 디렉토리의 왼쪽 서브 디렉토리의 총 디렉토리 용량과 오른쪽 서브 디렉토리의 총 디렉토리의 용량을 구하고

그 두개의 용량합에 루트디렉토리의 용량을 합하면 총 디렉토리의 용량이 계산됩니다.

후위순회를 약간 응용하여 쉽게 구현할 수 있습니다.

코드

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
 
typedef struct treeNode
{
    int data;
    struct treeNode* left, * right;
}treeNode;
 
int calc(treeNode* root)
{
    int left_size, right_size;
    if (root == NULL)return 0;
    else
    {
        left_size = calc(root->left);//후위
        right_size = calc(root->right);//후위
        return left_size + right_size + root->data;//계산한 용량값을 리턴한다.
    }
}
int main()
{
    treeNode n4 = { 500,NULL,NULL };
    treeNode n5 = { 200,NULL,NULL };
    treeNode n3 = { 100,&n4,&n5 };
    treeNode n2 = { 50,NULL,NULL };
    treeNode n1 = { 0,&n2,&n3 };
    printf("디렉토리의 총 용량은 %d입니다.\n", calc(&n1));
}

결과