트리

정의

 데이터의 상-하 관계(계층적 관계)를 저장하는 자료 구조

 

용어

 1. root 노드(뿌리 노드): 트리의 시작 노드, 뿌리가 되는 노드

 2. 부모노드 : 특정 노드의 직속 상위 노드

 3. 자식노드 : 특정 노드의 직속 하위 노드

 4. 형제노드 : 같은 부모를 갖는 노드

 5. leaf 노드 : 자식 노드를 갖고 있지 않은, 가장 말단에 있는 노드

 

종류

 이진트리

 1. 각 노드가 최대 2개의 자식 노드를 갖을 수 있는 트리

 2. 구현

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

root_node = Node(2)
node_B = Node(3)
node_C = Node(5)
node_D = Node(7)
node_E = Node(11)

# B와 C를 root 노드의 자식으로 지정
root_node.left_child = node_B
root_node.right_child = node_C

# D와 E를 root 노드의 자식으로 지정
node_B.left_child = node_D
node_B.right_child = node_E

# root 노드에서 왼쪽 자식 노드 받아오기
test_node_1 = root_node.left_child

print(test_node_1.data)

# 노드 B의 오른쪽 자식 노드 받아오기
test_node_2 = test_node_1.right_child

print(test_node_2.data)

 정 이진 트리(Full Binary Tree)

  - 모든 노드가 2개 또는 0개의 자식을 갖는 이진트리

완전 이진 트리(Complete Binary Tree) - O(lg(n))

  - 이진 트리 중 마지막 레벨 직전의 레벨까지는 모든 노드들이 다 채워진 트리

  - 마지막 레벨에 노드들이 다 채워질 필요가 없어도 왼쪽부터 오른쪽 방향으로는 다 채워져야함을 의미

구현

def get_parent_index(complete_binary_tree, index):
    """배열로 구현한 완전 이진 트리에서 index번째 노드의 부모 노드의 인덱스를 리턴하는 함수"""
    parent_index = index // 2

    # 부모 노드가 있으면 인덱스를 리턴한다
    if 0 < parent_index < len(complete_binary_tree):
        return parent_index

    return None


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

    # 왼쪽 자식 노드가 있으면 인덱스를 리턴한다
    if 0 < left_child_index < len(complete_binary_tree):
        return left_child_index

    return None


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

    # 오른쪽 자식 노드가 있으면 인덱스를 리턴한다
    if 0 < right_child_index < len(complete_binary_tree):
        return right_child_index

    return None

# 테스트 코드
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)

 

 포화 이진 트리(Perfect Binary Tree)

  - 모든 레벨이 빠짐없이 다 노드르 채워져있는 이진 트리