[자료구조] 전위 순회와 후위 순회를 알 때의 트리

전위 순회와 후위 순회의 결과가 주어질 때 트리를 구하고, 이 트리를 통해 중위 순회도 구현할 수 있다.

---

원리

위와 같은 트리가 주어졌을 때 전위 순회와 후위 순회의 결과는 다음과 같다.

• 전위 순회 : 1 2 4 8 9 5 10 11 3 6 7
• 후위 순회 : 8 9 4 10 11 5 2 6 7 3 1

이때 전위 순회의 첫 번째 숫자와 후위 순회의 마지막 숫자가 루트 노드라는 것을 알 수 있다. (전위 순회는 루트 노드를 먼저, 후위 순회는 루트 노드를 마지막으로 방문하기 때문이다.)

 

그 다음 전위 순회의 두 번째 숫자는 루트 노드의 왼쪽 자식 노드가 될 것이고, 후위 순회에서 마지막에서 두 번째 노드는 루트 노드의 오른쪽 자식 노드가 될 것이다. 이때 두 번째 숫자인 2를 후위 순회에서 찾아보면 8부터 2까지는 루트 노드의 왼쪽 서브트리가 되는 것을 알 수 있다.

 

이후 루트 노드의 왼쪽 서브트리에 진입하고, 4가 왼쪽 서브트리의 루트 노드가 되는 것을 알 수 있다. 이와 같은 방법으로 트리를 완성시켜 나가게 되는데 정리를 해보면 다음과 같다.

• 전위 순회의 첫 번째, 후위 순회의 마지막 노드는 동일하며 루트 노드가 된다.
• 전위 순회에서 루트 노드 다음의 노드는 왼쪽 자식 노드, 후위 순회에서 루트 노드 이전 노드는 오른쪽 자식 노드가 된다.
• 후위 순회에서 루트 노드의 왼쪽 자식 노드를 포함한 이전 노드는 왼쪽 서브트리가 되며 그 이후부터 루트 마지막 전까지는 오른쪽 서브트리가 된다.

---

코드로 구현하기

위의 규칙으로 코드로 구현해보자.

makeTree를 통해 트리를 만들었으며 in_order 함수를 통해 중위 순회의 결과를 출력하였다.

N = 11

def makeTree(node):
    current = pre_order[node]
    visited[current] = True
    flag = 1

    # current 노드의 왼쪽 자식 노드를 찾기위해
    # 전위 순회에서 node의 다음 노드와 같아지는 지점을 찾는다.
    if node + 1 > N:
        return
    while flag <= N and post_order[flag] != pre_order[node + 1]:
        flag += 1

    if flag > N:
        return

    # post_order[flag]에는 왼쪽 자식 노드가 있음.
    # 왼쪽 자식 노드의 부모 노드를 현재 방문한 노드로 설정
    # 현재 방문한 노드의 왼쪽 자식 노드를 post_order[flag]로 설정
    if tree[post_order[flag]][1] == -1:
        tree[current][0] = post_order[flag]
        tree[post_order[flag]][1] = current

    # current 노드의 오른쪽 자식 노드를 찾기 위해
    # post_order에서 현재 current 노드를 찾는다.
    # 이후 flag - 1을 오른쪽 자식 노드로 설정한다.
    while flag <= N and post_order[flag] != pre_order[node]:
        flag += 1

    if flag > N:
        return

    # post_order[flag-1]에는 current 노드의 오른쪽 자식노드가 있음.
    if tree[post_order[flag - 1]][1] == -1:
        tree[current][2] = post_order[flag - 1]
        tree[post_order[flag - 1]][1] = current

    # 처음 위의 과정을 거치게 되면 루트 노드와 왼쪽 자식 노드, 오른쪽 자식 노드로
    # 3개의 노드가 완성이 될 수 있음

    # 이제 왼쪽 자식 노드를 루트 노드로 갖는 왼쪽 서브트리를 탐색하러 간다.
    # 전위 순회의 결과에서 현재 방문한 노드의 왼쪽 자식 노드를 찾고
    # 왼쪽 서브트리를 완성시키러 간다.
    for i in range(1, N+1):
        if pre_order[i] == tree[current][0]:
            makeTree(i)

    # 현재 방문한 노드의 오른쪽 자식 노드를 찾고
    # 오른쪽 서브트리를 완성시키러 간다.
    for i in range(1, N+1):
        if pre_order[i] == tree[current][2]:
            makeTree(i)

def in_order(node):
    if tree[node][0] != -1:
        in_order(tree[node][0])
    print(node)
    if tree[node][2] != -1:
        in_order(tree[node][2])

pre_order = [-1, 1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 7]
post_order = [-1, 8, 9, 4, 10, 11, 5, 2, 6, 7, 3, 1]

tree = [[-1, -1, -1] for _ in range(N + 1)] # 0-왼쪽자식노드, 1-부모노드 2-오른쪽자식노드
visited = [False] * (N + 1)

makeTree(1)
in_order(1)