[자료구조] ep7-1) 트리(Tree)

ㅇ트리(Tree) ADT: 계층적으로 저장된 데이터 원소들을 모델링 - 계층적 구조

맨 위의 원소를 제외하고, 각 트리 원소는 부모(parent) 원소와 0개 이상의 자식(children) 원소들을 가진다

(전제: 트리는 비어있지 않다 - 알고리즘 단순화)

루트(root) 노드: A

 

내부 노드(internal node): 적어도 한 개의 자식을 가진 노드(A, B, C, F)

외부 노드, 리프(external node, leaf): 자식이 없는 노드(E, I, J, K, G, H, D)

형제(siblings): 같은 부모를 가진 노드들(G, H)

조상(ancestor): 부모(parent), 조부모(grandparent), 증조부모(grand-grandparent) 등

자손(descendant): 자식(child), 손주(grandchild), 증손주(grand-grandchild) 등

부트리(subtree): 노드와 그 노드의 자손들로 구성된 트리

 

경로(path): 조상 또는 자손을 따라 이어진 노드 시퀀스 e.g. ABFI

경로 길이(path length): 경로 내 간선(edge)의 수

노드의 깊이(depth): 루트로부터 노드에 이르는 유일한 경로의 길이

노드의 높이(height): 노드로부터 외부노드에 이르는 가장 긴 경로의 길이

트리의 높이(height of a tree): 루트의 높이

 

"트리의 크기가 N 이라면, 전체 간선의 개수는 N - 1 이다"

 

※ css의 선택자와 자료구조 트리에서 정의하는 자손과 자식의 의미가 모두 동일하다)

자손(descendant): 특정 요소의 하위에 있는 모든 요소를 의미

자식(child): 특정 요소에 직접 연결된 바로 다음 레벨의 요소들을 의미

 

 

 

 

ㅇ순서 트리(Ordered Tree): 각 노드의 자식들에 대해 선형 순서가 정의되어 있는 트리

e.g. 구조적 문서

 

트리의 응용

- 직접 응용: 조직 구성도, 파일 시스템, 프로그래밍 환경(내부 노드: 프로그램 구조물 / 리프: 어휘, 상수, 심볼)

- 간접 응용: 알고리즘 구현, 자료구조 구현

 

 

 

 

 

!!중요!!

ㅇ이진 트리(binary tree): 순서 트리를 모델링 한 것

이진 트리는 최대 두 개의 자식을 가진다

 

 

전제 1: 적정 이진 트리로 구현

- 트리의 각 내부 노드가 두 개의 자식을 가짐(left, right)

- 좌우 자식 노드 가운데 하나가 비어 있는 경우라도 적정 이진 트리로 구현 가능

 

전제 2: 이진 트리는 비어있지 않다

 

이진 트리의 재귀적 정의 - 루트가 자식의 순서쌍을 가지며, 자식이 내부 노드인 경우 이진 트리이다

(자식이 내부 노드라는 것은, 그 자식 역시 이진 트리의 루트가 된다는 의미! 이 부분이 재귀적 정의의 핵심이다. 즉, 자식 노드도 다시 두 자식을 가질 수 있고, 그 자식도 마찬가지로 계속해서 이진 트리의 구조를 따르게 된다)

 

이진 트리의 응용: 수식 표현, 의사결정 과정, 검색

계산기가 바로 이진 트리의 응용이다

2 x (a - 1) / (3 + b)

 

수식을 표현하는 이진 트리이므로 수식 트리라고도 한다

리프가 피연산자가 된다

 

 

[이진 트리의 성질]

n: 노드 수

e: 외부 노드 수(리프 수)

i: 내부 노드 수

h: 트리의 높이

그림을 보며 성질을 이해하자

 

성질)

e = i + 1

n = i + e = 2e - 1

h <= i

h <= (n - 1) / 2

e <= 2^h

h >= log2(e)

h >= log2(n + 1)  - 1

 

 

 

이진 트리의 깊이(depth)와 높이(height) 의사코드

재귀적 성질을 이용

 

 

 

 

 

 

 

 

활용) 이진 트리 삽입과 탐색

[연결리스트를 이용한 이진트리]

• 이진 트리의 노드에 저장되는 정보
  - data : 노드에 저장되는 값 (아래 문제에서 폴더의 용량)
  - left : 왼쪽 자식 노드를 가리키는 링크, right : 오른쪽 자식 노드를 가리키는 링크

• 이진 트리를 이용한 폴더 구조 표현
  - 이진 트리는 최대 2개의 자식 노드를 가짐.
  - 컴퓨터의 폴더 구조가 이진 트리 형태로 구성되어 있다고 가정함.

 

각각의 노드는 폴더 이름과 용량을 나타내며, 아래 트리에서 폴더 F1에는 20MB가 저장되어 있음을 의미함.

이진 트리를 이용한 폴더 구조 표현

 

 

 

문제) 위 트리를 연결리스트를 이용해서 구현하고, 주어진 노드에 대해 자신과 왼쪽 자식, 오른쪽 자식의 용량을 순서대로 출력하시오.

※ 참고사항: 실습 및 테스트 용이성을 위해 본 문제에서는 고정된 트리를 사용하지만, 일반적으로 동적으로 삽입, 삭제 가능한 트리를 사용함.

※ 도움말:

• 루트노드 삽입 함수를 만들어 사용하며, data(폴더 용량), left(왼쪽 자식 링크), right(오른쪽
• 자식 링크)를 인수로 받음.
• 모든 노드는 아래 그림과 같이 자신의 위치를 가리키는 포인터변수를 만들어 사용함.

• 단말 노드부터 생성하고, 부모노드를 붙여가는 방식으로 트리를 구성함.
  - 예를 들어, F7과 F8을 생성하고, 이를 이용해 F6을 생성하여 F6, F7, F8로 구성된 트리를 생성.
  - 비슷한 방법으로 트리를 확장해 나감.

 

출력)

자식 및 노드 존재 여부에 따라 출력 내용이 달라짐.

- 한쪽 자식만 존재하는 경우, 자신과 해당 자식 노드의 용량 2개 값만 출력.

- 자식 노드가 없는 경우, 자신의 용량 1개 값만 출력.

- 존재하지 않는 노드 번호가 입력되는 경우 –1을 출력.

 

test case

 

 

 

(전체 코드)

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

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

NODE* newNode(int data, NODE* left, NODE* right);

int main() {
    int nodeNum;
    NODE* F7 = newNode(130, NULL, NULL);
    NODE* F8 = newNode(80, NULL, NULL);
    NODE* F6 = newNode(120, F7, F8);
    NODE* F3 = newNode(50, NULL, F6);
    NODE* F4 = newNode(70, NULL, NULL);
    NODE* F5 = newNode(90, NULL, NULL);
    NODE* F2 = newNode(30, F4, F5);
    NODE* F1 = newNode(20, F2, F3);

    scanf("%d", &nodeNum);
    if (nodeNum == 8) {
        printf("%d", F8->data);
    } else if (nodeNum == 7) {
        printf("%d", F7->data);
    } else if (nodeNum == 6) {
        printf("%d %d %d", F6->data, F6->left->data, F6->right->data);
    } else if (nodeNum == 3) {
        printf("%d %d", F3->data, F3->right->data);
    } else if (nodeNum == 5) {
        printf("%d", F5->data);
    } else if (nodeNum == 4) {
        printf("%d", F4->data);
    } else if (nodeNum == 2) {
        printf("%d %d %d", F2->data, F2->left->data, F2->right->data);
    } else if (nodeNum == 1) {
        printf("%d %d %d", F1->data, F1->left->data, F1->right->data);
    } else {
        printf("-1");
    }

    return 0;
}

NODE* newNode(int data, NODE* left, NODE* right) {
    NODE* newNode = (NODE*)malloc(1 * sizeof(NODE));
    newNode->data = data;
    newNode->left = left;
    newNode->right = right;
    return newNode;
}

 

 

 

 

 

 

 

 

 

참고 및 출처: 데이터 구조 원리와 응용(국형준교수님), C언어로 쉽게 풀어 쓴 자료구조(천인국)