[자료구조] 12. 트리, 트리 순회 이해하기(feat. 정이진트리, 포화이진트리, 완전이진트리)

안녕하십니까 다제입니다. 

 

오늘은 트리와 트리의 종류 그리고 순회에 대해서 이야기를 해볼까합니다. 

 

 

---

 

목차 

 - 트리 정의

 - 구현 

 - 종류 및 특징

 - 순회 (pre, post, in)

 

 

---

 

1. 트리란?

  -. 여러 개의 노드들로 구성되어 계층적으로 하위 노드에 대한 reference를 갖는 구조 를 말합니다. 

 

2. 구현 

  -. 구현은 생각보다 간단합니다. 

  -. class를 정의하고 서로 간의 reference만 넣어주면됩니다. 

# 노드 클래스 생성 
class Node:
	def __init__(self, data):
    	self.data = data 
        self.left_child = None
        self.right_child = None 
 
 # 노드 생성 
 root_node = Node(1)
 node_1 = Node(2)
 node_2 = Node(3)
 node_3 = Node(4)
 
 # 노드 reference 연결 
 root_node.left_child = node_1
 root_node.right_child = node_2
 node_2.left_child = node_3
 
 # 출력 
 print(root_node.left_child.data)

 

 

---

 

3. 트리의 종류 및 특징 

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

    -. 정의 : 모든 노드의 하위 노드들이 0 또는 2로 채워진 구조 

    -. 구조 

정 이진 트리 예 - 직접 제작한 이미지	정 이진 트리 예 - 직접 제작한 이미지

 

  2) 완전 이진 트리(Perfect Binary Tree) 

    -. 정의 : 맨 마지막 노드를 제외한 모든 하위노드가 채워져 있으며, 맨 마지막 노드는 왼쪽부터 오른쪽으로 순차적으로 채워진 구조 

    -. 트리의 높이 

층 수	총 노드 수의 최솟값	총 노드 수의 최댓값
1	1	1
2	1+1	1+2
h	1+2+4+$2^{h-1}+1$ = $2^{h}$	1+2+4+$2^{h}$ = $2^{h+1}-1$

      * 위와 같이 높이와 노드 수의 관계를 수식으로 기재할 수 있습니다. 

      * 이해가 안돼시는 분들은 등비수열을 한번 검색해보시는 것을 추천드립니다. 

      * 위 식에서 h를 구해보도록 하겠습니다. 

      * $2^{h}$ <= n < $2^{h+1}-1$ 이런 수식이 성립되게 되고, 여기에 log를 취해줍니다. 

      * $log(n)$의 정수가 h가 됩니다. 

    -. 구조 

포화 이진 트리 예 - 직접 제작한 이미지	포화 이진 트리 예 - 직접 제작한 이미지

     * 여기서 중요한 것은 오른쪽 이미지 입니다. 오른쪽 이미지는 정 이진 트리이면서 포화 이진 트리의 구조를 갖습니다.

      * 정 이진 트리와 포화 이진 트리가 햇갈릴 수 있어서 준비한 이미지 입니다. 

 

  3) 포화 이진 트리(Complete Binary Tree)

    -. 정의 : 모든 노드가 채워진 구조 

    -. 트리의 높이 

      * n = $2^{h+1}-1$  이러한 수식이 성립되게 됩니다. 

      * 이를 계산하면 높이를 바로 알 수 있습니다. 

    -. 구조 

	없음
완전 이진 트리 예 - 직접 제작한 이미지	-

 

 

---

 

4. 순회(order)

 -. 순회란? 자료 구조에 저장된 데이터를 도는 것을 말합니다. 

 -. 순회에는 pre_order, post_order, in_order가 있습니다. 

 -. 각 순회를 구분 짓는 중요한 특징은 순회를 하는 도중 데이터 값을 출력하는 순서입니다. 

 -. 즉, pre_order는 데이터 값을 출력하고 left_child, right_child를 순회하고 

 -. post_order는 left_child, right_child를 순회하고 데이터 값을 출력하고  

 -. in_order는 left_child 순회하고 데이터 값을 출력하고 right_child를 순회합니다. 

 -. 코드로 살펴보도록 하겠습니다. 

def pre_order_traverse(node):
    """root node를 입력받아 트리를 순회하고 data를 출력하는 함수
        기능1) 현재 노드데이터를 출력하는 기능
        기능2) 재귀적으로 왼쪽 부분 트리 순회
        기능3)  재귀적으로 오른쪽 부분 트리 순회"""
    if node is not None:
        print(node.data)
        post_order_traverse(node.left_child)
        post_order_traverse(node.right_child)

def post_order_traverse(node):
    """root node를 입력받아 트리를 순회하고 data를 출력하는 함수
        기능1) 재귀적으로 왼쪽 부분 트리 순회
        기능2)  재귀적으로 오른쪽 부분 트리 순회
        기능3) 현재 노드데이터를 출력하는 기능 """
    if node is not None:
        post_order_traverse(node.left_child)
        post_order_traverse(node.right_child)
        print(node.data)


def in_order_traverse(node):
    """root node를 입력받아 트리를 순회하고 data를 출력하는 함수
        기능1) 재귀적으로 왼쪽 부분 트리 순회
        기능2)  현재 노드데이터를 출력하는 기능
        기능3)  재귀적으로 오른쪽 부분 트리 순회"""
    if node is not None:
        in_order_traverse(node.left_child)
        print(node.data)
        in_order_traverse(node.right_child)

 

꼭 한번씩 코드를 복사하셔서 실행을 해보시는 것을 추천드립니다. 

 

처음에는 감이 잘 안오실 수도 있지만, 코드를 하나씩 돌려보시다보면 이해가 되실겁니다. 

 

오늘도 글을 읽어주셔서 감사드립니다.