[자료구조] 트리 (Tree)

트리 (Tree)

- 계층 구조 (Hierarchical Structure)로 자료를 저장하는 자료구조 (비선형 자료구조)

- 노드(Node), 간선 (Edge)의 집합

- 계층 구조 : 특정 부모 노드 하나에 여러 개의 자식 노드들이 연결되는 구조

회사 조직도 모델링

​

---

노드 종류

1. 위치 기준

노드 이름	설명
루트(Root) 노드	트리의 첫 번째 노드
단말(Leaf 혹은 Terminal) 노드	자식 노드가 없는 노드
내부 (Internal) 노드	자식 노드가 있는 노드

 

2. 관계 기준

노드 이름	설명
부모(Parent) 노드	자식 노드와 간선(Edge)으로 연결
자식(Child) 노드	부모 노드와 간선(Edge)으로 연결
선조(Ancestor) 노드	루트 노드 - 부모 노드까지 경로 상에 있는 모든 노드
후손(Descendant) 노드	특정 노드의 아래에 있는 모든 노드
형제(Sibling) 노드	같은 부모 노드의 자식 노드

 

---

노드의 속성

속성 이름	설명
레벨(Level)	루트 노드로부터 현재 노드까지의 거리 (루트노드 레벨 : 1)
높이(Height)	가장 먼 거리에 있는 자식 노드의 높이에 1을 더한 값 (단말 노드 높이 : 1)
차수(Degree)	자식 노드의 개수

​

※'레벨' 은 위(루트 노드)에서 아래로

'높이'는 아래(가장 멀리 있는 자식노드)에서 위로

​

EX)

• 2번 노드의 레벨 : 2
• 6번 노드의 높이 : 1
• 4번 노드의 높이 : 4
• 10번 노드의 레벨 : 4