[Python] BinaryTree 구현하기

💡 트리 구조는 운영체제의 파일 시스템이 트리구조, HTML이나 XML 문서를 다룰 때 사용하는 DOM도 트리구조로 이루어져 있다. 또한 검색 엔진이나 데이터베이스도 트리 자료구조를 기반으로 한다

• root : 최상위 노드
• 부모노드 : 자식 노드를 가진 노드
• 자식노드 : 부모 노드의 하위노드
• 형제노드 : 부모가 같은 노드
• 리프노드 : 자식이 없는 노드
• 서브트리 : 특정 노드를 루트로 생각할 때 생기는 트리

트리 노드 표현 두가지

• N-링크 표현법
• 왼쪽 자식 오른쪽 형제 트리

왼쪽 자식 - 오른쪽 형제 트리

class LCRSNode:
    def __init__(self, new_data):
        self.left_child = None
        self.right_sibling = None
        self.data = new_data

def LCRS_DestroyTree(root):
    if root.right_sibling is not None:
        LCRS_DestroyTree(root.right_sibling)

    if root.left_child is not None:
        LCRS_DestroyTree(root.left_child)

    root.left_child = None
    root.right_sibling = None

def LCRS_AddChildNode(parent, child):
    if parent.left_child is None:
        parent.left_child = child
    else:
        temp_node = parent.left_child
        while temp_node.right_sibling is not None:
            temp_node = temp_node.right_sibling

        temp_node.right_sibling = child

def LCRS_PrintTree(node, depth):
    for i in range(depth-1):
        print("   ", end='')  # 공백 3칸

    if depth > 0:  # 자식 노드 여부 표시
        print("+--", end='')

    # 노드 데이터 출력
    print(node.data)

    if node.left_child is not None:
        LCRS_PrintTree(node.left_child, depth + 1)

    if node.right_sibling is not None:
        LCRS_PrintTree(node.right_sibling, depth)

이진트리

하나의 노드가 자식 노드를 2개까지 만 가질 수 있는 이진 트리 → 각 노드의 최대 차수가 2이다.

위의 그림을 포화 이진트리 ( Full Binary Tree )

포화 이진 트리의 전단계를 완전 이진트리(Complete Binary Tree)

💡 포화 이진 트리와 완전 이진 트리를 분류해서 설명하는 이유는 검색에서 트리의 노드가 가능한 한 완전한 모습으로 유지해야 높은 성능이 가능하다.

높이 균형 트리와 완전 높이 균형 트리

루트 노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 2이상 차이가 나지 않는 이진 트리를 말함

이진 트리의 순회

💡 순회 Traversal는 트리 안에서 노드 사이를 이동하는 연산
전위 순회, 중위 순회, 후위 순회가 있다

• 전위 순회 Preorder Traversal
  

1. 루트 노드부터 시작하여 아래로 내려오면서

2. 왼쪽 하위 트리를 방문하고, 방문이 끝나면

3. 오른쪽 하위 트리를 방문한다

• 중위 순회 Inorder Traversal
  

1. 왼쪽 하위 트리부터 시작해서

2. 루트를 거쳐

3. 오른쪽 하위 트리를 방문하는 방법이다

   💡 응용하는 대표 사례는 수식 트리

• 후위 순회 Postorder Traversal
  

1. 왼쪽 하위 트리 방문

2. 오른쪽 하위 트리 방문 후

3. 루트 노드를 방문한다

   class Node:
       def __init__(self, data, left = None, right = None):
           self.data = data
           self.left = left
           self.right = right
   
   class BinaryTree:
       def __init__(self, root):
           self.root = root
   
   def preorder(node):
       if node is not None:
           print(node.data,end=" ")
           if node.left:
               preorder(node.left)
           if node.right:
               preorder(node.right)
   
   def inorder(node):
       if node is not None:
           inorder(node.left)
           print(node.data,end=" ")
           inorder(node.right)
   
   def postorder(node):
       if node is not None:
           postorder(node.left)
           postorder(node.right)
           print(node.data,end=" ")
   
   A = Node('A')
   B = Node('B')
   C = Node('C')
   D = Node('D')
   E = Node('E')
   F = Node('F')
   G = Node('G')
   # 트리에 노드 추가
   A.left = B
   B.left = C
   B.right = D
   
   A.right = E
   E.left = F
   E.right = G
   
   # 트리 출력
   print("Preorder ...")
   preorder(A)
   print()
   
   print("Inorder ...")
   inorder(A)
   print()
   
   print("Postorder ...")
   postorder(A)
   print()