코드 7-1에서 TreeNode 클래스의 생성자를 보면 실제 데이터를 담을 __data와 왼쪽 자식 노드를 참조할 __left, 오른쪽 자식을 가리킬 __right가 있는 것을 확인할 수 있습니다. 다음으로 이전에 구현했던 스택 클래스를 가져오겠습니다. 같은 폴더 안에 stack.py를 두고 모듈로 import해도 되고, 클래스를 복사해서 지금 작성 중인 파일에 붙여도 됩니다. 예제 코드에서는 스택 클래스를 복사해서 파일에 붙여 넣었습니다.

코드 7-2는 전위 순회를 구현한 것입니다.

코드 7-2

def preorder(cur):
    # 현재 노드가 empty node라면
    if not cur:
        return

    # 방문
    print(cur.data, end=' ')

    preorder(cur.left)  # 왼쪽 서브 트리로 이동

    preorder(cur.right) # 오른쪽 서브 트리로 이동

이번에도 방문은 노드의 데이터를 출력하는 것으로 대신합니다. 방문 순서를 보면 먼저 현재 노드를 방문하고 왼쪽 서브 트리에 대해 다시 preorder를 호출함으로써 왼쪽 서브 트리의 모든 노드를 방문합니다. 이후 오른쪽 서브 트리에 대해 preorder를 호출해서 오른쪽 서브 트리를 모두 순회하면 되지요.