[자료구조] 완전 이진트리 구현 (배열) - C

완전 이진트리

자식 노드가 왼쪽에서부터 채워져있는 형태의 트리

 

 

위 트리는 완전이진트리의 예시이다.

 

완전 이진트리는 배열으로 나타내기 편리하다.

아래와 같이 왼쪽 위에서부터 순서대로 한층씩 내려오며 배열의 인덱스에 채워넣는다고 하자.

 

두 가지 방법으로 배열을 채울 수 있다.

 

1. 인덱스 0부터 차례로 채워넣기

규칙성을 찾아보자.

왼쪽 자식 인덱스 :  2*(부모 인덱스)+1

오른쪽 자식 인덱스 : 2*(부모 인덱스)+2

 

 

실행 코드

#include<stdio.h>
#define MAX_NODE 16

void btree_array(int arr[], int idx){
    // 왼쪽 자식 출력
    int left_child = 2 * idx+1;
    if (left_child < MAX_NODE && arr[left_child] != 0) {
        printf("왼쪽 자식 : %d\n", arr[left_child]);
    } else {
        printf("왼쪽 자식 : 없음\n");
    }

    // 오른쪽 자식 출력
    int right_child = 2 * idx + 2;
    if (right_child < MAX_NODE && arr[right_child] != 0) {
        printf("오른쪽 자식 : %d\n", arr[right_child]);
    } else {
        printf("오른쪽 자식 : 없음\n");
    }
}

int main(void){
    int arr[MAX_NODE] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 55, 25, 65}; 
    btree_array(arr, 3);
    return 0;
}

 

위 코드는 인덱스가 3인 40의 왼쪽 자식과 오른쪽 자식을 출력하는 코드이다.

 

실행 결과

 

 

 

 

2. 인덱스 1부터 차례로 채워넣기(0번 인덱스는 비워두기)

 

규칙성을 찾아보자.

왼쪽 자식 인덱스 :  2*(부모 인덱스)

오른쪽 자식 인덱스 : 2*(부모 인덱스)+1

 

실행 코드

#include<stdio.h>
#define MAX_NODE 16

void btree_array(int arr[], int idx){
    // 왼쪽 자식 출력
    int left_child = 2 * idx;
    if (left_child < MAX_NODE && arr[left_child] != 0) {
        printf("왼쪽 자식 : %d\n", arr[left_child]);
    } else {
        printf("왼쪽 자식 : 없음\n");
    }

    // 오른쪽 자식 출력
    int right_child = 2 * idx + 1;
    if (right_child < MAX_NODE && arr[right_child] != 0) {
        printf("오른쪽 자식 : %d\n", arr[right_child]);
    } else {
        printf("오른쪽 자식 : 없음\n");
    }
}

int main(void){
    int arr[MAX_NODE] = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 55, 25, 65};  // 배열에 첫번째 값은 사용하지 않는다.
    btree_array(arr, 2);
    return 0;
}

 

 

실행 결과

 

 

 

 

계산이 비교적 쉬운 이유로 첫번째 인덱스 값을 0으로 하는 두번째 방법을 많이 사용한다.