파이썬으로 트리 순회 구현하기

 

다음은 위와 같은 구조의 이진 트리를 생성하고, 전위/중위/후위 순회를 수행하는 코드이다.

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None
    
    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
            return
        queue = [self.root]
        while queue:
            temp = queue.pop(0)
            if not temp.left:
                temp.left = Node(key)
                return
            else:
                queue.append(temp.left)
            if not temp.right:
                temp.right = Node(key)
                return
            else:
                queue.append(temp.right)
    
    def preorder_traversal(self, node, result=None):
        if result is None:
            result = []
        if node:
            result.append(node.key)
            self.preorder_traversal(node.left, result)
            self.preorder_traversal(node.right, result)
        return result
    
    def inorder_traversal(self, node, result=None):
        if result is None:
            result = []
        if node:
            self.inorder_traversal(node.left, result)
            result.append(node.key)
            self.inorder_traversal(node.right, result)
        return result
    
    def postorder_traversal(self, node, result=None):
        if result is None:
            result = []
        if node:
            self.postorder_traversal(node.left, result)
            self.postorder_traversal(node.right, result)
            result.append(node.key)
        return result

bt = BinaryTree()
for i in range(1, 7):
    bt.insert(i)
    
print("전위 순회:", bt.preorder_traversal(bt.root))  # [1, 2, 4, 5, 3, 6]
print("중위 순회:", bt.inorder_traversal(bt.root))   # [4, 2, 5, 1, 3, 6]
print("후위 순회:", bt.postorder_traversal(bt.root)) # [4, 5, 2, 6, 3, 1]