[자료구조] 트리 (Tree)

트리 (Tree)

트리 구조란 그래프의 일종으로 여러 노드가 한 노드를 가리킬 수 없는 구조입니다. 

 

트리 용어

루트 노드: 최상위 노드

단말 노드: 자식이 없는 노드

내부: 단말 노드가 아닌 노드

간선: 노드를 연결하는 선 (branch, edge라고도 부름), 노드가 N개일 경우 N-1개의 간선을 가진다

노드의 크기: 자신을 포함한 모든 자손 노드의 개수

    - 자손노드는 자신의 하위 모든 노드, 자식 노드는 자신의 바로 하위 노드

노드의 깊이: 루트노드에서 해당 노드에 도달하기 위해 거치는 간선의 수

노드의 레벨: 트리의 특정 깊이에 있는 노드의 집합

 

트리 종류

이진 트리 (Binary Tree)

- 각 노드가 최대 두개의 자식을 갖는 트리

이진 트리 순회

중위 순회
  - 왼쪽 서브 트리 > 현재 노드 > 오른쪽 서브 트리

전위 순회
  - 현재 노드 > 왼쪽 서브 트리 > 오른쪽 서브 트리

후위 순회
  - 왼쪽 서브 트리 > 오른쪽 서브 트리 > 현재 노드

 

완전 이진 트리 (Complete Binary Tree)

- 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있음

- 마지막 레벨은 왼쪽에서 오른족으로 차있어야함

전 이진 트리 (Full Binary Tree)

- 모든 노드가 0개 또는 2개의 자식의 노드를 갖는 트리

포화 이진 트리

- 모든 말단 노드는 같은 높이에 있어야 하면서 마지막 레벨이 꽉 채워져 있어야 함

 

이진 탐색 트리 (Binary Search Tree)

- 모든 노드가 아래와 같은 특정 순서를 따르는 속성이 있는 이진 트리

- (왼쪽 자식 <= n < 오른쪽 자식) 모든 노드에 대해서 반드시 참이어야 함

 

 

 

참고 문서

---

gmlwjd9405.github.io/2018/08/12/data-structure-tree.html