자료구조

tree

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

간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.

트리에서 최상위 노드를 루트 노드(root node)라고 한다.

또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node)

B를 A의 자식 노드(child node)라고 한다.

자식 노드가 없는 노드를 잎 노드(leaf node)라고 한다.

잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다.

binary-tree

바이너리트리, 이진트리 같은 말이다.

각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조이다.

크기가 9이고, 높이가 3인 이진 트리

탐색

in-order : 왼쪽 자식노드, 내 노드, 오른쪽 자식노드 순서로 방문한다.
pre-order : 내 노드, 왼쪽 자식노드, 오른쪽 자식노드 순서로 방문한다.
post-order : 왼쪽 자식노드, 오른쪽 자식노드, 내 노드 순서로 방문한다.
level-order : 내 노드, 내 노드로부터 깊이 1인 노드들, 내 노드로부터 깊이 2인 노드들, ... , 내 노드로부터 깊이 N인 노드들 (N: 나(트리)의 깊이)

Referfence

https://ko.wikipedia.org/wiki/트리_구조

https://ko.wikipedia.org/wiki/이진_트리

---