Inorder Traversal
-
Common Lisp으로 구현한 트리(Tree)를 중위 순회(In-order Traversal)하는 반복자(Iterator)Programmer/Programming 2016. 5. 17. 15:02
사소해 보이는 연산 뒤에 숨어있는 것 은 인턴 전화 면접에서 깨달은 내용을 담고 있다. 이 글은 인턴 면접을 소재로 하는데, 면접의 내용 중에 트리(Tree)를 중위 순회(Inorder Traversal)하는 반복자를 구현하는 것이 있다. 이 글의 필자는 C++로 구현하였다. 평소 업무에서 Common Lisp을 쓸 기회가 없어서 자꾸 잊어버린다. 도구를 갈고 닦지 않으면 녹슬기 마련이다. 간단하게 트리의 중위 순회를 Common Lisp으로 작성해봤다. 순회 순서 왼쪽의 하위 트리를 순회한다. 자신(중간) 오른쪽의 하위 트리를 순회한다. 순회할 첫번째 노드 구하기 : begin 최상위 노드의 가장 왼쪽에 있는 노드가 첫번째 노드이다. 구현은 왼쪽 하위 노드를 재귀적으로 찾는다. (defun begin ..