트리(Tree)

트리는 계층적 구조를 가진 자료구조이며, 선형이다. 트리는 노드가 간선으로 연결되어있다.

한 노드와 간선으로 연결되어 있는 노드 중 바로 위층에 있는 노드를 부모 노드, 바로 아래 층에 있는 노드를 자식 노드라고 한다. 또, 트리의 모든 노드 중 아래 간선의 갯수 중 가장 많은 것의 갯수를 차수라고 한다.

트리에는 루트 노드, 리프 노드가 있다. 루트 노드는 트리의 맨 위의 노드이다. (그림에서 A)

리프 노드는 자식 노드가 없는, 즉 차수가 0인 노드이다.

루트의 자식 노드가 새로운 노드로 되어 구성하는 트리를 서브 트리라고 한다.

트리의 높이는 루트 노드로부터 간선의 개수다.

트리의 레벨은 루트 노드로부터의 층수이다. 루트 노드의 층수는 1이다.

트리의 순회 방법으로는 4가지가 있다.

전위, 중위, 후위, 레벨 순회가 있다.

전위 순회는 루트 노드 → 왼쪽 자식 노드의 하위 트리 → 오른쪽 자식 노드의 하위 트리 순으로 방문한다.

중위 순회는 좌측 하위 트리 → 루트 노드 → 우측 하위 트리 순으로 방문한다.

후위 순회는 좌측 하위 트리 → 우측 하위 트리 → 루트 노드 순으로 방문한다.