Tree (트리)

그래프의 일종.

데이터 항목의 한 묶음을 세그먼트라고 하는데, 이 세그먼트 사이의 연결을 나뭇가지처럼 표현한 것이 트리 구조다.

​

1. 트리 종류

a. 이진 트리 (binary tree)

- 자식노드가 최대 2개면 이진 트리라고 한다.

- 이진 탐색 트리, 힙 등을 구현하기 위해 사용된다.

b. 삼항 트리 (ternary tree)

- 자식노드가 최대 3개면 삼항 트리로 구분된다.

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

- 노드들이 왼쪽부터 차곡차곡 쌓여있는 형태의 트리

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

- 단말 노드까지의 깊이가 동일하면서 모든 노드의 자식 노드가 2개인 이진 트리를 말한다.

​

2. 노드 종류

a. 노드

- 그래프를 구성하는 하나의 요소.

- 그래프는 점과 선으로 구성되는데, 이 점을 노드라고 한다.

(트리구조도 그래프의 일종)

b. 루트 노드

- 트리 구조의 최상위 노드를 루트(root)라고 한다.

c. 부모노드

- 하위 노드를 가리키는 상위 노드를 부모(parent)라고 한다.

d. 자식노드

- 상위 노드가 가리키는 하위 노드를 자식(child)라고 한다.

e. 형제 노드

- 같은 계층에 있는 노드를 형제(siblings)라고 한다.

f. 잎 노드, 단말 노드

- 자식 노드가 없는 노드를 잎(leaf) 또는 단말(terminal)라고 한다.

​

3. 용어

a. 경로(path)

- 한 노드에서 다른 한 노드에 이르는 길 사이에 있는 노드들의 순서

b. 길이(length)

- 출발 노드에서 도착 노드까지 거치는 노드의 갯수

c. 깊이(depth)

- 루트 경로의 길이

d. 레벨(level)

- 루트 노드(1) 로 부터 노드까지 연결된 엣지의 수의 합

e. 높이(height)

- 가장 긴 루트 경로의 길이

f. 차수(degree)

- 각 노드의 자식의 갯수

- 트리의 차수(degree of tree): 트리의 최대 차수

g. 크기(size)

- 노드의 개수

h. 너비(width)

- 가장 많은 노드를 갖고 있는 레벨의 크기

​

4. 순회 연산

a. 전위 순회 (PRE-ORDER)

- 부모노드 -> 왼쪽 자식노드 -> 오른쪽 자식노드 순으로 순회

b. 중위 순회 (IN_ORDER)

- 왼쪽 자식노드 -> 부모노드 -> 오른쪽 자식노드 순으로 순회

c. 후위 순회 (POST-ORDER)

- 왼쪽 자식노드 -> 오른쪽 자식 노드 -> 부모노드 순으로 순회

d. 계층 순회 (LEVEL-ORDER)

- 트리의 레벨 순서에 따라 순회

​

​

참고 출처

Binary Tree(이진 트리)

 

 

이진 트리

 

자료구조 :: 이진 트리 순회 - 전위 순회, 중위순회, 후위순회

 

전위 순회, 중위 순회, 후위 순회 - 트리를 어떤 순서로 방문할까?

 

[자료구조] Level order traversal 시 연속적인 자료가 탐색되는 이진트리 만들기 (추가)

 

 

다람쥐와 포동포동이

 

RememberCook 9월 28일 정식 출시!