[자료구조] 트리, 이진트리 구현, 정이진트리, 완전이진트리 구현, 포화이진트리, 트리순회(pre, post, in-order) 구현

soyyeong·2023년 9월 17일

자료구조 코테스터디

알고리즘

목록 보기

9/20

트리란?

트리란, 데이터의 상-하 관계(계층적 관계)를 저장하는 자료구조이다.
트리에서 상위는 부모, 하위는 자식으로 부른다.
그중 가장 위에 해당하는 노드를 root 노드라고 부른다.

트리의 활용
- 계층적 관계가 있는 데이터를 컴퓨터에서 사용
- 컴퓨터 과학의 다양한 문제를 해결 (ex.정렬, 압축)
- 추상자료형을 구현하는 데에 사용 (ex.딕셔너리, 세트, 우선순위 큐)

이진트리

각 노드가 최대 2개의 자식 노드를 가질 수 있는 트리
2개 밖에 없기 때문에, 왼쪽 자식 & 오른쪽 자식으로 구별해서 부른다.

이진트리 구현

위와 같은 트리를 구현해보자.

class Node:
    """이진 트리 노드 클래스"""
    def __init__(self, data):
            self.data = data
            self.left_child = None
            self.right_child = None


# root 노드 생성
root_node = Node("A")
node_B = Node("B")
node_C = Node("C")
node_D = Node("D")
node_E = Node("E")
node_F = Node("F")
node_G = Node("G")
node_H = Node("H")

root_node.left_child = node_B
root_node.right_child = node_C

node_B.left_child = node_D
node_B.right_child = node_E

node_E.left_child = node_G
node_E.right_child = node_H

node_C.right_child = node_F

이진트리 종류

1. 정 이진 트리 (Full Binary Tree)

정 이진 트리(Full Binary Tree)는 모든 자식노드가 0개 또는 2개로만 이루어진 이진트리를 말한다.

2. 완전 이진 트리 (Complete Binary Tree)

이진 트리 중에서도 마지막 레벨 직전의 레벨까지는 모든 노드들이 다 채워진 트리를 “완전 이진 트리”라고 한다. 또, 마지막 레벨에서는 노드들이 다 채워질 필요는 없더라도, 왼쪽부터 오른쪽 방향으로는 노드들이 다 채워져야 한다.

아래는 완전 이진트리다.

아래는 완전 이진트리가 아닌 경우다.

완전 이진트리 구현

트리가 완전 이진 트리(complete binary tree)인 경우에 배열이나 파이썬 리스트로 구현한다.

def get_parent_index(complete_binary_tree, index):
    """배열로 구현한 완전 이진 트리에서 index번째 노드의 부모 노드의 인덱스를 리턴하는 함수"""
    # 여기에 코드를 작성하세요
    if index > 1:
        return index//2


def get_left_child_index(complete_binary_tree, index):
    """배열로 구현한 완전 이진 트리에서 index번째 노드의 왼쪽 자식 노드의 인덱스를 리턴하는 함수"""
    if len(complete_binary_tree) > index*2:
        return index*2


def get_right_child_index(complete_binary_tree, index):
    """배열로 구현한 완전 이진 트리에서 index번째 노드의 오른쪽 자식 노드의 인덱스를 리턴하는 함수"""
    if len(complete_binary_tree) > index*2+1:
        return index*2+1

# 테스트 코드
root_node_index = 1 # root 노드

tree = [None, 1, 5, 12, 11, 9, 10, 14, 2, 10]  # 과제 이미지에 있는 완전 이진 트리

# root 노드의 왼쪽과 오른쪽 자식 노드의 인덱스를 받아온다
left_child_index = get_left_child_index(tree, root_node_index)
right_child_index = get_right_child_index(tree,root_node_index)

print(tree[left_child_index])
print(tree[right_child_index])

# 9번째 노드의 부모 노드의 인덱스를 받아온다
parent_index = get_parent_index(tree, 9)

print(tree[parent_index])

# 부모나 자식 노드들이 없는 경우들
parent_index = get_parent_index(tree, 1)  # root 노드의 부모 노드의 인덱스를 받아온다
print(parent_index)

left_child_index = get_left_child_index(tree, 6)  # 6번째 노드의 왼쪽 자식 노드의 인덱스를 받아온다
print(left_child_index)

right_child_index = get_right_child_index(tree, 8)  # 8번째 노드의 오른쪽 자식 노드의 인덱스를 받아온다
print(right_child_index)

3. 포화 이진 트리 (Perfect Binary Tree)

포화 이진 트리는 위 트리처럼 모든 레벨이 빠짐없이 다 노드로 채워져있는 이진 트리이다.

트리 순회

순회 : 자료구조에 저장된 모든 데이터를 도는 것

트리에 저장된 모든 데이터를 출력해보도록 하자.
선형적 자료구조를 순회할 때는 보통 반복문을 사용하면 된다.
트리에서는 앞과 뒤라는 선형적인 관계가 없기 때문에 조금 다른 방식을 사용한다. 트리를 순회할 때는 주로 재귀함수를 사용한다.

순회 기본 동작
- 재귀적으로 왼쪽 부분 트리 순회
- 재귀적으로 오른쪽 부분 트리 순회
- 현재 노드 데이터 출력
트리를 순회하는 대표적인 방법 3가지
1. pre-order
2. post-order
3. in-order

1. pre-order 순회

: 부분 트리를 순회하기 전에 현재 노드를 출력하는 방법이다.

1. 현재 노드 데이터를 출력
2. 재귀적으로 왼쪽 부분 트리 순회
3. 재귀적으로 오른쪽 부분 트리 순회

pre-order의 출력 순서를 살펴보자. 위 순서를 재귀적으로 호출하는 것을 알 수 있다.

2. post-order 순회

: 부분트리를 순회한 후에 현재 노드를 출력하는 방법이다.

1. 재귀적으로 왼쪽 부분 트리 순회
2. 재귀적으로 오른쪽 부분 트리 순회
3. 현재 노드 데이터를 출력

post-order 출력 순서를 살펴보자.

3. in-order 순회, 파이썬 구현

: 부분트리 순회 사이에 현재 노드를 출력하는 방법이다.

1. 재귀적으로 왼쪽 부분 트리 순회
2. 현재 노드 데이터를 출력
3. 재귀적으로 오른쪽 부분 트리 순회

in-order 출력 순서를 살펴보자.

class Node:
    """이진 트리 노드를 나타내는 클래스"""

    def __init__(self, data):
        """이진 트리 노드는 데이터와 두 자식 노드에 대한 레퍼런스를 갖는다"""
        self.data = data
        self.left_child = None
        self.right_child = None

def traverse_inorder(node):
    """in-order 순회 함수"""
   
    if node is not None:
        traverse_inorder(node.left_child) # 1. 왼쪽 부분 트리를 in-order 순회한다
        print(node.data)   # 2. 현재 노드의 데이터를 출력한다.
        traverse_inorder(node.right_child) # 3. 오른쪽 부분 트리를 in-order 순회한다.

# 여러 노드 인스턴스 생성
node_A = Node("A")
node_B = Node("B")
node_C = Node("C")
node_D = Node("D")
node_E = Node("E")
node_F = Node("F")
node_G = Node("G")
node_H = Node("H")
node_I = Node("I")

# 생성한 노드 인스턴스들 연결
node_F.left_child = node_B
node_F.right_child = node_G

node_B.left_child = node_A
node_B.right_child = node_D

node_D.left_child = node_C
node_D.right_child = node_E

node_G.right_child = node_I

node_I.left_child = node_H

# 노드 F를 root 노드로 만든다
root_node = node_F

# 만들어 놓은 트리를 in-order로 순회한다
traverse_inorder(root_node)