[Algorithm] 트리, 이진 트리, 깊이 우선 순회_TIL Day3-4

트리(trees)

트리란?

- 정점(node)과 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료 구조

- 최상단은 root node, 최 하단은 leaf node, 중간에는 내부 노드(internal nodes)라고 부름

 

이진 트리(Bynary Trees)

연산의 정의

• size() - 현재 트리에 포함되어 있는 노드의 수를 구함
• depth() - 현재 트리의 깊이 (또는 높이; height)를 구함
• traversal - 순회
  • 넓이 우선 순회 (breadth first traversal)
  • 깊이 우선 순회 (depth first traversal)
    - 중위 순회 : left subtree -> 자기 자신 -> right subtree
    - 전위 순회 : 자기 자신 -> Left subtree -> Right subtree
    - 후위 순회 : Left subtree -> Right subtree -> 자기 자신

깊이 우선 순회 구현해보기

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
        if(r > l):
            return r + 1
        else:
            return l + 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