트리

트리

리스트는 순서대로 데이터를 나열하는 자료구조인 반면, 트리는 데이터 사이의 계층 관계를 나타내는 자료구조입니다.
트리를 구성하는 요소는 노드(node)와 가지(edge)입니다. 각각의 노드는 가지로 연결되어 있습니다. O는 노드 -는 가지를 나타냅니다.

• 루트
  트리의 가장 윗보분에 위치하는 노드를 루트(root)라고 합니다. 하나의 트리에는 하나의 루트만 있습니다. 위 그림을 거꾸로 보면 나무 모양과 비슷하다는 것을 알고 있습니다. 루트는 이 나무의 뿌리에 해당하는 부분입니다.

• 리프
  트리의 가장 아랫부분에 해당하는 노드를 리프(leaf)라고 합니다. 이때 '가장 아래에 위치한다'라는 말은 물리적으로 가장 아랫부분에 위치한다는 의미가 아니라 노드가 더 이상 뻗어나가지 않는 마지막에 위치한다는 의미로 끝 노드(terminal node) 또는 바깥 노드(external node)라고도 합니다.

• 안쪽 노드
  리프를 제외한 나머지 노드(루트 포함)를 안쪽 노드라고 합니다.

• 안쪽 노드를 끝이 아닌 노드(non-terminal node)라고 합니다.

• 자식
  어떤 노드에서 가지로 연결된 아래쪽 노드를 자식(child)이라고 합니다. 노드는 자식을 여럿 가질 수 있으며, 리프는 자식을 가질 수 없습니다.

• 부모
  어떤 노드에서 가지로 연결된 바로 위쪽 노드를 부모(parent)라고 합니다. 각 노드에서 부모는 하나뿐이며, 루트는 부모를 가질 수 없습니다.

• 형제
  부모가 같은 노드를 형제(sibling)라고 합니다.

• 조상
  어떤 노드에서 위쪽으로 뻗어 나간 모든 노드를 조상(ancestor)이라고 합니다.

• 자손
  어떤 노드에서 아래쪽으로 뻗어 나간 모든 노드를 자손(descendant)이라고 합니다.

• 레벨
  루트로부터 얼마나 떨어져 있는지를 나타낸 값을 레벨(level)이라고 합니다. 루트의 레벨은 0이고, 루트에서 가지가 하나씩 아래로 뻗어나갈 때마다 레벨이 1씩 늘어납니다.

• 차수
  노드가 갖는 자식의 수를 차수(degree)라고 합니다. 모든 노드의 차수가 n이하인 트리를 n진 트리라고 합니다.

• 높이
  루트에서 가장 멀리 떨어진 리프까지의 거리(리프 레벨의 최댓값)를 높이(height)라고 합니다.

• 서브트리
  트리안에서 다시 어떤 노드를 루트로 정하고 그 자손을 이루어진 트리를 서브트리(subtree)라고 합니다.

• 널트리
  노드가 전혀 없는 트리를 널트리(null tree)라고 합니다.

순서 트리와 무순서 트리

형제 노드 사이의 순서 관계를 따지는지 그렇지 않은지에 따라 트리는 두 종류로 분류합니다. 형제 노드의 순서를 따지면 순서 트리(ordered tree), 따지지 않으면 무순서 트리(unordered tree)라고 합니다.

순서 트리 탐색

• 너비 우선 탐색(가로형 탐색)
  너비 우선 탐색(breadth-first search)은 낮은 레벨에서 시작해 왼쪽에서 오른쪽 방향으로 따라가다가한 레벨에서 탐색이 끝나면 다음 레벨로 내려갑니다.
  

A -> B -> C -> D -> E -> F -> G -> H -> I -> J -> K -> L

• 깊이 우선 탐색(세로형 탐색)
  깊이 우선 탐색(depth-first search)은 리프에 이를때까지 아래로 내려가면서 탐색합니다. 리프에 도달해 더 이상 탐색할 곳이 없으면 부모에게 돌아갑니다. 그런 다음 다시 자식 노드로 내려갑니다.
  
  위에서처럼 깊이 우선 탐색을 진행하면 노드 A는 총 3번 지나갑니다.

  A -> B / B -> C / C -> A

  다른 노드의 경우도 마찬가지로 두 자식 가운데 한쪽이 없으면 노드를 지나는 횟수가 줄겠지만 노드를 지나는 최댓값은 3이 됩니다. 그런데 깊이우선 탐색을 진행하면서 '언제 노드를 방문할지'는 3종류로 구분이 가능합니다.
  

  • 전위 순회(preorder)
    노드 방문 -> 왼쪽 자식 -> 오른쪽 자식

    A -> B -> D -> H -> E -> I -> J -> C -> F -> K -> L -> G

  • 중위 순회(inorder)
    왼쪽 자식 -> 노드 방문 -> 오른쪽 자식

    H -> D -> B -> I -> E -> J -> A -> K -> F -> L -> C -> G

  • 후위 순회
    왼쪽 자식 -> 오른쪽 자식 -> 노드 방문

    H -> D -> I -> J -> E -> B -> K -> L -> F -> G -> C -> A