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

다음과 같은 연산이 정의된다.

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

  • depth(): 현재 트리의 깊이(또는 height)

  • traversal(순회)


노드(Node)

노드는 Data/LeftChild/RightChild를 가진다.

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


트리(Tree)

앞서 Node에서 연결되는 부분을 다 지정해주므로, Binary tree에서는 루트 노드(root node)가 어디인지만 정의해주면 된다.

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


size()

각 노드에서 size()를 정의해주면, 전체의 노드 수는 이를 이용하여 재귀적인 방법으로 쉽게 구할 수 있다.

class Node:
  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

Binary Tree 전체에 대해서 노드의 수를 구하는 메소드는 다음과 같다.

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


depth()

전체 이진 트리의 depth()는 left subtree의 depth()와 right subtree의 depth()를 확인하여 그 중 더 큰 것에 1을 더하여 구해줄 수 있다.

class Node:
  def depth(self):
    ...

clas BinaryTree:
  def depth(self):
    ...


순회(Traversal)

순회는 크게 두 가지로 나누어진다.

  • 깊이 우선 순회(DFS: Depth First Traversal)

  • 넓이 우선 순회(BFS: Breadth First Traversal)

이 두 가지에 대해서는 다음 포스트들에서 살펴보도록 한다.