Winwoo's Story

이진 트리의 순회

1. 순회의 세 가지 방법

- 기준 : root node를 언제 방문 하는지

- 재귀적 형태로 구성하면 높이 상관없이 순회 가능

※ VisitFuncPtr 함수 포인터를 사용하여 트리 구조를 이용한 원하는 행동을 할 수 있음

Tree란?

"개층적 관계(Hierarchical Relationship)를 표현하는 자료구조"

트리의 예

트리의 용어 정리

- 노드(node) : 트리의 구성요소에 해당하는 'A, B, C, D, E, F'와 같은 요소

- 간선(edge) : 노드와 노드를 연결하는 연결선

- 루트 노드(root node) : 트리 구조에서 최상위에 존재하는 'A'와 같은 노드

- 단말 노드(terminal node) : 아래로 또 다른 노드가 연결되어 있지 않은 'E, F, C, D'와 같은 노드

- 내부 노드(internal node) : 단말 노드를 제외한 모든 노드로 'A, B'와 같은 노드

트리의 노드간 관계

- 노드 A는 노드 B, C, D의 부모 노드(parent node)이다.

- 노드 B, C, D는 노드 A의 자식 노드(child node)이다.

- 노드 B, C, D는 부모 노드가 같아, 서로가 서로에게 형제 노드(sibling node)이다.

서브 트리의 이해

서브 트리 역시 서브 트리로 이뤄져 있으며, 그 서브 트리 역시 또 다른 서브 트리로 이뤄져 있다. 

 -> 특징 : 재귀적!

- 하나의 트리를 구성하는 왼쪽과 오른쪽의 작은 트리를 가리켜 서브 트리라 한다.