이진트리 Binary Tree 순회 방법 중위 순회 InOrder Traversal, 전위 순회 PreOrder Traversal, 후위 순회 PostOrder Traversal

Binary Tree란?

Binary Tree는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조이다. 이 Binary Tree를 재귀적으로 정의할 수 있는데 오늘은 그것을 살펴보려고 한다. 

 

Binary Tree 재귀적으로 정의 

• Base case : 트리가 비어 있거나 노드가 하나도 없는 상태 일 때
• 재귀 : 하나의 루트 노드가 있으며, 그 루투 노드에 왼쪽과 오른쪽에 각각 서브 트리가 있다. 이 서브 트리 또한 이진 트리이다. 

 

 

이진 트리의 구조

 

이진 트리는 노드, 루트노드, 서브트리 3가지로 구성되어 있다. 

• 노드 : 데이터를 저장하는 기본 단위이다. 
• 루트 노드 : 드리의 가장 상단에 있는 노드이다. 
• 왼쪽 서브트리 와 오른쪽 서브트리 : 각각의 노드가 최대 두 개의 자식 노드를 가질 수 있으며, 이를 왼쪽과 오른쪽으로 나눈다. 

 

 

이진 트리의 순회 방법 

 

이진 트리의 순회 방법에는 여러가지가 있는데 대표적으로 중위 순회(InOrder Traversal), 전위 순회(PreOrder Traversal), 후위 순회(PostOrder Traversal)가 있다. 

 

1. InOrder Traversal

왼쪽 서브트리를 먼저 방문, 루트 노드를 방문, 그다음 오른쪽 서브트리를 방문하는 방식이다. 

 

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

    def in_order(root):
        if root is None:
            return
        in_order(root.left)
        print(root.data, end=' ')
        in_order(root.right)

 

 

2. PreOrder Traversal

루트 노드를 먼저 방문, 그다음 왼쪽 서브트리, 마지막으로 오른쪽 서브트리를 방문한다. 

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

    def pre_order(root):
        if root is None:
            return
        print(root.data, end=' ')
        pre_order(root.left)
        pre_order(root.right)

 

 

3. PostOrder Traversal

왼쪽 서브트리와 오른쪽 서브트리를 먼저 방문한 후, 루트 노드를 방문한다. 

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        
    def post_order(root):
    	if root is None:
            return
        post_order(root.left)
        post_order(root.right)
        print(root.data, end=' ')

 

이진 트리의 높이 

이진 트리의 높이는 트리에서 가장 긴 경로를 따라 루트에서부터 리프(leaf)까지의 노드 수를 말한다. 이를 재귀적으로 계산하면 다음과 같다. 

def height(root):
    if root is None:
        return 0
    return 1 + max(height(root.left), height(root.right))

 

 

이외에도 이진트리를 사용한 다양한 알고리즘 문제들이 있지만 기본적인 이진트리의 순회방법만 알고 있으면 그다지 어렵지 않다. 아래에는 대략 어떤 문제가 있는지 남겨 두겠다.

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

# 이진 트리의 크기 계산
def size(root):
    if root is None:
        return 0
    return 1 + size(root.left) + size(root.right)

# 이진 트리의 거울 만들기
def mirror(root):
    if root is None:
        return
    root.left, root.right = root.right, root.left
    mirror(root.left)
    mirror(root.right)

# 이진 트리의 삽입
def insert(root, data):
    if root is None:
        return Node(data)
    
    if data < root.data:
        root.left = insert(root.left, data)
    else:
        root.right = insert(root.right, data)
    
    return root

# 이진 트리의 메모리 해제 (파이썬은 자동 메모리 관리이므로 추가 작업 필요 없음)
def destruct(root):
    if root is None:
        return
    destruct(root.left)
    destruct(root.right)
    root = None

# 트리의 가중치 합
def sum_of_weights(root):
    if root is None:
        return 0
    return sum_of_weights(root.left) + sum_of_weights(root.right) + root.data

# 최대 경로 가중치 계산
def max_path_weight(root):
    if root is None:
        return 0
    left_weight = max_path_weight(root.left)
    right_weight = max_path_weight(root.right)
    return root.data + max(left_weight, right_weight)

# 예시 트리 생성
root = Node(6)
root = insert(root, 2)
root = insert(root, 1)
root = insert(root, 4)
root = insert(root, 3)
root = insert(root, 9)
root = insert(root, 7)

# 크기 계산
print("Size of tree:", size(root))

# 가중치 합 계산
print("Sum of weights:", sum_of_weights(root))

# 최대 경로 가중치 계산
print("Max path weight:", max_path_weight(root))

# 거울 변환 후 크기 다시 계산
mirror(root)
print("Size of tree after mirroring:", size(root))

 

• 크기 계산(size): 트리의 모든 노드 개수를 구한다.
• 거울 변환(mirror): 트리의 왼쪽과 오른쪽 서브트리를 교환하여 거울 트리를 만든다.
• 노드 삽입(insert): 이진 탐색 트리(BST)에 새 노드를 추가한다.
• 트리의 가중치 합(sum of weights): 트리의 모든 가중치 값을 합산한다.
• 최대 경로 가중치(max path weight): 루트에서 리프까지의 경로 중 가중치가 가장 큰 경로를 찾는다.