간략하게 내 식으로 기억하기
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. 실제 트리의 모형상에서 움직이는 특징 관찰(나중에 시간나면 트리 순회하는 그림들 갖다 붙여놓자)
-전위순회
부모노드 -> 왼쪽노드 -> 왼쪽노드의 자식 노드들 -> 오른쪽 노드 -> 오른쪽노드의 자식 노드들
빨간색 표시한 부분에서 자식노드를 방문하는 방식은 역시 본인->왼쪽->오른쪽
-중위순회
트리상으로 보면 가장 왼쪽에 위치하는 녀석이 먼저 출력된다고 보면 됨
-후위순회
가장 왼쪽 말단에 있는 녀석부터 출력하기 시작함.
그 다음부터는 자식들이 모두 출력되면, 바로 그 부모가 바로 다음으로 출력되는 방식으로 진행됨
결국 루트노드는 제일 상단레벨에 있으므로, 루트이외의 모든 노드가 방문되어서야 출력된다.
레벨 순회는 생각하기 쉬워서 따로 정리 안함
'알고리즘' 카테고리의 다른 글
이진 탐색트리_ 탐색, 삽입, 삭제, 전위순회 (0) | 2018.07.10 |
---|---|
최소신장트리 간선의 가중치 출력 - Kruskal으로 간선이 선택됨 (0) | 2018.07.09 |
무방향 간선 그래프 만들고 그래프 너비우선탐색(BFS)으로 순회 (0) | 2018.07.06 |
인접행렬을 이용한 그래프 구현하기(알고리즘_교보문고_국형준 참고) (0) | 2018.07.05 |
배열로 구현한 개방조사법 해시테이블(선형조사법으로 충돌 방지) (0) | 2018.07.05 |