[C & Java] 트리 Tree 1 - 트리? / 이진트리? / 트리 표현법

Algorithm

[C & Java] 트리 Tree 1 - 트리? / 이진트리? / 트리 표현법

건복치 2020. 11. 3. 06:21

1. 트리(Tree)의 개념

계층적인 자료를 표현하는데 적합한 자료구조
한 개 이상의 노드로 이루어진 유합 집합
A~J를 노드(node)
이들 중 하나의 하나의 노드를 루트(root) 노드라 하고 나머지 노드들을 서브 트리(sub tree)라 한다.
계층적 구조에서 가장 높은 곳에 있는 노드 A가 루트가 됨
루트와 서브트리는 간선(edge)으로 연결됨

ex) {A, B, C, D, E, F, G, H, I, J} 중에서 루트 노드는 A이고

나머지 {B, E, F, G}, {C, H}, {D, I, J}의 3개의 노드 집합들은 A의 서브 트리라 한다.

다시 서브 트리 {B, E, F, G}의 루트는 B가 되고, 나머지 {E}, {F}, {G} 노드들은 다시 3개의 서브 트리로 나뉜다.

나머지도 마찬가지이다.

노드들 간에는 부모, 형제, 조상, 자손 관계가 존재한다.
A는 B의 부모 노드(parent node)이며, 반대로 B는 A의 자식 노드(children node)이다.
B, C, D는 형제 관계(sibling)이다.
조상 노드(ancestor node)란 루트 노드에서 임의의 노드까지의 경로를 이루고 있는 노드들이다.
후손 노드(descendent node)는 임의의 노드 하위에 연결된 모든 노드들이다.
- 즉, 어떤 노드의 서브 트리에 속하는 모든 노드들은 후손 노드이다.
단말 노드(terminal node, leaf node)는 자식 노드가 없는 노드이다.
비단말 노드(nonterminal node)는 그 반대이다.

노드의 차수(degree)는 어떤 노드가 가지고 있는 자식 노드의 개수이다.
- ex) 루트 노드 A의 경우 자식 노드가 3개이기 때문에 차수도 3이다.
- 단말 노드는 차수가 0인 노드이다.

트리의 차수는 트리가 가지고 있는 노드의 차수 중에서 가장 큰 값이다.
- ex) A, B노드의 차수가 3으로 전체 트리의 차수는 3

레벨(level)은 트리의 각층에 번호를 매기는 것으로, 루트의 레벨은 1, 한 층씩 내려갈수록 1씩 증가한다.
- ex) A의 레벨은 1, B의 레벨은 2

높이(height)는 트리가 가지고 있는 최대 레벨이다.
- ex) 위 그림의 트리의 높이는 3

트리들의 집합을 포레스트(forest)라 한다.

A는 루트 노드이다.
B는 D, E, F의 부모 노드이다.
C는 B의 형제 노드이다.
D, E, F는 B의 자식 노드이다.
B의 차수는 3이다.
트리의 높이는 4이다.

2. 이진트리

모든 노드가 2개의 서브 트리를 가지고 있는 트리를 이진트리(binary tree)라 한다.
서브 트리는 공집합일 수 있다.
따라서 이진트리의 노드에는 최대 2개까지의 자식 노드가 존재할 수 있고 모든 노드의 차수가 2 이하가 된다.
서브 트리 간의 순서가 존재해 왼쪽 서브 트리와 오른쪽 서브 트리로 구별된다.

이진트리의 정의

공집합이거나
루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합 (이진트리의 서브 트리들은 모두 이진트리여야 한다.)

위의 그림에서 SUB3은 하나의 노드 D로만 이루어져 있다.
- 노드 D를 SUB3의 루트라고 생각하면 SUB3의 서브 트리는 공집합이다.
- 정의 1에 의해 공집합도 이진트리 이므로 정의 2에 의해 SUB3은 루트와 공집합 서브 트리 2개를 가지는 이진트리이다.
같은 식으로 SUB2 역시 루트와 공집합 서브 트리 2개를 가지는 이진트리이다.
SUB1은 루트 노드 B와 서브 트리 SUB3과 공집합 서브 트리를 가진 이진트리이다.
최종적으로 전체 트리는 루트 노드 A와 SUB1, SUB2의 두 개의 서브 트리를 가진 이진트리이다.

이진트리의 성질

이진트리의 분류

1. 포화 이진트리(full binary tree)

각 레벨에 노드가 꽉 차있는 이진트리를 의미
높이 k인 이진트리는 정확하게 2^k -1개의 노드를 가진다.
각 노드에 번호를 붙일 수 있다.
번호는 레벨 단위로 왼쪽에서 오른쪽으로 번호를 붙이면 되고 번호는 항상 일정하다. (A~G -> 1~7)

2. 완전 이진트리(complete binary tree)

높이가 k일 때 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 순서대로 노드가 채워져 있다.
마지막 레벨에서는 노드가 꽉 차 있지 않아도 되지만 중간에 빈 곳이 있어서는 안 된다.
따라서 포화 이진트리는 항상 완전 이진트리이지만 그 역은 성립 안됨
번호를 붙일 수 있음

3. C언어에서의 이진트리 표현법

배열 이용
포인터 이용

Java언어에서의 이진트리 표현은 아래 포스트를 확인해주세요.

[Java] 트리(tree) 구현 - 1차원 배열 / 2차원 배열 / 클래스 3가지 방법 구현

3-1. 배열 표현법

주로 포화 이진 트리나 완전 이진트리의 경우 많이 쓰이는 방법이다.

그 외의 이진트리도 저장이 불가능한 것은 아니지만 기억공간의 낭비가 심해진다. (아래 그림 참고)

저장하고자 하는 이진트리를 일단 완전 이진트리라고 가정하고 깊이가 k이면 최대 2^k -1개의 공간을 연속적으로 할당한 다음

완전 이진트리의 번호대로 노드들을 저장한다.

인덱스 0은 사용하지 않음(사용 않는 편이 계산을 간단하게 함)

배열 표현법에서는 인덱스만 알면 노드의 부모나 자식을 쉽게 알 수 있다.

노드 i의 부모 노드 인덱스 = i / 2
노드i의 왼쪽 자식 인덱스 = 2i
노드i의 오른쪽 자식 인덱스 = 2i + 1

3-2. 링크 표현법

노드가 구조체로 표현되고, 각 노드가 포인터를 가지고 있어서 이 포인터를 이용하여 노드와 노드를 연결하는 방법이다.

하나의 노드는 3개의 필드를 가진다.

데이터를 저장하는 필드, 왼쪽 자식 노드와 오른쪽 자식 노드를 가리키는 2개의 포인터 필드를 가진다.

2개의 포인터를 이용해 부모 노드와 자식 노드를 연결한다.

구조체를 이용해 노드의 구조를 정의하고 링크는 포인터의 개념을 이용해 정의하면 된다.

저장되는 데이터는 정수라고 가정

링크 법으로 표현된 트리는 루트 노드를 가리키는 포인터만 있으면 트리안의 모든 노드들에 접근할 수 있다. (연결 리스트와 유사)

노드들은 모두 동적 메모리 할당을 이용하여 생성됨

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

* C로는 전체 구현 안함 X 개념만 / Java는 아래 관련 포스트 확인

참고

아래를 참고해 정리한 내용입니다.

C언어로 쉽게 풀어쓴 자료구조(개정 3판) - 생능 출판 - 8장 트리