Traverse(Node *D) {
    if(D == NULL) return;
    Visit(D);  // Preorder Traversal
    Traverse(D->Left);
    Visit(D);  // Inorder Traversal
    Traverse(D->Right);
    Visit(D);  // Postorder Traversal
}

• Preorder Traversal : 왼쪽 서브트리를 방문하기 전에 해당 노드를 방문
• Inorder Traversal : 왼쪽 서브트리를 방문한 뒤, 오른쪽 서브트리를 방문하기 전 해당 노드를 방문
• Postorder Traversal : 오른쪽 서브트리를 방문한 뒤 해당 노드를 방문

• Preorder : 6, 4, 2, 1, 3, 5, 8, 7, 9
• Inorder : 1, 2, 3, 4, 5, 6, 7, 8, 9
• Postorder : 1, 3, 2, 5, 4, 7, 9, 8, 6

1. Preorder 배열에서 루트 노드를 찾는다. 첫 번째 원소가 루트 노드이다.
2. Inorder 배열에서 해당 루트 노드를 찾는다. 만약 찾지 못하면 false를 리턴한다.
3. Inorder 배열의 k번째 원소가 루트 노드라면, 아래와 같이 왼쪽, 오른쪽 서브트리에 대해 재귀 수행한다.
• Preorder의 1번째 원소 다음 k-1개 원소, Inorder의 왼쪽 k-1개 원소에 대해 재귀 수행
• 루트와 왼쪽 서브트리 원소들을 제외한, Preorder와 Inorder의 나머지 원소들에 대해 재귀 수행
• 다음과 같은 예제에서
• Preorder : 6, 4, 2, 1, 3, 5, 8, 7, 9
• Inorder : 1, 2, 3, 4, 5, 6, 7, 8, 9
• 초록색으로 표시된 왼쪽 서브트리와 파란색으로 표시된 오른쪽 서브트리에 대해 재귀 수행된다.
• 재귀 수행 시 Preorder의 남은 원소 개수가 부족해지면 false 리턴
4. 재귀 수행이 둘 다 true를 리턴하면 true 리턴

컴파일러에서 Tree의 응용

Parsing

• 가정
• 연산자마다 우선순위가 있다.
• 우선순위가 같은 연산자는 왼쪽에 있는 것이 먼저 계산된다고 하자.
• 중위 표현식의 처음과 끝을 $로 표시한다.
• ex) $ a + b * c $
• $는 우선순위가 가장 낮은 연산자이다.

parsing 알고리즘에서는 두 개의 스택이 사용된다. 1번 스택은 연산자를 저장하는 스택이며, 2번 스택은 피연산자나 표현식 트리를 저장하는 스택이다.

1번 스택에서 연산자 노드가 pop될 때마다 2번 스택의 노드 2개가 pop되어 자식으로 들어간다. 여기서 표현식 트리가 형성되며, 해당 트리에 후위 순회를 함으로써 연산 결과값이 산출된다. 따라서 해당 트리를 하나의 연산 결과값으로 해석할 수 있다.

(위 그림과 같은 트리를 6 / 3 + 5 의 결과값인 7로 해석할 수 있음)

그러므로 트리를 만드는 과정은 1번 스택의 연산자와 2번 스택의 값에 대해 연산을 수행하는 것으로 볼 수 있다.

여기서 중요한 것은 1번 스택에서 우선순위가 더 높은 연산자, 수식에서 더 왼쪽에 있는 연산자가 먼저 pop되도록 하는 것, 즉 먼저 연산되도록 하는 것이다.

괄호가 있는 경우 Parsing