[Python] 트리 구현 / 순회(전위 순회, 중위 순회, 후위 순회, 레벨 순회)

이진 탐색 트리를 구현하기에 앞서 기본적인 트리의 구현을 해보려 한다.

오늘 구현할 트리는 별도의 기능을 갖지 않고 트리의 순회를 중점적으로 보려 한다.

순회란 트리를 돌면서 어떤 원소가 있는지 확인하는 작업을 말한다.

이 때 어느 원소를 먼저 보는지에 따라 순회의 종류가 달라진다.

트리의 순회는 재귀 방법으로 쉽게 구현할 수 있다.

 

위의 트리를 코드로 구현해 보자

 

1. 트리의 구조

class Node(object):
    def __init__(self, item):
        self.item = item
        self.left = self.right = None
        
class BinaryTree(object):
    def __init__(self):
        self.root = None

- Node class에서 item원소는 루트(노드)가 갖는 값을 저장하는 변수

- left와 right는 각각 루트의 자식 노드를 가리킨다

- BinaryTree class는 빈 root만을 갖고 Node원소로 초기화 시켜준다

 

2. 전위순회

- 전위 순회는 자식 노드를 확인하기 전에 서브 트리의 루트를 먼저 확인한 후에 자식 노드를 확인하는 순회 방법이다.

- 자식 노드를 확인할 때는 왼쪽 노드부터 확인한다.

전위 순회의 구현

def preorder(self):
        def _preorder(node):
            print(node.item, end=' ')
            if node.left:
                _preorder(node.left)
            if node.right:
                _preorder(node.right)
        _preorder(self.root)

3. 중위순회

- 중위순회는 왼쪽 자식 노드, 루트 노드, 오른쪽 자식 노드 순으로 값을 확인하는 방식이다.

- 자식 노드를 확인하고 밑에 자손 노드들이 있다면 자손 노드들도 동일한 방식으로 확인한다.

중위 순회의 구현

def inorder(self):
    def _inorder(node):
        if node.left:
            _inorder(node.left)
        print(node.item, end=' ')
        if node.right:
            _inorder(node.right)
    _inorder(self.root)

4. 후위 순회

- 후위 순회는 자식 노드를 모두 확인한 후에 루트 노드를 확인하는 순회 방법이다.

- 자식 노드의 자손 노드가 존재한다면 동일한 방식으로 모두 확인한다.

후위 순회의 구현

def postorder(self):
    def _postorder(node):
        if node.left:
            _postorder(node.left)
        if node.right:
            _postorder(node.right)
        print(node.item, end=' ')
    _postorder(self.root)

5. 레벨 순회

- 레벨 순회는 각 레벨마다의 노드를 탐색하는 방법이다.

- 큐를 이용해 구현할 수 있다.

from collections import deque

def levelorder(self):
    q = deque([self.root])
    while q:
        node = q.popleft()
        print(node.item, end=' ')
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

 

---

전체 코드

from collections import deque

class Node(object):
    def __init__(self, item):
        self.item = item
        self.left = self.right = None
        
class BinaryTree(object):
    def __init__(self):
        self.root = None
    
    def preorder(self):
        def _preorder(node):
            print(node.item, end=' ')
            if node.left:
                _preorder(node.left)
            if node.right:
                _preorder(node.right)
        _preorder(self.root)
    
    def inorder(self):
        def _inorder(node):
            if node.left:
                _inorder(node.left)
            print(node.item, end=' ')
            if node.right:
                _inorder(node.right)
        _inorder(self.root)
    
    def postorder(self):
        def _postorder(node):
            if node.left:
                _postorder(node.left)
            if node.right:
                _postorder(node.right)
            print(node.item, end=' ')
        _postorder(self.root)
        
    def levelorder(self):
        q = deque([self.root])
        while q:
            node = q.popleft()
            print(node.item, end=' ')
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)

BT = BinaryTree()
N1 = Node(1)
N2 = Node(2)
N3 = Node(3)
N4 = Node(4)
N5 = Node(5)
N6 = Node(6)
N7 = Node(7)
N8 = Node(8)

BT.root = N1
N1.left = N2
N1.right = N3
N2.left = N4
N2.right = N5
N3.left = N6
N3.right = N7
N4.left = N8

print('preorder')
BT.preorder()

print('\ninorder')
BT.inorder()

print('\npostorder')
BT.postorder()

print('\nlevelorder')
BT.levelorder()