트리 순회(tree traversal) 알고리즘, 비전공자 문돌이가 설명하는 파이썬 기본 문법 (9)

1. K-ary Trees란?

지금까지 저희가 살펴본 트리 구조는 이진(binary) 트리였습니다. K-ary 트리는 가지가 3개가 될 수도 있고, 4개가 될 수도 있는 구조입니다. 

2. 트리 순회(Traversal)란?

트리를 순회하는, 쉽게 말해 돌아다니는 방법은 몇 가지가 있을까요? 대표적으로 왼쪽에서 오른쪽으로, 위에서 아래로 순차적으로 돌아다니는 방법이 있겠죠. 이외에도 몇 가지 방법을 소개하겠습니다.

Level-order(Breadth-first) Traversal: 위에서 아래, 왼쪽에서 오른쪽 

위의 그림에서 노란색 원이 나타내는 것이 바로 순회 순서입니다. 결론부터 말하면 Level-order Traversal은 FIFO(first in, first out) 큐 구조입니다. 위에서 아래로 훑으면서, 같은 층에 여러 노드가 있다면 왼쪽에서 오른쪽으로 훑는 것입니다. 코드를 통해 좀 더 자세히 살펴보겠습니다.

완전한 코드가 아닌 이해를 돕기 위한 pseudo code로 생각하면 좋을 듯 합니다

class Tree():
    def visit(self, node: TreeNode):
        print(node.val)
    
    def BFT(self):
        if self.root == None:
            return
        q = [self.root]
        while q:
            curNode = q.pop(0)
            self.visit(curNode)
            for childNode in curNode.child:
                if childNode:
                    q.append(childNode)

아래 그림은 위 코드의 실행 과정을 표현한 것입니다. while loop에서 첫 실행, 두 번째 실행, 세 번째 실행나타낸 것이며 로직을 쉽게 이해할 수 있을 겁니다. 

<The first while loop>

<The second while loop>

<The third while loop>

q가 empty list가 되면 while loop을 탈출하게 됩니다. 참고로 deque()와 popleft() 메서드를 사용하면 노드 추가 및 삭제가 더 빠르다고 합니다. pop(0)의 경우 시간 복잡도가 $O(N)$이기 때문에 스택과 큐를 합친 구조인 deque를 사용하여 가장자리에 원소를 추가하거나 가장자리에 있는 원소를 제거합니다. 

list.pop()의 시간 복잡도: $O(1)$
pop()은 뒤에서부터 원소를 제거한다

from collections import deque

class Tree():
    def visit(self, node: TreeNode):
        print(node.val)
    
    def BFT(self):
        if self.root == None:
            return
        q = deque([self.root]) # deque 사용
        while q:
            curNode = q.popleft() # popleft 사용
            self.visit(curNode)
            for childNode in curNode.child:
                if childNode:
                    q.append(childNode)

Depth First Traversals: 3가지 타입 골라쓰기(Preorder, Inorder, Postorder)

1. 전위순회(Preorder): 일단 위에서 아래로, 이후 왼쪽부터 차근차근

Preorder는 왼쪽이 가장 중요합니다. 위에서 아래로 진행하는 것은 맞지만, 2개의 자식 노드 중 오른쪽 자식 노드보단 왼쪽 자식 노드의 자식 노드, 즉 손자 노드부터 순회합니다. 그림으로 설명하는 것이 훨씬 좋을 듯 합니다.

Level-order Traversal에서는 한 층에 도착하면 그 층에 있는 모든 자식 노드들을 우선적으로 순회했습니다. 따라서 노드 2에 도착하면 그 다음이 노드6 였죠. 하지만 Preorder는 일단 왼쪽부터 찍고 보는 스타일입니다.

class Tree():
    def visit(self, node: TreeNode):
        print(node.val)
    
    def __DFT_preorderHelp(curNode: TreeNode):
        if curNode == None:
            return
        self.visit(curNode)
        
        for childNode in curNode.child:
            self.__DFT_preorderHelp(childNode)
            
    def DFT_preorder(self):
        self.__DFT_preorderHelp(self.root)

또 다시 재귀 구조입니다. 코드로만 이해하기 어려우신 분은 아래 그림을 참고해주세요.

2. 중위순회(Inorder): 아예 왼쪽부터 시작, 중간에 들리기

Inorder은 일단 가장 아래에 위치한 왼쪽 노드부터 시작하며, 일단 목표는 같은 층의 맨 오른쪽 노드로 가는 것입니다. 하지만 오른쪽 노드에게 가는 그 과정에서 부모 혹은 조부모 노드가 있다면 무조건 들렸다 가야 합니다. 마찬가지로 그림으로 설명하겠습니다. 

노드1에서 노드3으로 가는데, 그 중간에 부모가 있기 때문에 부모를 먼저 들렸다 갑니다. 노드3에서 노드5로 가야 하는데, 조부모가 있기 때문에 또 한 번 들립니다. 노드5에서 노드7로 가려니 부모 노드가 또 있습니다. 이렇게 바로 같은 층 노드로 이동해야 하는데, 그 사이에 어떤 노드가 있다면 해당 노드를 먼저 들린 후 다시 들리게 됩니다. 

class Tree():
    def visit(self, node: TreeNode):
        print(node.val)
    
    def __DFT_inorderHelp(curNode: TreeNode):
        if curNode == None:
            return
            
        if not curNode.child:
            self.visit(curNode)
            
        for i in range(len(curNode.child)):
            if i == 1:
                self.visit(curNode)
            self.__DFT_inorderHelp(curNode.child[i])
            
    def DFT_inorder(self):
        self.__DFT_inorderHelp(self.root)

마찬가지로 재귀 구조이며, 위의 Preorder를 참고하시면 비교적 쉽게 이해할 수 있을 것입니다. for 문 내부 i == 0 부분에서 self.__DFT_inorderHelp(curNode.child[0]) 부분이 위 그림의 노드1로 내려가게 됩니다. i == 0일 때 걸리는 과정이 길어지는 것이죠. i == 1 이 될 때, 비로소 root 노드인 4가 출력되고 self.__DFT_inorderHelp(curNode.child[1]) 이 시작되는 것입니다. 

3. 후위순회(Postorder): 자식부터 먼저

Postorder은 자식 노드를 우선적으로 출력하는 방법입니다. 자식 노드를 다 거치고 나서 그 부모 노드를 출력하는데요, 그림을 보시면 이해가 될 것입니다. 

자식 노드를 먼저 순회하고, 직접적으로 연결된 부모 노드를 들렸다가, 다시 자식 노드가 있는 층으로 돌아갑니다. 부모 노드는 자식 노드가 모든 여행을 마치고 돌아올 때까지 기다리는 것이죠. root 노드인 노드4의 경우, 자식 노드인 노드2와 노드6 이후에야 출력됩니다. 

class Tree():
    def visit(self, node: TreeNode):
        print(node.val)
    
    def __DFT_postorderHelp(curNode: TreeNode):
        if curNode == None:
            return
            
        for i in range(len(curNode.child)):
            self.__DFT_inorderHelp(curNode.child[i])
        self.visit(curNode)
        
    def DFT_postorder(self):
        self.__DFT_postorderHelp(self.root)

트리 구조 형태의 데이터는 우리에게 가장 직관적이고, 시각화를 하는 데도 편리합니다. 오직 성능만 따진다면 hash table을 사용한 search가 유리하겠지만, 우리가 폴더 및 파일을 찾을 때 cmd에서 명령어를 쳐서 찾진 않죠. GUI를 통해 어느 폴더에 어느 파일이 있는지 순회를 하고 싶은 겁니다. 이때는 트리 구조가 훨씬 도움이 됩니다.