깊이우선순회(DFS)

깊이 우선 순회(Depth First Traversal)

깊이 우선 순회는 다시 중위 순회(In-order Traversal), 전위 순회, 후위 순회로 나누어진다.

• 중위 순회(In-order Traversal)

중위 순회는 (1)Left subtree $\rightarrow$ (2)자기 자신 $\rightarrow$ (3)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 []

• 전위 순회(Pre-order Traversal)

전위 순회는 (1)자기 자신 $\rightarrow$ (2)Left subtree $\rightarrow$ (3)Right subtree 순으로 순회한다. 구현은 앞서 inorder와 같은 방식으로 쉽게 할 수 있다.

• 후위 순회(Post-order Traversal)

후위 순회는 (1)Left subtree $\rightarrow$ (2)Right subtree $\rightarrow$ (3)자기 자신 순으로 순회한다. 이 역시 앞서 inorder와 같은 방식으로 구현을 쉽게 할 수 있다.