트리 순회

 

트리 순회

 

 일단 트리가 구성되어 있다면, 이 트리를 다양한 방법으로 순회하여 원하는 노드에 접근할 수 잇다.

다양한 순회 방법에 대해 간략히 알아보자.

 

• 전위 순회 (preorder traversal) 
  이 방법은 현재 노드를 먼저 방문하고, 그다음은 현재 노드의 왼쪽 하위 노드를,
  마지막으로는 현재 노드의 오른쪽 하위 노드를 재귀적인 방식으로 방문한다.
  여기서 '전위(pre)'는 상위 노드를 하위 노드보다 먼저 방문한다는 뜻이다.
  
  전위 순회는 항상 부모 노드를 방문한 다음 왼쪽 자식 노드, 오른쪽 자식 노드를 차례로 방문한다.
  이러한 방식의 순호를 루트 노드에서만 수행하는 것이 아니라
  루트 노드 아래의 모든 서브 트리에 대해 적용한다.
  
  
  
• 중위 순회 (in-order traersal)
  중위 순회 방법은 왼쪽 노드를 먼저 방문하고, 그 다음에는 현재 노드,
  마지막으로는 오른쪽 노드를 방문한다.
  
  
  
• 후위 순회 (post-order traversal)
  후위 순회 방법은 두 자식 노드를 먼저 방문한 후, 현재 노드를 방문한다.
  
  
  
• 레벨 순서 순회 (level order traversal)
  레벨 순서 순회 방법은 트리의 맨 위 레벨부터 아래 레벨까지,
  왼쪽 노드에서 오른쪽 노드 순서로 방문한다.
  즉, 트리의 루트 노드부터 단계별로 차례대로 나열하는 것과 같다.