[Coding Test][Python][CodeTree] Binary Tree 개념 및 구현

 

 

1. Binary Tree(이진 트리) 란?

Tree의 각 node가 최대 두 개의 자식(0개, 1개, 2개) Node를 가지는 Tree의 형태의 자료구조입니다.

위의 그림은 Binary Tree를 나타낸 그림입니다.

2. Binary Tree(이진 트리) 구현

Binary Tree는 구현이 간단하는 특징이 있습니다.

1) 배열을 이용한 Binary Tree 구현

Binary Tree는 자식 Node가 두개이기 때문에 하나는 왼쪽, 하나는 오른쪽에 존재합니다.

이 때, Root Node를 배열의 Index 1에 넣게 되면 왼쪽 자식 Node를 Index 2, 오른쪽 자식 Node를 Index 3에 넣어 주면 됩니다.

이러한 방식으로 Parent Node의 Index를 i라고 하면 왼쪽 자식 Node는 Index $2i$, 오른쪽 자식 Node는 Index $2i +1$에 위치하게 됩니다.

반대로 Parent Node의 Index를 구하기 위해서는 자식 Node의 Index i에서 $i // 2$를 통해 구할 수 있습니다.

아래 그림처럼 완전 이진 트리(Complete Binary Tree)가 아닌 경우에도 비어있는 Node에 대해서는 값을 비워둠으로써 Binary Tree를 구현할 수 있습니다.

2) Linked List를 이용한 Binary Tree 구현

배열로 구현하기도 하지만 Binary Tree를 주로 Linked List를 통해 구현합니다.

 

우선 Tree의 각 Node를 나타내는 Node Class를 정의합니다.

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

 

아래 코드는 Binary Tree를 나타냅니다.

Binary Tree를 생성하기 위해서는 삽입, 탐색 등 여러 Method를 정의해야합니다.

이는 아래에서 구현을 하도록 하겠습니다.

class BinaryTree:
    def __init__(self):
        self.root = None
        
    def insert(self, data):
    	pass
    
    def preorder(self, node):
        pass
    
    def inorder(self, node):
        pass
   
    def postorder(self, node):
        pass
        
    def levelorder(self, root):
    	pass

 

3. Binary Tree(이진 트리) 탐색(순회)

Binary Tree의 탐색은 DFS를 통해 탐색을 합니다. 따라서 Recursion을 통해 순회합니다.

Tree를 방문하는 순서는 크게 Preorder Traversal(전위 순회), Inorder Traversal(중위 순회), Postorder Traversal(후위 순회)가 있습니다. (BFS를 통한 Levelorder Traversal도 존재합니다.)

1) Preorder Traversal(전위 순회)

Parent Node -> Left Child -> Right Child 순으로 탐색하는 순회방법입니다.

모든 Node에 대해 Parent Node에 대해 먼저 방문한 후, 왼쪽 자식 Node들을 모두 순회하고, 그 이후 오른쪽 자식 Node를 순회합니다.

def preorder(node):
    if node:
        print(node.data, end=' ')
        preorder(node.left)
        preorder(node.right)

 

2) Inorder Traversal(중위 순회)

Left Child -> Parent Node -> Right Child 순으로 탐색하는 순회방법입니다.

모든 Node에 대해 왼쪽 자식 Node들을 모두 순회하고, Parent Node에 대해 방문한 후, 그 이후 오른쪽 자식 Node를 순회합니다.

def inorder(node):
    if node:
        inorder(node.left)
        print(node.data, end=' ')
        inorder(node.right)

3) Postorder Traversal(후위 순회)

Left Child -> Right Child ->  Parent Node 순으로 탐색하는 순회방법입니다.

모든 Node에 대해 왼쪽 자식 Node들을 모두 순회하고, 그 이후 오른쪽 자식 Node를 모두 순회한 뒤, 마지막으로 Parent Node를 방문합니다.

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.data, end=' ')

4) Level Order Traversal

Root에서 시작하여 상위 레벨에서 하위 레벨 순으로, 각 레벨에서는 왼쪽에서 오른쪽 방향으로 순회하는 방법입니다.

def level_order(root):
    if root is None:
        return
    
    q = deque()
    q.append(root)
    
    while q:
        curr = q.popleft()
        print(current.data, end=' ')
        
        if curr.left:
            q.append(current.left)
        if curr.right:
            q.append(current.right)

4. Binary Tree(이진 트리) Method 구현

1) Node 정의

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

2) Binary Tree 구현

from collections import deque
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None
   
    def insert(self, data):
        new_node = Node(data)
        if not self.root:
            self.root = new_node
            return

        q = deque([self.root])

        while q:
            curr = q.popleft()

            # 왼쪽 자식이 없으면 새 노드 삽입
            if not curr.left:
                curr.left = new_node
                return
            else:
                q.append(curr.left)

            # 오른쪽 자식이 없으면 새 노드 삽입
            if not curr.right:
                curr.right = new_node
                return
            else:
                q.append(curr.right)
                          
    def preorder(self, node):
        if node:
            print(node.data, end=' ')
            self.preorder(node.left)
            self.preorder(node.right)
    
    def inorder(self, node):
        if node:
            self.inorder(node.left)
            print(node.data, end=' ')
            self.inorder(node.right)
   
    def postorder(self, node):
        if node:
            self.postorder(node.left)
            self.postorder(node.right)
            print(node.data, end=' ')
        
    def level_order(root):
        if root is None:
            return

        q = deque()
        q.append(root)

        while q:
            curr = q.popleft()
            print(curr.data, end=' ')

            if curr.left:
                q.append(curr.left)
            if curr.right:
                q.append(curr.right)

3) 결과 확인

위 Tree를 순회한 결과입니다.

bt = BinaryTree()
bt.insert(5)
bt.insert(3)
bt.insert(6)
bt.insert(4)
bt.insert(7)
bt.insert(8)
bt.insert(9)

print("전위 순회 결과:")
bt.preorder(bt.root)
print()

print("중위 순회 결과:")
bt.inorder(bt.root)
print()

print("후위 순회 결과:")
bt.postorder(bt.root)

 

전위 순회 결과:
5 3 4 7 6 8 9
중위 순회 결과:
4 3 7 5 8 6 9
후위 순회 결과:
4 7 3 8 9 6 5

 

다음 글에서는 Binary Tree의 한 종류인 Binary Search Tree에 대해 적어보겠습니다.

 

출처) 코드트리 https://www.codetree.ai/landing