Page 405 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

차수

노드가 갖는 자식의 수를 차수(degree)라고 합니다. 예를 들어 X의 차수는 2, Y의 차수는 3입
니다. 모든 노드의 차수가 n 이하인 트리를 n진 트리라고 합니다. 앞의 그림 10-1의 트리는
모든 노드의 자식이 3개 이하이므로 3진 트리입니다.
모든 노드의 자식 수가 2개 이하인 경우는 특별히 이진트리라고 합니다.

높이

루트부터 가장 멀리 떨어진 리프까지의 거리(리프 레벨의 최댓값)를 높이(height)라고 합니다.
그림 10-1에서 트리의 높이는 3입니다.

서브 트리
트리 안에서 다시 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리를 서브 트리
(subtree)라고 합니다. 그림 10-1에서 초록색으로 표시한 부분은 X를 루트로 하는 서브 트리
입니다.

널 트리
노드, 가지가 없는 트리를 널 트리(null tree)라고 합니다.

순서 트리와 무순서 트리
a b
형제 노드의 순서가 있는지 없는지에 따라 트리를 X X
두 종류로 분류합니다. 형제 노드의 순서를 따지면 Y Z Z Y

순서 트리(ordered tree), 따지지 않으면 무순서 트리
두 트리는 다른 순서 트리이면서
(unordered tree)라고 합니다. 예를 들어, 그림 10-2 같은 무순서 트리라고 할 수 있습니다.
의 a , b 는 순서 트리로 보면 다른 트리지만 무순서 [그림 10-2] 순서 트리와 무순서 트리

트리로 보면 같은 트리라고 할 수 있습니다.

순서 트리 탐색

순서 트리의 노드를 스캔하는 방법은 두 가지입니다. 여기서는 이진트리를 예로 들어 살펴보
겠습니다.

10•트리 405