📒 트리 - 순회

📌 깊이 우선 순회

📙 구현

• 중위 순회(in-order traversal) : 왼쪽 오른쪽 사이의 자기자신을 순회하는 것

  1. Left subtree
  2. 자기 자신
  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. 자기 자신
  2. Left subtree
  3. 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 []

• 후위 순회(post-order traversal) : 자기자신을 마지막에 순회하는 것

  1. Left subtree
  2. Right subtree
  3. 자기 자신

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

📌 넓이 우선 순회

• 원칙
  • 수준(level)이 낮은 노드를 우선으로 방문
  • 같은 수준의 노드들 사이에는 부모 노드의 방문 순서에 따라 방문, 왼쪽 자식이 우선
  • 재귀적 방법이 적합하지 않다.
  • 한 노드를 방문했을 때,
    • 나중에 방문할 노드들을 순서대로 기록해 두어야한다.
    • 큐를 이용하면 된다.

📙 구현

1. 빈 리스트 -> (초기화) traversal, 빈 큐 -> q
2. 빈 트리가 아니면, root node를 q에 추가(enqueue)
3. q가 비어 있지 않은 동안
   3-1. q에서 node원소를 추출(dequeue)
   3-2. node를 방문
   3-3. node의 왼쪽, 오른쪽 자식(있으면)들을 q에 추가
4. q가 빈 큐가 되면 모든 노드 방문 완료

class BinaryTree:
	def bft(self):
    	q = ArrayQueue()
        traversal = []
        if self.root:
        	q.append(self.root)
        while q.Empty()==0:
        	node = q.dequeue
            traversal.append(node.data)
            if node.left:
            	q.enqueue(node.left)
            if node.right:
            	q.enqueue(node.right)
        return traversal