[자료구조] Tree Traversal and Parsing

• 본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다.
• 따라서 완벽하지 않은 부분이 있을 수 있습니다.
• 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다.

---

Traversal

• Traversal : 모든 노드를 특정 순서로 방문하는 것
• 여기서 '방문'이란 단순히 거치는 것을 넘어서 해당 노드에서 특정한 작업을 수행하는 것이다.

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
}

---

Pre/In/Post order

• Pre : 6,4,2,1,3,5,8,7,9
• In : 1,2,3,4,5,6,7,8,9 (크기 순서로대로 출력)
• Post : 1,3,2,5,4,7,9,8,6
• 이러한 결과를 토대로 Tree를 재구성하는 알고리즘을 짤 수도 있다.

---

Notation

• 위와 같이 수식을 트리로 표현할 수도 있다. 이 때 이를 어떻게 Traversal 하느냐에 따라 수식의 표현이 달라진다.
• Prefix Notation : * + / 6 3 5 - 6 4
• Infix Notation : 6 / 3 + 5 * 6 -4 (괄호 필요, 가장 일반적 수식)
• Postfix Notation : 6 3 / 5 + 6 4 - * (괄호 불필요)
• 즉, 수식에 Traversal을 적용하면 꽤 유의미한 결과를 뽑아낼 수 있다.

---

Parsing

• Pasrsing은 일반적 수식 혹은 숫자의 나열을 트리 형태로 변환하는 것이다. 이를 컴퓨터가 해당 수식을 이해했다고 표현할 수도 있다.
• 즉, ((A / B + C) * (A-D) + C)라는 식을 입력받아 이를 T1 = A / B, T2 = T1 + C, T3 = A - D, T4 = T2 * T4, T5 = T4 + C의 형태로 출력한다. (이는 트리의 관계와 매우 유사한 형태를 띄는 것을 알 수 있다.)
• Parsing Algorithm : 연산자에 우선 순위를 주고 동일한 우선순위일 경우 왼쪽의 연산자가 우선순위를 갖도록 한다.
• while 수식을 처음부터 끝까지 읽기 if 피연산자 then 노드만들고 push to 2nd stack // 피연산자 stack if 연산자 then 우선순위 비교 with top of 1st stack // 연산자 stack case 현 input이 우선순위 높음 : 1st stack에 넣기 case top of 1st stack이 우선순위 높음 : 2nd stack으로부터 2개 pop 1st stack의 top 연산자에 2nd stack에서 pop한 값 두개 자식으로 붙여서 새 노드 만듬 해당 노드 2nd stack에 push continue case $$ : 작업종료
• 여기에 괄호 개념을 추가하면
• 여는 괄호 : Input일때 가장 우선순위가 높고, stack 안에서는 가장 우선순위가 낮다
• 닫는 괄호 : 가장 낮은 우선순위를 가지며 stack으로 가지 않는다. (바로 처리, (와 )는 만나면 없어진다.)