자료구조(파이썬) - 트리 (Tree)

교육 정보

• 교육 명: 경기미래기술학교 AI 교육
• 교육 기간: 2023.05.08 ~ 2023.10.31
• 오늘의 커리큘럼:
  파이썬 자료구조
  (7/17 ~ 7/28)
• 강사: 이현주, 이애리 강사님
• 강의 계획:
  1. 자료구조

자료구조

트리 (Tree)

• 데이터의 계층적 관계를 나타내는 자료구조

• 이진트리 구현하기
  • 이진트리: 한 노드가 최대 2개의 자식노드를 가질 수 있는 트리

class Node:
  def __init__(self, data):
    self.data = data
    self.left_child = None
    self.right_child = None

root = Node(1)
node1 = Node(2)
node2 = Node(3)
node3 = Node(4)
node4 = Node(5)

root.left_child = node1 
root.right_child = node2
node1.left_child = node3
node1.right_child = node4


print(root.left_child.left_child.data)
print(root.right_child.data)
#
# 결과
4
3

• 완전 이진트리
  • leaf node 이전의 모든 노드가 채워져 있고 leaf node 레벨의 노드가 왼쪽부터 채워져있는 트리

• 완전 이진트리에서 부모/자식 노트 찾기
  - 완전 이진트리 리스트 저장 방법
  = [None, root, 깊이 1인 노드 왼쪽 - 오른쪽 순서, 깊이 2인 노드 왼쪽 - 오른쪽 순서...]
  - 특정 부모 노드의 왼쪽 왼쪽 노드 찾기
  : 왼쪽 자식 노드 = 부모 노드 인덱스 * 2
  - 특정 부모 노드의 오른쪽 자식 노드 찾기
  : 오른쪽 자식 노드 = (부모 노드 인덱스 * 2) + 1
  - 반대로 자식노드에서 부모 노드찾기
  : 자식노드 % 부모 노드

  def get_parent_index(complete_binary_tree, index):
    if index == 1:
        return None
    else:
        return index // 2
  def get_left_child_index(complete_binary_tree, index):
    child_idx = index * 2
    if child_idx >= len(complete_binary_tree)-1:
        return None
    else:
        return child_idx
  def get_right_child_index(complete_binary_tree, index):
    child_idx = index * 2 + 1
    if child_idx >= len(complete_binary_tree)-1:
        return None
    else:
        return child_idx