[Tree] 트리 순회 - Tree traversal

Tree Traversal

 

Tree Traversal 은 트리 순회이다.

Tree 자료구조에서 각각의 노드를 정화히 한 번만, 체계적으로 방문하는 과정이다.

 

전위 순회(PreOrder Traversl)

Root 노드부터 탐색하기 시작한다.

root => sub left => sub right

PreOrder Traversal은 가장 깊은 왼쪽 노드부터 탐색하기 때문에, 우리가 잘 알고 있는 DFS 라고 생각하면 된다.

def preOrder(node):
  print(node, end = ' ')

  if node.left != null:
    preOrder(node.left)

  if node.right != null:
    preOrder(node.right)

 

중위 순회(InOrder Traversal)

왼쪽 서브 트리부터 탐색하기 시작한다.

sub left => root => sub right

 

def inOrder(node):
  if node.left != null:
    inOrder(node.left)

  print(node, end = ' ')

  if node.right != null:
    inOrder(node.right)

 

후위 순회(PostOrder Traversal)

sub left => sub right => root

def inOrder(node):
  if node.left != null:
    inOrder(node.left)

  if node.right != null:
    inOrder(node.right)

  print(node, end = ' ')

 

레벨 순서 순회(Level-Order Traversal)

모든 node를 낮은 레벨 부터 순회한다.

BFS 라고 생각하면 된다.

def leverlOrder(graph, start_node):
  visited = []
  queue = []

  queue.append(start_node)
  visited.append(start_node)

  while queue:
    s = queue.pop(0)
    print(s, end = " ")

    for i in graph[start_node]:
      if i not in visited:
        visited.append(i)
        quque.append(i)

def levelOrder(tree):
  queue = []
  queue.append(tree)

  while queue:
    node = queue.pop(0)
    print(node.data, end = ' ')

    if node.left != None:
      queue.append(node.left)

    if node.right != None:
      queue.append(node.right)

Recursive

 

      9
  1       3
2   4   6   7

위와 같은 Tree 모양 일때, 순회 순수

PreOrder Traversal : 9 => 1 => 2 => 4 => 3 => 6 => 7

InOrder Traversal : 2 => 1 => 4 => 9 => 6 => 3 => 7

PostOrder Traversal : 2 => 4 => 1 => 6 => 7 => 3 => 9

Level-Order Traversal : 9 => 1 => 3 => 2 => 4 => 6 => 7