Tree(트리)

Tree(트리)

 

트리란?

비선형 자료구조로써 나무처럼 가지를 늘려가며 뻗어나가는 특징을 갖고 있고, 트리는 계층적 관계를 표현하는 자료구조

 

트리의 예

트리의 예로는 집안의 족보나 기업및 정부의 조직도도 트리의 예가 됨.

 

트리 관련 용어

 

 

노드 : node

트리의 구성 요소에 해당하는 A, B, C, D, E, F와 같은 요소.

간선 : edge

노드와 노드를 연결하는 연결선.

루트 노드 : root node

트리 구조에서 최상위에 존재하는 A와 같은 노드.

레벨 : level

각 층별로 숫자를 매긴 것.

높이 : height

트리의 최고 레벨을 가리켜 높이라 함.

부모 노드 : parent node

노드 A는 노드 B, C, D의 부모 노드이다.

자식 노드 : child node

노드 B, C, D는 노드 A의 자식 노드이다.

 

서브 트리

큰 트리는 작은 트리로 구성이 되는데 이렇듯 큰 트리에 속하는 작은 트리를 서브 트리라 함.

 

이진 트리

루트 노드를 중심으로 두 개의 서브 트리로 나뉘어 짐.

나뉘어진 두 서브 트리도 모두 이진 트리.

노드가 위치 할 수 있는 곳에 노드가 존재하지 않으면, 공집합 노드가 존재하는 것으로 간주.

 

포화 이진 트리와 완전 이진 트리

포화 이진 트리

모든 레벨이 꽉 차 있고 노드를 더 추가하려면 레벨을 늘려야 하는 이진 트리.

완전 이진 트리

포화 이진 트리처럼 모든 레벨이 꽉 찬 상태는 아니지만, 차곡차곡 빈틈없이 노드가 채워진 이진 트리를 뜻한다.

 

*이진 트리의 구현 링크

https://glorychoi.tistory.com/15

이진 트리(Binary Tree)

 

 

//출처 윤성우의 열혈 자료구조