트리 / 깊이 우선 탐색

트리

• 트리들은 데이터베이스 시스템 또는 검색 엔진 등에서 아주 많이 이용된다.
• 트리를 딱딱하게 말하면, 순환하는 길이 없는 그래프 (graph) 로 정의된다.

트리 용어

• 노드 (nodes)
• 간선 (edges)
• 루트 노드 (root node), 리프 노드 (leaf nodes), 내부 노드 (internal nodes)
• 부모 (parent) 노드와 자식 (child) 노드
• 노드의 수준 (level)
• 노드의 차수 (degree)
• 트리의 높이 (height) - 또는, 깊이 (depth) -
• 부분 트리 (서브트리; subtrees)
• 이진 트리 (binary trees)
• 포화 이진 트리 (full binary trees)
• 완전 이진 트리 (complete binary trees)

트리 종류

• 포화 이진트리

• 완전 이진트리 (리프 노드 위는 모두 포화 이진트리, 리프노드는 순차적으로 채워져있음)

 

실습 1 - depth 구현하기

class Node:

    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None

    def size(self):
        l = self.left.size() if self.left else 0
        r = self.right.size() if self.right else 0
        return l + r + 1

    def depth(self):
        l = self.left.depth() if self.left else 0
        r = self.right.depth() if self.right else 0
        return max(l , r) + 1

class BinaryTree:

    def __init__(self, r):
        self.root = r

    def size(self):
        if self.root:
            return self.root.size()
        else:
            return 0

    def depth(self):
        if self.root:
            return self.root.depth()
        else:
            return 0

def solution(x):
    return 0

• size는 해당 트리안에 모든 노드의 개수를 세는 반면, depth는 각 노드 탐색이 가능하다면 max(l , r) + 1를 이용한 재귀로 트리의 깊이를 구할 수 있다.

실습 2 - 순회(inorder,preorder, postorder) 구현하기

class Node:

    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None


    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self.data)
        if self.right:
            traversal += self.right.inorder()
        return traversal


    def preorder(self):
        traversal = []
        traversal.append(self.data)
        if self.left:
            traversal += self.left.preorder()
        if self.right:
            traversal += self.right.preorder()
        return traversal

    def postorder(self):
        traversal = []
        if self.left:
            traversal += self.left.postorder()

        if self.right:
            traversal += self.right.postorder()

        traversal.append(self.data)
        return traversal


class BinaryTree:

    def __init__(self, r):
        self.root = r


    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []


    def preorder(self):
        if self.root:
            return self.root.preorder()
        else:
            return []


    def postorder(self):
        if self.root:
            return self.root.postorder()
        else:
            return []



def solution(x):
    return 0