tree

하나의 노드가 여러 노드를 가르킬수 있으며 비선형적 자료구조

• 데이터 구조의 계층적인(상하관계) 속성을 표현할때 사용할 수 있다.
• 재귀적인 구조를 가지고 있다.

✓ 노드 (node) : 트리 구조를 이루는 데이터
✓ 루트 (root) : 트리의 시작점
✓ 간선 (edge) : 노드와 노드를 연결하는 선
✓ 부모 (parent) : 두 노드가 상하관계에 있을 때 상위에 존재하는 노드
✓ 자식 (children) : 부모 노드의 하위에 위치한 노드
✓ 단말 (leaf) : 자식이 없는 노드
✓ 형제 (sibling): 같은 부모를 가지는 노드
✓ 깊이 (depth) : 노드에서 루트까지의 거리
✓ 차수 (degree) : 하위 트리의 개수

tree 구현

tree 종류

✓ 이진 트리 : 각 노드가 최대 2개의 자식 노드를 가지는 트리
✓ 정 이진 트리 (full binary tree) : 모든 노드가 2개의 자식을 가지거나 자식이 없는 트리
✓ 포화 이진 트리 (perfect binary tree) : 모든 노드가 2개의 자식을 가지고 leaf 노드가 같은 레벨인 트리
✓ 완전 이진 트리 (complete binary tree) : 아래 두 가지의 조건을 모두 만족하는 트리

• 마지막 레벨을 제외하고 모든 노드가 채워져야 한다.
• 노드는 왼쪽에서 오른쪽으로 채워져야 한다. (오른쪽 노드가 있다면 무조건 왼쪽 노드도 존재한다.)

tree 순회

트리 구조에서 각 노드를 한 번씩 방문하는 과정

✓ 전위 탐색 (Pre-order)

• 노드 방문
• 왼쪽 서브 트리를 순회
• 오른쪽 서브 트리를 순회
  

✓ 중위 탐색 (In-order)

• 왼쪽 서브 트리를 순회
• 노드 방문
• 오른쪽 서브 트리를 순회

✓ 후위 탐색 (Post-order)

• 왼쪽 서브 트리를 순회
• 오른쪽 서브 트리를 순회
• 노드 방문

틀린 부분이 있거나 보충해야 할 내용이 있다면 댓글이나 DM(sungstonemin)으로 알려주시면 감사하겠습니다😄