트리의 특징
트리의 구성요소
•
트리는 모두 Node 로 구성되어 있으며 트리 내의 위치에 따라 명칭이 달라진다.
•
Root Node : 트리의 가장 최상단에 위치한 Node
•
Branch Node : Root 와 Leaf 사이에 위치한 Node
•
Leaf Node : Branch 노드 끝에 존재하는 Node 또는 단말 노드 (Terminal Node)
트리의 Node 간의 관계
•
Parent : 특정 Node 의 상위 Node
•
Children : 특정 Node 의 하위 Node
•
Sibling : 같은 상위 Node 에서 분기된 위상이 같은 Node
트리의 Path
•
Length : 특정 Node 부터 시작해서 특정 Node 까지 이동하는 데 거치는 Node 의 개수
•
Depth : Root Node 로 부터 특정 Node 까지의 경로 length
•
Level : Depth 가 같은 Node 들의 집합
•
Height : 전체 트리에서 Depth 가 가장 깊은 곳의 값 즉 전체 트리의 높이가 된다.
•
Degree
◦
특정 Node 의 차수 (Degree) 는 Children Node의 갯수
◦
트리의 차수 (Degree) 는 각 Node 들의 Degree 중 가장 높은 값
트리의 표현방법
중첩된 괄호 표기법 (Nested Parenthesis Notation)
(A(B(C)(D(E)(F)))(G(H))(I(J(K))))
Python
들여쓰기 표기법 (Indentation Notation)
•
탐색기의 폴더 구조의 표기법
노드의 특징
노드의 표현방법
N-링크 표기법 (N-Link)
•
Node의 Degree 가 N 이라면, 노드가 N 개의 링크를 가지고 있어서 이 링크들이 각각 자식 노드를 가리키도록 노드를 구성하는 방법
•
단점으로 차수가 노드마다 달라지는 트리에는 적용하기 매우 복잡하다.
Left Child-Right Sibling 표기법
•
왼쪽에는 자식에 대한 포인터를 갖고, 오른쪽에는 형제에 대한 포인터를 갖는 노드 구조
•
특정 Node 의 모든 Children Node 를 얻으려면, 왼쪽 자식 노드에 대한 포인터만 가지고 있으면 된다.
