트리구조

Tree

💡 서로 연결된 Node의 계층형 자료구조로써, root와 부모-자식 관계의 subtree로 구성됨

트리 관련 용어

• 노드 : 구성 요소
• 간선 (Edge) : 노드간에 연결된 선
• 루트 노드(Root) : 트리의 시작점
• 리프 노드(Leaf) : 트리의 마지막 노드
• 자식 노드(child), 부모 노드(parent), 형제 노드(sibiling)
• 차수 (degree) : 각 노드 갖는 자식의 수, 모든 노드의 차수가 n개 이하인 트리를 n진 트리라고 한다
• 조상 (ancestor) : 위쪽으로 간선을 따라가면 만나는 모든 노드
• 자손 (descendant) : 아래쪽으로 간선을 따라가면 만나는 모든 노드
• 높이 (height) : 루트 노드에서 가장 멀리있는 리프 노드 까지의 거리, 즉 리프 노드중에 최대 레벨 값
• 서브트리 (subtree) : 트리의 어떤 노드를 루트로 하고, 그 자손으로 구성된 트리

현재 위의 그림은 2진트리임

Binary Tree

위의 그림처럼 차수가 2개 이하인 트리를 이야기한다

코테에서 가장 활용이 많이 된다

Complete Binary Tree

완전 2진트리

마지막 레벨을 제외한 나머지 레벨이 차수가 2로 꽉꽉 채워져 있는 상태이다

꽉꽉 채워야하기 때문에 만약에 노드를 추가 하고 싶다면 위의 그림 숫자처럼 차례차례 넣어야한다

노드의 구현

노드 구현하기

class Node:
  def __init__(self):
    self.value = 0
    self.left_child = None
    self.right_child = None

2진트리 구현

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

class BinaryTree:
  def __init__(self):
    self.root = None # 루트 만들어주기
    
bt = BinaryTree()
bt.root = Node(value=1)
bt.root.left = Node(value=2)
bt.root.right = Node(value=3)
bt.root.left.left = Node(value=4)
bt.root.left.right = Node(value=5)
bt.root.right.right = Node(value=6)

이 코드를 트리구조 그림으로 그려보면