[자료구조] 트리의 표현과 순회

이번에는 트리를 Python으로 표현하는 것과 순회하는 방법에 대해 알아보도록 한다.

---

트리의 표현

Python 리스트를 통해 아래의 트리를 표현해보려고 한다.

아래의 코드를 보면 2차원 리스트를 생성한 것을 알 수 있는데 -1은 비어있음을 의미하고 각각 왼쪽 자식 노드와 오른쪽 자식 노드를 의미한다.

N = 6
tree = [[-1, -1] for _ in range(N)]

이제 각각의 노드에 왼쪽 자식 노드와 오른쪽 자식 노드를 입력받는다. 비어있을 때는 -1을 입력하도록 하였다. 각각 입력받은 것을 해당 노드의 0번 인덱스(왼쪽 자식 노드)와 1번 인덱스(오른쪽 자식 노드)에 저장한다.

for i in range(N):
    left, right = map(int, input().split())
    tree[i][0], tree[i][1] = left, right

for i in range(N):
    print("{} -> left : {}, right : {}".format(i, tree[i][0], tree[i][1]))

위의 과정에서 각 노드의 자식 노드들을 출력하면 다음과 같다.

0 -> left : 1, right : 2
1 -> left : 3, right : 4
2 -> left : -1, right : 5
3 -> left : -1, right : -1
4 -> left : -1, right : -1
5 -> left : -1, right : -1

 

트리의 순회

트리를 순회하는 방법에는 전위 순회, 중위 순회, 후위 순회가 존재한다. 각각의 이름은 부모 노드를 언제 방문하는지에 따라 정해진다. 

 

전위 순회

전위 순회는 부모 노드를 먼저 방문하여 부모 노드 -> 왼쪽 노드 -> 오른쪽 노드 순으로 방문한다. 이를 Python 코드로 작성하면 다음과 같다. 재귀 함수를 활용하였으며 print()로 node를 출력하는 부분이 부모 노드를 방문했다는 것을 의미한다. 

 

전위 순회처럼 부모 노드를 출력한 후에 왼쪽 노드와 오른쪽 노드를 순서대로 방문한다. 가장 먼저 루트 노드인 0부터 출발을 한다. 이후에 왼쪽 노드인 1을 방문한다면 1도 자식 노드를 갖고 있고 부모 노드가 된다. 그렇다면 여기서 다시 1의 왼쪽 자식 노드인 3을 방문 후에 더 이상 자식 노드를 갖고 있지 않다고 판단하여 1로 돌아온 후에 오른쪽 자식 노드인 4를 방문하게 된다.

 

결론적으로 0 -> 1 -> 3 -> 4 -> 2 -> 5 순으로 트리를 전위 순회하게 된다.

def pre_order(node):
    if node != -1:
        print(node, end=' ')
        pre_order(tree[node][0])
        pre_order(tree[node][1])

 

중위 순회

중위 순회는 부모 노드를 중간에 방문하여 왼쪽 노드 -> 부모 노드 -> 오른쪽 노드 순으로 방문한다. 아래와 같이 코드로 구현할 수 있다. 먼저 재귀적으로 맨 왼쪽의 노드인 3을 방문한다. 이후 3의 부모 노드인 1로 돌아와서 1을 방문하고 오른쪽 노드를 방문한다. 0의 왼쪽 서브 트리를 모두 방문한다면 0을 방문하고 이를 통해 왼쪽 노드 -> 루트 노드 순으로 방문하게 되었다. 이제 마지막으로 오른쪽 서브 트리를 방문하게 되는데 2의 왼쪽 노드는 없기 때문에 2 방문 후에 5를 방문하게 된다. 여기서 계속 방문했다는 것은 print()로 출력했다는 것을 의미한다.

결론적으로 3 -> 1 -> 4 -> 0 -> 2 -> 5 순으로 트리를 중위 순회하게 된다.

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

 

후위 순회

후위 순회는 부모 노드를 마지막으로 방문하여 왼쪽 노드 -> 오른쪽 노드 -> 부모 노드 순으로 방문한다. 아래와 같이 코드로 구현할 수 있다. 먼저 맨 아래의 왼쪽 노드인 3을 방문한 후에 1의 오른쪽 노드인 4를 방문 하고 1로 돌아와 1을 방문한다. 이렇게 왼쪽 서브 트리를 모두 방문하였고 이제 오른쪽 서브 트리로 이동한다. 2의 왼쪽 노드는 없기 때문에 5를 방문한 후에 2를 방문하면서 오른쪽 서브 트리를 모두 방문하였고 마지막으로 루트 노드인 0을 방문한다.

결론적으로 3 -> 4 -> 1 -> 5 -> 2 -> 0 순으로 트리를 후위 순회하게 된다.

def post_order(node):
    if node != -1:
        post_order(tree[node][0])
        post_order(tree[node][1])
        print(node, end=' ')