프로그래머스 강의_18

이진 트리(Binary Trees)

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

(1) 연산의 정의

• size() : 현재 트리에 포함되어있는 노드의 수를 구함

• depth() : 현재 트리의 깊이(또는 높이; height)를 구함

• 순회(traversal) :
  (2) 이진트리의 구현 - 노드(Node)
  노드는 data를 가지고 left와 right 두가지 포인터같은 것이 있다.

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

  (3) 이진트리의 구현 - 트리(Tree)

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

  (4) 이진트리의 구현 - size()
  => 재귀적인 방법으로 쉽게 구할 수 있음!
  만약 left subtree의 size()와 Right subtree의 size()를 알고 있다면 전체 이진트리의 size() = left subtree의 size() + right subtree의 size() + 1(자기 자신)

  class Node:
   def size(self):
       l = self.left.size() if self.left else 0
       r = self.right.size() if self.right else =
       return l + r + 1
   def size(self) :
       # size를 반환하는 함수
       if self.root:
           return self.root.size()
       # emptysubtree이면 size가 0이라는 뜻
       else:
           return 0 

  (5) 이진트리의 구현 - depth()
  => 재귀적인 방법으로 쉽게 구할 수 있음!
  전체 이진 트리의 depth() = left subtree의 depth()와 right subtree의 depth() 중 더 큰 것!+ 1

  class Node:
    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 depth(self):
        if self.root:
            return self.root.depth()
        else :
            return 0

  (6) 이진트리의 순회(Traversal)

• 깊이 우선 순회(depth first traversal)
  1) 중위 순회(in-order traversal)
  순회의 순서 : left subtree => 자기 자신 => right subtree

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

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

  2) 전위 순회(pre-order traversal)
  순회의 순서 : 자기자신 => Leftsubtree => Right subtree

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

  3) 후위 순회(post-order traversal)
  순회의 순서 : Left subtree => Right subtree > 자기자신

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

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