트리(Tree) 개념과 파이썬 구현

트리(Tree)

트리는 그래프의 종류로 실제 트리를 거꾸로 세워 놓은 모양의 자료구조입니다.

 

트리의 예시로는 조직의 계층구조가 있습니다.

 

트리에서는 알아야 할 용어들이 있습니다.

 

루트 : 트리의 최상위에 있는 노드

부모 노드 : 노드의 상위에 연결된 노드

자식 노드 : 노드의 하위에 연결된 노드

형제 노드 : 동일한 부모를 가지는 노드

조상 노드 : 루트까지의 경로상에 있는 모든 노드들의 모임

후손 노드 : 노드 아래로 있는 모든 노드들의 모임

차수 : 자식 노드의 수

이파리 : 자식이 없는 노드

레벨 : 깊이(루트가 레벨 1이고 아래로 갈수록 1씩 증가

높이 : 트리의 최대 레벨

 

위의 트리에서 보면 루트는 A입니다.

B와 C의 부모노드는 A이고 A의 자식 노드는 B, C입니다.

그리고 B와 C는 부모노드가 A로 같기 때문에 형제 노드입니다.

L의 조상 노드는 G, C, A입니다.
C의 후손 노드는 G, H, L, M입니다.
A의 차수는 2입니다.
이파리는 I, J, E, K, L, M, H입니다.
트리의 높이는 4입니다.