• 전위 순회(preorder traversal): 이 방법은 현재 노드를 먼저 방문하고, 그다음은 현재 노드의 왼쪽 하위 노드를, 마지막으로는 현재 노드의 오른쪽 하위 노드를 재귀적인 방식으로 방문합니다. 여기서 ‘전위(pre)’는 상위 노드를 하위 노드보다 먼저 방문한다는 뜻입니다. 그림 2-4의 트리를 전위 순회 방식으로 탐색하면 다음과 같습니다.

CEO, 부사장, IT부장, 보안팀장, 앱개발팀장, 마케팅부장, 물류팀장, 홍보팀장

전위 순회는 항상 부모 노드를 방문한 다음 왼쪽 자식 노드, 오른쪽 자식 노드를 차례로 방문합니다. 이러한 방식의 순회를 루트 노드에서만 수행하는 것이 아니라 루트 노드 아래의 모든 서브 트리에 대해 적용합니다. 전위 순회는 다음과 같이 구현할 수 있습니다.

static void preOrder(node* start)
{
    if (!start)
        return;

    std::cout << start->position << ", ";
    preOrder(start->first);
    preOrder(start->second);
}