[3일차][이진트리] 부모노드의 합 구하기

- 문제 설명

먼저 입력받은 수들을 입력된 순서대로 작은값이 부모에 오도록 정렬한 뒤

가장 마지막 노드의 부모들의 합 구하기

2

3                5

7            4        6

위와 같을 경우 마지막 노드 6의 부모들의 합은 5+2로 7이다.

- 입력

1 // 테스트 케이스

6 // 노드 갯수

7 2 5 3 4 6

- 출력

#1 7 // 테스트 케이스, 합

- 입력 예시

3
6
7 2 5 3 4 6
6
5 5 4 3 2 1
8
7 2 6 10 8 5 11 7

- 출력 예시

#1 7
#2 3
#3 16

- 코드

#include "stdio.h"

void makeBinaryHeapTree(int data); //트리에 값 넣기

int sumOfParents(int last); // 부모들의 합 구하기

int last; // 노드 수

int tree[10]; // 트리 순서대로 저장된 배열

int main(int argc, const char * argv[]) {

    int T;

    scanf("%d", &T);

    for(int tc = 1;tc <= T;tc++)

    {

        int N;

        scanf("%d",&N);

        last = 0;

        for(int i=0; i < N; i++)

        {

            int inputData;

            scanf("%d",&inputData);

             makeBinaryHeapTree(inputData);

        }

        int sum = sumOfParents(last);

        printf("#%d %d\n",tc,sum);

        

    }

    return 0;

}

void makeBinaryHeapTree(int data) // 넣은 노드를 순서에 맞게 정렬

{

    int child = ++last; // 새로 추가된걸 자식번호

    int perant = child/2; // 부모 번호

    tree[child] = data;

    while(child > 1 && tree[child] < tree[perant]) // 자식이 루트가 아니면, 부모가 존재하고 자식의 데이터가 더 작으면

    {

        // 값 바꾸기

        int swap = tree[child];

        tree[child] = tree[perant];

        tree[perant] = swap;

        

        // 자식과 부모 번호 바꾸기

        child = perant;

        perant = child/2;

    }

}

int sumOfParents(int last)

{

    int sum = 0;

    while (tree[last] != 0)

    {

        last /= 2; // 2진 트리기 때문에 나누기 2를하면 부모노드

        sum += tree[last]; // 부모노드 값을 더함

    }

    return sum;

}