트리 순회

전산학에서 트리 순회(Tree traversal)는 트리 구조에서 각각의 노드를 정확히 한 번만, 체계적인 방법으로 방문하는 과정을 말한다. 이는 노드를 방문하는 순서에 따라 분류된다. 여기서 설명하는 알고리즘은 이진 트리에 대해서 작성되었지만, 다른 모든 트리에서도 일반화될 수 있다.

순회

연결 리스트와 1차원 배열과 같은 선형 자료 구조에서는 한 가지의 논리적인 순회 방법만이 존재하지만, 트리 구조의 순회에는 많은 방법이 존재한다. 이진 트리의 루트 노드에서 시작해서, 세 가지 주요 단계를 거치며 순회를 진행하는데, 그 단계에는 현재 노드를 방문하는 것, 왼쪽 자식 노드를 순회하는 것과 오른쪽 자식 노드를 순회하는 것이 있다. 이러한 과정은 재귀로 쉽게 설명할 수 있다.

구현

preorder(node)
  print node.value
  if node.left ≠ null then preorder(node.left) 
  if node.right ≠ null then preorder(node.right)
inorder(node)
  if node.left  ≠ null then inorder(node.left)
  print node.value
  if node.right ≠ null then inorder(node.right)
postorder(node)
  if node.left  ≠ null then postorder(node.left)
  if node.right ≠ null then postorder(node.right)
  print node.value
모든 구현은 트리의 높이에 비례한 호출 스택 공간이 필요하다. 약하게 균형 잡힌 트리에서 이는 더욱 중요하다.
각각의 노드가 부모 포인터를 가지고 있거나 스레드 이진 트리인 경우 스택을 쓸 필요가 없다. 스레드를 쓰는 경우, 중위 순회를 더 크게 개량할 수 있고, 전위 순회와 후위 순회에 필요한 부모 노드의 필요성을 되찾더라도 이것이 알고리즘에 기반한 간단한 스택보다 더 느려지게 된다.
스레드 트리를 중위 순회할 경우, 이런 식으로 할 수 있다.
inorder(node)
  while hasleftchild(node) do
    node = node.left
  do
    visit(node)
    if (hasrightchild(node)) then
      node = node.right
      while hasleftchild(node) do
        node = node.left
    else
      while node.parent ≠ null and node = node.parent.right
        node = node.parent
      node = node.parent
  while node ≠ null
스레드 이진 트리는 포인터가 자식 노드인지를 판단하는 부분이 추가된다.

큐 기반 레벨 순서 순회

레벨 순서 순회는 간단한 큐로 구현할 수 있다. 아래는 그 의사코드이다. 이 구현에는 마지막 노드의 깊이에 비례한 공간이 필요하다. 이는 모든 노드 번호의 합계 / 2가 된다. 공간을 더욱 효율적으로 사용하고 싶으면 반복 심화 깊이 우선 탐색(iterative deepening depth-first search)을 사용한다.
levelorder(root) 
  q = empty queue
  q.enqueue(root)
  while not q.empty do
    node := q.dequeue()
    visit(node)
    if node.left ≠ null
      q.enqueue(node.left)
    if node.right ≠ null
      q.enqueue(node.right)

중위 순회

중위 순회는 특히 이진 탐색 트리에서 사용되는데, 이진 탐색 트리의 설정에 따른 기본적인 순서에서 값을 반환해야 하기 때문이다. 왜냐하면, 이진 탐색 트리의 노드 n에서, n의 모든 왼쪽 서브 트리는 n보다 작고, n의 모든 오른쪽 서브 트리는 n보다 크거나 같다. 따라서, 만약 왼쪽 서브 트리를 순서대로 방문하게 된다면, 재귀 호출을 사용하고, n을 방문하고, 오른쪽 서브 트리를 순서대로 방문하여, n을 루트로 하는 모든 서브트리를 순서대로 방문하게 된다. 재귀 호출이 정확히 서브 트리를 순서대로 방문하는지 구조적 귀납법의 수학적 원리를 사용하여 추측할 수 있다. 역순 중위 순회는 값을 내림차순으로 정렬하는 것과 비슷하다.

반복 순회

모든 재귀 알고리즘은 트리의 깊이에 비례한 스택 공간이 필요하다. 재귀적 순회는 여러가지 잘 알려진 방법을 이용하여 반복적인 방법으로 변환할 수 있다. 아래의 예제는 재귀적인 방법을 사용하지 않는 후위 순회를 보여준다.
nonRecursivePostorder(rootNode)
  nodeStack.push(rootNode)
  while (! nodeStack.empty())
    currNode = nodeStack.peek()
    if ((currNode.left != null) and (currNode.left.visited == false))
      nodeStack.push(currNode.left)
    else 
      if ((currNode.right != null) and (currNode.right.visited == false))
        nodeStack.push(currNode.right)
      else
        print currNode.value
        currNode.visited := true
        nodeStack.pop()
이 경우, 각각의 노드는 보통의 정보가 아닌 추가적인 visited 플래그가 필요하다. 다음 예제는 visited 플래그를 사용하지 않는 전위 순회 함수를 자바로 구현한 것이다.
public void traverseTree(Node root) {
   Stack nodes = new Stack();
   nodes.push(root);
   Node currentNode;
   while (! nodes.isEmpty()){
      currentNode = nodes.pop();
      Node right = currentNode.right();
      if (right != null)
         nodes.push(right);
      Node left = currentNode.left();
      if (left != null)
         nodes.push(left);      
      System.out.println("Node data: "+currentNode.data);
   }}
만약 각각의 노드가 부모 노드의 정보를 가지고 있다면, 반복 순회는 스택이나 visited 플래그를 쓰지 않고도 구현할 수 있다.