[프로그래머스 알고리즘] 18강: 이진 트리 (Binary Trees)

이진트리의 추상적 자료구조

연산의 정의

• size() : 현재 트리에 포함되어 있는 노드의 수를 구함
  • 재귀적으로 구하기 쉬움
  • 전체 이진트리의 사이즈 = left subtree의 size() + right subtree의 size() + 1(자기 자신)
• depth() : 현재 트리의 깊이 (또는 높이)를 구함
  • 이도 재귀적은 방법으로 쉽게 구할 수 있음
  • max(left subtree의 depth(), right subtree의 depth()) + 1
• traversal() : 현재 트리의 노드를 방문하여 리스트에 추가함
  • 깊이 우선 순회 (depth first traversal)
    • 중위 순회(in-order traversal) : left subtree -> 자기 자신 -> right subtree

      

    • 전위 순회(pre-order traversal) : 자기 자신 -> left subtree -> right subtree

      

    • 후위 순회(post-order traversal) : left subtree -> right subtree -> 자기자신

      

  • 넓이 우선 순회 (breadth first traversal)

 

이진트리의 구현 - 노드(node)

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

 

이진트리의 구현 - 트리(tree)

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

 

---

18강 실습(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

 

18강 실습(2) : 이진트리의 전위순회 연산 구현

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


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 []

 

18강 실습(3) : 이진트리의 후위순회 연산 구현

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 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 postorder(self):
        if self.root:
            return self.root.postorder()
        else:
            return []