크래프톤 정글 week02, day13 - 트리, 알고리즘 문제

트리(Tree)

• 노드(Node)들이 연결된 계층적인 자료구조
• 특징
  • 트리는 하나의 루트 노드를 갖는다.
  • 루트 노드는 0개 이상의 자식 노드를 갖는다.
  • 자식 노드도 0개 이상의 자식 노드를 가지는 반복적인 트리를 구성한다.

• 용어
  • 루트(Root)
    • 트리의 최상위에 있는 노드
  • 부모(Parent)
    • 노드 바로 위에 연결된 노드
  • 자식(Child)
    • 노드 바로 아래에 연결된 노드
  • 리프 노드(leaf Node)
    • 자식이 없는 마지막 노드
  • 내부 노드(Internal Node)
    • 리프 노드를 제외한 모든 노드
  • 레벨(Level)
    • 루트 노드부터의 거리

 

• 트리 순회 방법
  • 전위 순회(preOrder)
    • 루트를 먼저 방문하고 왼쪽 자식노드부터 오른쪽 자식 노드까지 순서대로 방문
  • 중위 순회(inOrder)
    • 왼쪽 자식 노드를 먼저 방문하고, 루트를 방문 후, 오른쪽 자식 노드를 순서대로 방문
  • 후위 순회(postOrder)
    • 왼쪽 자식 노드를 먼저 방문하고, 오른쪽 자식 노드를 방문 후, 루트를 순서대로 방문한다.

​

• 트리 종류
  • 이진 트리(Binary Tree)
    • 각 노드가 최대 두 개의 자식 노드를 가지는 트리
  • 이진 탐색 트리(Binary Search Tree, BST)
    • 이진 트리의 한 종류로, 각 노드에 대해 해당 노드의 왼쪽에 있는 노드들은 현재 값보다 작고 오른쪽에 있는 노드들은 현재 값보다 큰 특성이 있다
  • 힙(Heap)
    • 각 노드 값이 자식 노드의 값보다 크거나(최대 힙) 작다(최소 힙)는 속성을 만족하는 이진 트리이다.
  • B트리(B-Tree)
    • 자식 노드의 수가 2개 이상인 트리이며, 주로 데이터베이스 시스템이나 파일 시스템에서 사용된다.
  • AVL 트리
    • 이진 탐색 트리의 한 종류로, 노드의 왼쪽 노드들과 오른쪽 노드들의 높이 차이가 최대 1이 되도록 유지하는 자가 균형 트리
  • 레드-블랙 트리(Red-Black Tree)
    • 이진 탐색 트리에 레드와 블랙 두 가지 색을 추가한 형태의 트리. 균형을 유지하기 위해 사용되며, 연산 복잡도 최악의 경우를 피하기 위해 사용

---

 

트리순회

• 이진 트리를 입력받아 전위 순회, 중위 순회, 후위 순회 결과를 출력
• 첫 입력은 노드의 생성 개수이고, 두 번째 입력부터 노드가 입력된다.

# 이진트리의 노드를 표현하기 위해 데이터를 묶어 사용할 수 있는 클래스를 사용
class Node:
    # 입력된 노드를 초기화
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

# 전위순회 - 뿌리를 먼저 방문해 시작
def preOrder(node):
    if node is not None:
        # 현재 노드의 데이터를 출력
        print(node.data, end="")
        # 왼쪽 노드부터 접근해 오른쪽 노드까지 이동
        preOrder(node.left)
        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="")

# 노드 정보를 저장할 딕셔너리
nodes = {}

N = int(input())
for _ in range(N):
    # 입력값에 현재 노드, 왼쪽 자식, 오른쪽 자식 값 입력
    data, left, right = input().split()

    # 만약 nodes에 입력한 data가 없을 때 
    if data not in nodes:
        # Node(data)를 nodes 딕셔너리에 저장
        nodes[data] = Node(data)
    # 왼쪽 자식노드가 존재할 때
    if left != '.':
        # 근데 그 노드가 아직 생성되지 않았을 때
        if left not in nodes:
            # nodes 딕셔너리의 left자리에 노드를 넣고 그 노드의 왼쪽 자식값으로 넣기
            nodes[left] = Node(left)
            nodes[data].left = nodes[left]
    # 오른쪽 자식노드가 존재할 때
    if right != '.':
        # 근데 그 노드가 아직 생성되지 않았을 때
        if right not in nodes:
            # nodes 딕셔너리의 right자리에 노드를 넣고 그 노드의 오른쪽 자식값으로 넣기
            nodes[right] = Node(right)
            nodes[data].right = nodes[right]

# root에 nodes 딕셔너리에 A값 미리 입력
root = nodes['A']

# 각 순회에 맞는 함수에 시작점인 A노드로 root값 전달
# print("전위 순회: ", end="")
preOrder(root)
print()

# print("중위 순회: ", end="")
inOrder(root)
print()

# print("후위 순회: ", end="")
postOrder(root)
print()

 

학습 시간 : 10 ~ 25시