(자료구조 기본개념)전위순회, 중위순회, 후위순회

간략하게 내 식으로 기억하기

1. 코드 중심으로 이해하기      

// 노드의 내용을 출력하는 printf("%d", w->key) 위치가 , 

자식에 방문하는 명령문들 앞에오면 전위,

자식 방문하는 중간에 있으면 중위, 

자식 다 방문한 후에 있으면 후위

의사코드

preOrder(NODE* w)

{

if(w = NULL)

return

printf("%d", w->key)

preOrder(w->left)

preOrder(w->right)

}

inOrder(NODE* w)

{

if(w = NULL)

return

inOrder(w->left)

printf("%d", w->key)

inOrder(w->right)

}

postOrder(NODE* w)

{

if(w = NULL)

return

postOrder(w->left)

postOrder(w->right)

printf("%d", w->key)

}

2. 실제 트리의 모형상에서 움직이는 특징 관찰(나중에 시간나면 트리 순회하는 그림들 갖다 붙여놓자)

-전위순회

부모노드 -> 왼쪽노드 -> 왼쪽노드의  자식 노드들 -> 오른쪽 노드 -> 오른쪽노드의 자식 노드들

빨간색 표시한 부분에서 자식노드를 방문하는 방식은 역시    본인->왼쪽->오른쪽

-중위순회

트리상으로 보면 가장 왼쪽에 위치하는 녀석이 먼저 출력된다고 보면 됨

-후위순회

가장 왼쪽 말단에 있는 녀석부터 출력하기 시작함.

그 다음부터는 자식들이 모두 출력되면, 바로 그 부모가 바로 다음으로 출력되는 방식으로 진행됨

결국 루트노드는 제일 상단레벨에 있으므로, 루트이외의 모든 노드가 방문되어서야 출력된다.

레벨 순회는 생각하기 쉬워서 따로 정리 안함