Common Lisp으로 구현한 트리(Tree)를 중위 순회(In-order Traversal)하는 반복자(Iterator)

사소해 보이는 연산 뒤에 숨어있는 것 은 인턴 전화 면접에서 깨달은 내용을 담고 있다.
이 글은 인턴 면접을 소재로 하는데,
면접의 내용 중에 트리(Tree)를 중위 순회(Inorder Traversal)하는 반복자를 구현하는 것이 있다.
이 글의 필자는 C++^[각주:1]로 구현하였다.

평소 업무에서 Common Lisp을 쓸 기회가 없어서 자꾸 잊어버린다.
도구를 갈고 닦지 않으면 녹슬기 마련이다.
간단하게 트리의 중위 순회를 Common Lisp으로 작성해봤다.

순회 순서

1. 왼쪽의 하위 트리를 순회한다.
2. 자신(중간)
3. 오른쪽의 하위 트리를 순회한다.

순회할 첫번째 노드 구하기 : begin

• 최상위 노드의 가장 왼쪽에 있는 노드가 첫번째 노드이다.
  구현은 왼쪽 하위 노드를 재귀적으로 찾는다.

(defun begin (node)
  (if left-node
    (begin left-node)
    node))

다음 방문할 노드 얻기 : next

• 순회 순서에 의해서 자신 이후에는 오른쪽 하위 트리를 순회한다.
  따라서, 다음 노드는 오른쪽 하위 트리의 가장 왼쪽의 노드이다.

  (begin (right node))

• 오른쪽 하위 트리가 없다면, 이 단계에서는 더 이상 방문할 곳이 없다.
  가장 가까운 상위 단계의 중간 노드를 찾는다.^[각주:2]

  (mid node)

(defun next (node)
  (if right-node
    (begin right-node)
    (mid node)))

가장 가까운 상위 단계의 중간 노드 찾기 : mid

• 오른쪽(순서 3)에서 올라왔다면, 이 단계에서는 더 이상 방문할 곳이 없다.

  (if (eq node (right parent-node))
    ;; ...
    )

  다시, 가장 가까운 상위 단계의 중간 노드를 찾는다.

  (mid mid-node)

• 아니라면, 왼쪽(순서 1)에서 올라왔다.
  순회 순서에 따라서 중간 노드를 반환한다.

  mid-node

(defun mid (node)
  (when mid-node
    (if (eq node (right mid-node))
      (mid mid-node)
      mid-node)))

최종 코드

(defun begin (node)
  (let ((left-node (left node)))
    (if left-node
      (begin left-node)
      node)))

(defun next (node)
  (when node
    (labels ((mid (node)
               (let ((mid-node (parent node)))
                 (when mid-node
                   (if (eq node (right mid-node))
                     (mid mid-node)    ; traversal is done for the current tree. go up the parent node
                     mid-node)))))
      (let ((right-node (right node)))
        (if right-node
          (begin right-node)
          (mid node))))))

2016/01/13 - [Practice/Lisp] - 암호 문자열 감추기 문제 풀이 : Common Lisp, Scheme

2013/08/20 - [Theory/Data Structure] - GLib의 GTree로 알아보는 균형 이진 트리 알고리즘

1. C라고도 볼 수 있는데, 필자가 연산자 오버로딩을 언급해서 C++로 보았다. [본문으로]
2. 상위 단계로 올라갈 때,
   • (순서 1)이라면, 중간 노드를 찾는 것이고,
   • (순서 3)이라면, 다시 상위 단계로 올라가서 이를 반복하게 된다.
   결과는
   • 순회하지 않은 중간 노드를 찾거나
   • 중간 노드를 못찾거나 (왜? 모두 방문했으니까)
   둘 중에 하나이다.
   위 과정은 mid 함수 구현에서 다시 설명한다. [본문으로]