트리순회 ( Tree - travalsal )

트리순회는 트리 구조를 탐색하거나 처리할 때, 가장 기본이 되는 알고리즘인데요.

트리를 순회한다는 것은

트리의 모든 노드를 특정한 순서로 한번 씩 방문하는 것

을 의미합니다.

트리순회를 공부하는 것만으로

• 재귀함수의 호출과정에 대해 좀 더 이해할 수 있게되고,
• DFS(깊이우선탐색)나 BFS(너비우선탐색) 을 사용하는데 있어서 기본이 되니까

알고있으면 좋겠죠~?

트리순회의 종류

트리 순회의 종류에는 기본적으로 3가지가 있습니다.

1. 전위순회( pre-order )
2. 중위순회( in-order )
3. 후위순회( post-order )

각각 노드를 방문하는 순서에 따라 다른데요.

이 네가지를 예시와 함께 살펴보겠습니다.

우리가 사용할 트리는

        A
      /   \
     B     C
    / \   / \
   D   E F   G

이거예용 지피티쨩 아리가또네~

전위순회,중위순회,후위순회 모두 사용될 기본 python treenode 클래스에요

class treeNode:
    def __init__(self,val):
        self.val = val
        self.left = None
        self.right = None

전위순회 ( pre-order )

전위순회는 루트 -> 왼쪽 -> 오른쪽 순서대로 방문해요.

위에있는 트리기준으로는

A → B → D → E → C → F → G

가 될거예요.

코드로는 이렇게 됩니다.

def preorder(node):
    if node is None:
        return
    print(node.value)     # 루트 처리
    preorder(node.left)   # 왼쪽 자식
    preorder(node.right)  # 오른쪽 자식

루트 > 왼쪽 > 오른쪽 이기 때문에

root 인 현재를 print 문에 찍어줘요.

그리고나서 왼쪽을 호출하고 오른쪽을 호출합니다.

A -> B -> D 가 순서대로 출력되는이유도 B,D 가 모두 트리구조에서는 자기자신이 루트이기 때문이예요.

중위순회 ( in-order )

중위순회는 왼쪽 -> 루트 -> 오른쪽 순으로 진행됩니다.

위에 있는 트리 기준으로는

D → B → E → A → F → C → G

이렇게 될거예요.

코드로는 이렇게 됩니다.

def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(node.value)
    inorder(node.right)

전위순회와 거의 비슷하지만 print 문이 가운데 찍혀있는 점이 보이네요.

왼쪽 먼저방문하고 루트를 찍고 오른쪽을 방문하기 때문에

left 와 right 중간에 print 가 찍혀있습니다. inorder 를 모두 돌고나서일거예요.

그래서 D -> B -> E 순서대로 찍히는거예요.

후위순회 ( post-order )

후위순회는 왼쪽 -> 오른쪽 -> 루트 순서대로 진행됩니다.

이정도면 이제 감온다 ㅇㅈ ?? ㅋㅋㅋㅋㅋ

D → E → B → F → G → C → A

코드로는

def postorder(node):
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.value)

인데요. 왼쪽 방문하고 오른쪽 방문하고 마지막에 print 가 찍혀있네요.

루트를 가장 마지막에 방문하기 때문입니다.

순회를 아는 것은 왜 중요할까?

모든 순회 코드를 보고나니까 재귀함수의 호출과정에 대해 뭔가 이해가 가지 않나요?

트리 전체를 잘게 쪼개서

작은 트리로 만들어서 문제를 해결하는..

실제로 코드상에도 함수호출순서를 바꿔주는 것 외에는 달라지는 게 없습니다.

그리고 그래프 문제를 풀 때 이런 호출과정을 이해하고 있는게 도움이 됩니다.

( 물론 아직 안풀어봄 ㅋㅋㅋ 아 ㅋㅋㅋ )

앞으로 더 깊은 알고리즘을 공부하기에 앞서 트리순회과정을 이해하고 있는것은 좋습니다.

자매품으로 입력받은 값으로 트리를 만드는 것도 연습해보세요.

그럼 모두 하이팅