1. 트리

Reference :
- C언어로 쉽게 풀어쓴 자료구조 [개정3판] / 천인국, 공용해, 하상호 / 생능출판사
- 건국대학교 컴퓨터공학과 자료구조 수업 / 김성렬 교수님
- https://velog.io/tags/datastructure

---

1. 트리의 개념

선형 자료 구조

: 리스트, 스택, 큐

 

계층적인 자료구조 = 비선형 자료구조

: 트리

트리란?

: 구조가 트리처럼 생겨서 이름이 트리 ㅋㅋ

ex) 결정 트리 : 인간의 의사 결정 구조를 표현한 한 가지 방법

---

- 트리의 용어들

노드

: 트리의 구성 요소

 

루트 노드 (root)

: 가장 높은 곳에 있는 노드

 

서브 트리 (sub tree)

: 나머지 노드

 

간선 (edge)

: 루트와 서브트리를 연결하는 선

 

노드의 종류

: 부모 노드, 자식 노드, 형제 노드, 조상 노드, 후손 노드, 단말 노드, 비단말 노드

 

노드의 차수 (degree)

: 어떤 노드가 가지고 있는 자식 노드의 개수

ex) 단말 노드는 차수가 0

 

트리의 차수

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

ex) 그림의 트리의 차수는 3

 

트리에서의 레벨 (level)

: 트리의 각층에 번호를 매기는 것

=> 루트의 레벨은 1이 되고 한 층씩 내려갈수록 1씩 증가

 

트리의 높이 (height)

: 트리가 가지고 있는 최대 레벨

ex) 그림의 트리의 높이는 3

 

포리스트 (forest)

: 트리들의 집합

---

- 트리의 종류

트리를 프로그램 안에서 표현하는 가장 일반적인 방법

: 각 노드가 데이터를 저장 필드와 자식 노드를 가리키는 링크 필드를 가지게 하는 것

 

링크 n

: 자식 노드의 개수, 노드의 차수

 

- 일반 트리

: 자식 노드의 개수가 n개인 트리

=> 노드의 크기가 고정되지 않는 문제점이 있다

 

- 이진 트리

: 자식 노드의 개수가 2개인 트리