트리

개념

트리(tree)란 원소들 간에 1:n 관계를 가지는 비성형 자료구조이다.
원소들 간에 계층 관계를 가지는 계층형 자료구조이다.
상위 원소에서 하위원소로 내려가면서 확장되는 트리모양의구조이다.
나무를 거꾸로 세운 구조라고 생각하면 된다.

이해

트리 자료구조의 예로 가계도가 있다. 맨위의 'A'는 시작지점으로 레벨 0, 트리에서의 '루트'가 된다. 0의 바로 밑의 자식인 'B' 'C'는 레벨 1, 맨 밑의 'D','E','F','G'는 레벨 2가 된다.

루트에서 시작을하여 (레벨 0) -> 그다음 세대를 레벨 1 -> 레벨 1에서의 그다음 세대들은 레벨 2가되는데
쉽게 가족단위로 생각을하면 레벨 0가 A가 시조이면서 0세대 라고 생각을하자 .
A가 자식을 낳아 그다음 1세대 B,C가 생기고 B가 자식을 낳아 2세대인 D,E 가 생기고 C역시 자식을 낳아 2세대인 F,G 가 생기게 된다

트리 구조

노드 (Node) - 트리의 원소
위의 그림에서 트리의 원소는 A,B,C,D,E,F,G가 된다.

루트(Node) - 트리의 시작 노드 (레벨 0)
위 그림에서의 루트는 A이다

간선(Edge)- 노드를 연결하는 선 . 부모 노드와 자식노드를 연결
위 그림에서 D,E의 부모노드는 B이다.

형제 노드 - 같은 부모노드의 자식 노드들
D,E 는 형제관계

조상노드 - 간선을 따라 루트 노드까지 경로에 있는 모든 노드들
E의 조상노드 : B, A

자손 노드 - 서브 트리에있는 하위 레벨의 노드들
B의 자손노드 : D,E

서브 트리 - 부모노드와 연결된 간선을 끊었을때 생성되는 트리
(각 노드는 자식 노드의 개수 만큼 서브트리를 가진다.)

차수, 높이
노드의 차수: 노드에 연결된 자식 노드의 수
A의 차수 =2 B의 차수 =2

트리의 차수 : 트리에 있는 노드의 차수중에서 가장큰값

단말 노드 : 차수가 0인 노드, 자식 노드가 없는 노드

노드의 높이 : 루트에서 노드에 이르는 간선의 수, 노드의 레벨
B의 높이 : 1 단말 노드의 높이 : 0 루트 A의 높이 : 2

트리의 높이 : 트리에있는 노드의 높이중에서 가장 큰 값, 최대 레벨

Level : 루트에서 어떤 노드까지의 간선의 수

Forest

Forest 는 서브트리의 집합을 의미한다.

트리 A에서 노드 A를 제거하면 , A의 자식 노드 B,C,D 에대한 서브트리가 생기고 이들의 집합이 Forest 가 된다.