Data structures (with python) - 8.Tree - 8.1 Binary Tree

Data structures (with python) - 8.Tree - 8.1 Binary Tree

 

Tree

💡 A tree is non-linear and a hierarchical data structure consisting of a collection of nodes such that each node of the tree stores a value and a list of references to other nodes (the “children”).

트리는 비선형적이며 노드 모음으로 구성된 계층적 데이터 구조로, 트리의 각 노드가 값과 다른 노드에 대한 참조 목록('자식')을 저장합니다.

 

Binary Tree

💡 A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

이진 트리는 각 노드에 최대 두 개의 자식이 있는 트리 데이터 구조로, 왼쪽 자식과 오른쪽 자식이라고 합니다.

 

위키피디아

 

이진트리(binary tree)는 각 노드가 최대 두개의 자식 노드를 가지는 트리형태의 자료 구조입니다.

이진 트리의 각 노드는 '왼쪽', '오른쪽' 자식노드를 가질수 있으며, 이들은 부모 노드를 참조합니다.

 

특히 이진 검색트리(Binary Search Tree, BST, 바로 다음장에서 다룸), 힙(heap), 트라이(Trie) 등 많은 자료구조의 기반이 된다.

트라이(Trie)

이러한 자료구조들은 데이터 정렬, 검색, 우선순위 큐 등 다양한 문제를 효괒거으로 해결하는데 사용된다.

 

In Python

이진트리를 파이썬에서 구현하려면 Node 클래스를 생성한다.

이 클래스는 노드의 값을 저장하는 'data' 필드와 왼/오른쪽 자식 노드를 참조하는 'left', 'right'필드를 가진다.

 

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

# 노드 생성
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

1을 루트 노드로 가지는 이진 트리를 생성 해 보았다.

이진 트리의 루트 노드는 1, 1의 자식노드는 2와 3, 2의 자식노드는 4와 5이다.

 

활용

이진 트리를 활용한 알고리즘에는 대표적으로 트리 순회 (Tree Traversal)가 있다.

노드를 방문하는 순서에 따라 전위 순회(Pre-order), 중위 순회(In-order), 후위 순회(Post-order)로 나뉜다.

 

전위 순회는 노드를 방문하고, 그 노드의 왼쪽 서브트리, 오른쪽 서브트리 순서로 순회한다.

중위 순회는 왼쪽, 노드, 오른쪽 순서로 순회

후위 순회는 왼쪽, 오른쪽, 노드 순서로 방문한다.

 

이진 트리의 순회는 재귀적으로 구현할 수 있다.

왜? => 이는 각 노드에서 동일한 연산을 수행하기 떄문이다.

각 트리순회의 방법을 파이썬에서 구현해 봅니다.

# 전위 순회
def pre_order(node):
    if node is not None:
        print(node.data, end=' ')
        pre_order(node.left)
        pre_order(node.right)

# 중위 순회
def in_order(node):
    if node is not None:
        in_order(node.left)
        print(node.data, end=' ')
        in_order(node.right)

# 후위 순회
def post_order(node):
    if node is not None:
        post_order(node.left)
        post_order(node.right)
        print(node.data, end=' ')

 

위 함수들은 전위, 중위, 후위 순회를 수행하고 이진 트리의 노드 값을 출력합니다.