Tree Traversal   트리 순회

(2020-09-13)

트리 탐색

1.  트리 순회 (Tree Traversal)

  ㅇ 모든 정점을 한번씩 만 방문하거나, 목표 정점을 찾아가는 방법

  ㅇ 트리 순회 특징
     - 각 노드의 하부들을 각각 독립된 부분 트리(subtree)로써 순회
     - 즉, 재귀적(순환적)인 방법으로 서브 트리를 정의하며 순회할 수 있음


2. 트리 순회 종류 : 서브 트리 기준으로 순회전위 순회 (Preorder Traversal)
     - 루트 노드를 시작으로, 
     - 왼쪽 서브 트리를 먼저 순회하고,
     - 오른쪽 서브 트리를 그다음 순회
     * 깊이 우선, 전위 순회 (Depth First, Preorder Traversal) 라고도 함
       

  ㅇ 중위 순회 (Inorder Traversal)
     - 제일 왼쪽 최하위 노드를 시작으로,
     - 왼쪽 서브 트리를 먼저 순회하고
     - 부모(루트)를 거쳐,
     - 오른쪽 서브 트리들을 차례대로 순회
       

  ㅇ 후위 순회 (Postorder Traversal)
     - 제일 왼쪽 최하위 노드를 시작으로,
     - 왼쪽 서브 트리를 먼저 순회하고,
     - 오른쪽 서브 트리들을 차례대로 순회하고,
     - 부모(루트)를 순회
       


3. 기타 순회 종류 트리 순회가 아닌 그래프 순회로써, 너비 우선 (Breadth First Serach) 순회 방식 

       


[트리] 1. 트리 2. 트리 용어 3. 트리 종류 4. 이진 트리 5. 이진 탐색 트리 6. 스패닝 트리 7. 트리 순회 8. B 트리 9. 10. 멀티캐스트 트리 11. 결정 트리

 
        최근수정     요약목록     참고문헌