107. Inorder Traversal

트리의 중위 순회(Inorder Traversal)는 노드의 왼쪽 서브트리를 먼저 방문한 다음 노드를 방문하고 노드의 오른쪽 서브트리들을 방문하는 순회 방법이다. 여기서 서브트리의 방향에 대한 내용이 등장하는데 이 방향은 단순히 트리의 구조를 나타내었을 때의 방향이라고 생각해도 무방하다. 만약 자식 노드가 $3$개 이상일 경우 서브트리들 중 하나를 왼쪽 서브트리로, 나머지를 오른쪽 서브트리로 간주한다. 하지만 그런 노드가 있는 트리에서는 서브트리의 방향이 별로 의미 없는 경우가 많기 때문에 일반적으로 중위 순회는 이진 트리에서 수행된다.

 

앞에서 설명한 트리의 중위 순회 결과는 다음과 같다.

$\text{I G B F D A E J C H}$

 

구현은 다음과 같다.

// 인접 리스트를 사용한 경우

#import<bits/stdc++.h>
using namespace std;
vector<int>v, e[100005];
void inorder_traversal(int prev, int node)
{
    int c = 0;
    for(auto &p: e[node])
    {
        if(p != prev)
        {
            inorder_traversal(p);
            c++;
        }
        if(c == 1)v.push_back(node);
    }
}
int main()
{
    int n, root, x, y;
    cin >> n >> root;
    for(int i = 0; i < n - 1; i++)
    {
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    inorder_traversal(0, root);
}

// 1번이 루트 노드이고 나머지 노드들의 부모 노드들이 주어진 경우

#import<bits/stdc++.h>
using namespace std;
vector<int>v, e[100005];
void inorder_traversal(int node)
{
    int c = 0;
    for(auto &p: e[node])
    {
        inorder_traversal(p);
        c++;
        if(c == 1)v.push_back(node);
    }
}
int main()
{
    int n, x;
    cin >> n;
    for(int i = 2; i <= n; i++)
    {
        cin >> x;
        e[x].push_back(i);
    }
    inorder_traversal(1);
}

---

전위 순회와 마찬가지로 중위 순회도 식을 표현하는 데 쓸 수 있다. 이때 식을 표현하는 트리를 중위 순회한 결과를 중위 표기식(Infix Expression)이라고 하며 식을 이 방법으로 나타내는 것을 중위 표기법(Infix Notation)이라고 한다. 일반적으로 사용하는 산술식은 모두 중위 표기식이다.