[자료구조] 이진 트리 특징과 순회 방식 분석, 구현 및 활용

이진트리

정의 : 공집합 또는 루트와 왼쪽/오른쪽 서브트리로 구성된 유한집합(서브트리는 이진트리)
모든 노드가 2개의 서브트리를 가지고 있는 트리
서브트리는 공집할 수 있음

특징

각 노드에는 최대 2개까지의 자식 노드가 존재
- 각 노드의 차수 ≤ 2 → 구현하기가 편리
서브트리 간 순서 존재 ( L → R )

성질

노드의 개수가 n개이면 간선의 개수는 n-1개
높이가 h인 이진트리인 경우
- 최소 h개의 노드
- 최대 2^h-1개의 노드
n개의 노드를 가지는 이진트리의 높이
- 최대 n
- 최소 log_2(n+1)(올림)

이진트리의 분류

포화 이진트리

트리의 각 레벨에 노드가 꽉 차있는 이진트리

완전 이진트리

높이가 h일 때, 레벨 1부터 h-1까지는 노드가 모두 채워져 있음
마지막 레벨 h는 왼쪽부터 오른쪽으로 노드가 순서대로 채워짐

이진트리 표현

배열 표현법

모든 이진트리를 포화 이진트리라고 가정
각 노드에 번호를 붙여서 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장
부모와 자식의 인덱스 관계
- 배열의 인덱스가 1로 시작할 때
  - 노드 i의 부모 노드 인덱스 = |i/2|
  - 노드 i의 왼쪽 자식 노드 인덱스 = 2*i
  - 노드 i의 오른쪽 자식 노드 인덱스 = 2*i+1
- 배열의 인덱스가 0으로 시작할 때
  - 노드 i의 부모 노드 인덱스 = |i-1/2|
  - 노드 i의 왼쪽 자식 노드 인덱스 = 2*i+1
  - 노드 i의 오른쪽 자식 노드 인덱스 = 2*i+2
링크 표현법
- 포인터를 이용하여 부모노드가 자식노드를 가리키게 하는 방법
- 왼쪽 완전 이진트리를 링크 표현법으로 나타내면 오른쪽 처럼 된다.
- 노드의 구조
  - 왼쪽 자식노드 + data + 오른쪽 자식 노드
  - 트리 노드의 구조체 자료형

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

이진트리의 순회

순회 : 트리의 노드들을 체계적으로 방문
기본적으로 3가지 순회방법이 존재
- 전위 순회 : 자손노드보다 루트노드를 먼저 방문(V → L → R)
- 중위 순회 : 왼쪽 자손, 루트, 오른쪽 자손 순으로 방문( L → V → R)
- 후위 순회 : 루트노드보다 자손을 먼저 방문한다.( L → R → V)
- 왼쪽 서브트리 L, 오른쪽 서브트리 R, 루트 V

전위순회

루트를 먼저 방문하는 순회방법

preorder(TreeNode* root){
  if(root){
            printf("%d", root -> data); // 루트 노드 방문 출력
            preorder(root -> left); // 왼쪽 노드 방문
          preorder(root -> right); // 오른쪽 노드 방문
  }
}

중위순회

왼쪽서브트리 → 루트 → 오른쪽 서브 트리 순으로 방문

inorder(TreeNode* root){
  if(root){
            preorder(root -> left); // 왼쪽 노드 방문
            printf("%d", root -> data); // 루트 노드 방문 출력
          preorder(root -> right); // 오른쪽 노드 방문
  }
}

후위순회

왼쪽서브트리 → 오른쪽 서브트리 → 루트 순으로 방문

postorder(TreeNode* root){
  if(root){
            preorder(root -> left); // 왼쪽 노드 방문
            preorder(root -> right); // 오른쪽 노드 방문
            printf("%d", root -> data); // 루트 노드 방문 출력
  }
}

반복적 순회

앞선 재귀적인 순회 방식 말고 스택을 사용한 반복적 방법으로 순회 구현

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

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

// 스택 기능 함수
#define SIZE 100
int top = -1;
TreeNode *stack[SIZE];

void push(TreeNode* p){
    if(top < SIZE-1) stack[++top] = p;
}
TreeNode* pop(){
    TreeNode *p = NULL;
    if(top>= 0) p = stack[top--];
    return p;
}

// 전위 순회
void preorder_iter(TreeNode* root){

    while(1){
        for(;root;root = root -> left) 
        {
            push(root);
            printf("%d -> ",root->data);
        }
        root = pop();
        if(!root) break;
        root = root -> right;
    }
}

// 중위 순회
void inorder_iter(TreeNode* root){
    while(1){
        for(;root;root = root -> left) push(root);
        root = pop();
        if(!root) break;
        printf("%d -> ",root->data);
        root = root -> right;
    }
}

//후위 순회
void postorder_iter(TreeNode* root){
    while(1){
        do{
                        //이미 방문한 노드의 데이터 값을 NULL로 만듦
                        //스택에 맨 위의 노드를 꺼내서 연결된 왼쪽 노드를 없을때까지 스택에 넣음
            if(root -> data != NULL && root != NULL){
                push(root);
                root = root -> left;
            }
            else break;
        }while(root != NULL);

        root = pop();
        if(!root) break;

                // 연결된 오른쪽 노드가 있을 경우
        if(root -> right != NULL){
                        // 연결된 오른쪽 노드를 이미 방문했을 경우
            if(root -> right -> data == NULL){
                printf("%d -> ",root -> data);
                root -> data = NULL;
            }else{
                push(root);
                root = root -> right;
            }
        }
        else{
                        //연결된 노드가 왼쪽밖에 없는 경우
            printf("%d -> ", root -> data);
            root -> data = NULL;
        }
    }
}
TreeNode n1 = {1,NULL,NULL};
TreeNode n2 = {4,&n1,NULL};
TreeNode n3 = {16,NULL,NULL};
TreeNode n4 = {25,NULL,NULL};
TreeNode n5 = {20,&n3,&n4};
TreeNode n6 = {15,&n2,&n5};
TreeNode *root = &n6;

int main(void){

    printf("전위 순회 = ");
    preorder_iter(root);
    printf("\n");

    printf("중위 순회 = ");
    inorder_iter(root);
    printf("\n");

    printf("후위 순회 = ");
    postorder_iter(root);
    printf("\n");
    return 0;
}

<출력>

전위 순회 = 15 -> 4 -> 1 -> 20 -> 16 -> 25 -> 
중위 순회 = 1 -> 4 -> 15 -> 16 -> 20 -> 25 -> 
후위 순회 = 1 -> 4 -> 16 -> 25 -> 20 -> 15 ->

레벨 순회

노드를 레벨 순으로 검사하는 순회 방법 → 큐를 사용해 구현
- 아래와 같은 순서로 진행됨

/* ----- 큐 구현 함수 ---- */

void level_order(TreeNode *ptr){
    QueueType q;
    init_queue(&q);
    if(ptr == NULL) return;

    enqueue(&q,ptr);
    while(!is_empty(&q)){
        ptr = dequeue(&q);
        printf(" [%d] ", ptr -> data);
        if(ptr -> left) enqueue(&q,ptr -> left);
        if(ptr -> right) enqueue(&q,ptr -> right);
    }
}

TreeNode n1 = {1,NULL,NULL};
TreeNode n2 = {4,&n1,NULL};
TreeNode n3 = {16,NULL,NULL};
TreeNode n4 = {25,NULL,NULL};
TreeNode n5 = {20,&n3,&n4};
TreeNode n6 = {15,&n2,&n5};
TreeNode* root = &n6;

int main(){
    printf("레벨 순회 = ");
    level_order(root);
}

<출력>

레벨 순회 =  [15]  [4]  [20]  [1]  [16]  [25]

후위 순회 활용 - 수식트리계산

자식 노드 먼저 처리 후 부모 노드 처리

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

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

TreeNode n1 = {1,NULL,NULL};
TreeNode n2 = {4,NULL,NULL};
TreeNode n3 = {'*',&n1,&n2};
TreeNode n4 = {16,NULL,NULL};
TreeNode n5 = {25,NULL,NULL};
TreeNode n6 = {'+',&n4,&n5};
TreeNode n7 = {'+',&n3,&n6};
TreeNode *test = &n7;

int evaluate(TreeNode *root){
    if(root == NULL) return 0;
    if(root -> left == NULL && root -> right == NULL) return root -> data;

    int op1 = evaluate(root -> left);
    int op2 = evaluate(root -> right);
    printf("%d %c %d을 계산합니다.\n",op1,root->data,op2);
    switch(root->data){
        case '+':
        return op1 + op2;
        case '-':
        return op1 - op2;
        case '*':
        return op1 * op2;
        case '/':
        return op1 /op2;
    }
    return 0;
}
int main(){
    printf("수식의 값 = %d",evaluate(test));
}

<출력>

1 * 4을 계산합니다.
16 + 25을 계산합니다.
4 + 41을 계산합니다.
수식의 값 = 45

후위 순회 활용 - 폴더 용량 계산

/* --- TreeNode 구조체 ---- */

int calc_dir_size(TreeNode* root){
    if(root == NULL) return 0;
    int left_size = calc_dir_size(root->left);
    int right_size = calc_dir_size(root->right);
    return (root -> data + left_size + right_size);
}

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

<출력>

디렉토리 크기 =850

이진트리 연산

노드 개수 계산
- 각 서브트리에 대해 순환 호출 → 반환되는 값에 +1
높이
- 서브트리에 대해 순환호출 → 반환값 중 최댓값을 구하여 반환
단말노드 개수 계산
- 트리 노드 전체 순환 → 어떤 노드의 왼쪽 자식과 오른쪽 자식이 동시에 0이면 1 반환
  → 그렇지 않으면 비단말노드이므로 각각의 서브트리에 대해 순환호출 → 반환값을 서로 더함

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

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

TreeNode n1 = {1,NULL,NULL};
TreeNode n2 = {4,&n1,NULL};
TreeNode n3 = {16,NULL,NULL};
TreeNode n4 = {25,NULL,NULL};
TreeNode n5 = {20,&n3,&n4};
TreeNode n6 = {15,&n2,&n5};
TreeNode* root = &n6;

// 노드 개수 세기 함수
int get_node_count(TreeNode *node){
    int count = 0;
    if(node != NULL){
        count = 1+ get_node_count(node -> left) + get_node_count(node -> right);
    }
    return count;
}

// 단말 노드 개수 세기 함수
int get_leaf_count(TreeNode *node){
    int count = 0;
    if(node != NULL){
        if(node -> left == NULL && node -> right == NULL) return 1;
        else count = get_leaf_count(node -> left) + get_leaf_count(node -> right);
    }
    return count;
}

// 노드 높이 측정
int get_height(TreeNode *node){
    int height = 0;
    if(node != NULL){
        int lHeight = get_height(node -> left);
        int rHeight = get_height(node -> right);
        height = (lHeight >= rHeight)? 1+lHeight : 1+rHeight;
    }
    return height;
}

int main() {
    printf("노드 개수 : %d\n", get_node_count(root));
    printf("단말노드 개수 : %d\n", get_leaf_count(root));
    printf("높이 : %d\n", get_height(root));
}

<출력>

노드 개수 : 6
단말노드 개수 : 3
높이 : 3

저작자표시 변경금지

Today :

이진트리

특징

성질

이진트리의 분류

이진트리 표현

이진트리의 순회

전위순회

중위순회

후위순회

반복적 순회

레벨 순회

후위 순회 활용 - 수식트리계산

후위 순회 활용 - 폴더 용량 계산

이진트리 연산

티스토리툴바

이진트리

특징

성질

이진트리의 분류

이진트리 표현

이진트리의 순회

전위순회

중위순회

후위순회

반복적 순회

레벨 순회

후위 순회 활용 - 수식트리계산

후위 순회 활용 - 폴더 용량 계산

이진트리 연산

검색 태그

티스토리툴바