[자료구조] Tree

Aug 17, 2023

Contents

트리 노드 표현 두가지 왼쪽 자식 - 오른쪽 형제 트리 이진트리

💡

트리 구조는 운영체제의 파일 시스템이 트리구조, 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

루트 노드부터 시작하여 아래로 내려오며넛

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

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

중위 순회 Inorder Traversal

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

루트를 거쳐

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

💡

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

후위 순회 Postorder Traversal

왼쪽 하위 트리 방문

오른쪽 하위 트리 방문 후

루트 노드를 방문한다


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()