18. 트리의 운행(9-2)
1. 트리의 운행(tree traversal)
트리의 운행(tree traversal) 이란?
트리 구조의 각 노드를 전부 한번씩 방문하여 검색해내는 방법
일반 트리의 운행법
레벨 순서 (level order) 운행 방법
가장 간단한 트리 운행법으로 트리의 각 노드를 근 노드부터 시작하여 레벨순서대로 노드를 차례로 방문하여 검색하는 방법
하향식 레벨 순서(topdown level order) 방법
- 트리의 근 노드로 부터 시작하여 점차 레벨이 낮은 부분의 노드들을 순서대로 검색해 나가는 방법
상향식 레벨 순서(bottom up level order) 방법
- 트리 구조의 가장 낮은 레벨에 있는 잎 노드부터 시작하여 점차 상위
레벨의 노드를 순서대로 검색하고 마지막으로 근 노드를 검색하는 운행 방법
노드의 위치에 따른 운행법
전위 운행법(preorder traverse) : root-left-right 운행법
근 노드를 방문하고, 그 다음 레벨의 서브트리를 차례로 방문해서 검색하는 방법
만약 서브트리를 운행하던 중 잎 노드를 만나면 오른쪽에 있는 형제노드를 방문하여 검색하게 된다.
즉 근 노드의 왼쪽 서브트리를 먼저 검색하고 난 후 오른쪽 서브 트리를 검색하게 된다.
이때 서브트리의 운행은 근 노드를 기준으로 할 때와 같다.
후위 운행법(postorder traverse ) : left-right-root 운행법
후위 운행법은 먼저 서브트리를 방문 처리한 후 근 노드를 마지막으로 운행하는 방법
이때 한 서브트리의 처리가 끝나면 형제노드의 서브트리로 넘어간다.
후위 운행 순서 : E→F→B→K→L→M→G→C→H→I→J→D→A
패밀리 순서(family order)운행법 : 스택 이용 방법
먼저 근 노드를 검사하고, 그 다음 근 노드의 자식 노드들을 차례대로
검사한 후 가장 늦게 검사된 자식 노드로부터 역순으로 앞의 작업들을
순환적으로 반복하여 운행하는 방법
방문 순서 과정
근 노드를 방문한다.
근 노드의 자식 노드를 차례대로 방문하여 스택에 저장한다.
더 이상 자식 노드가 없으면, 스택의 TOP에서 1개의 노드를
출력하여 출력된 노드의 자식 노드를 스택에 입력하고,
스택에 더 이상의 데이터가 없을 때까지 위 과정을 반복한다.
단, 출력된 노드의 자식노드가 존재하지 않으면 스택의
마지막 노드를 출력한 후 위 과정을 반복한다.
이진 트리의 운행법(binary tree traversal)
왼쪽 서브트리가 오른쪽 서브트리보다 우선하는 경우
근 노드→ 왼쪽 서브트리→ 오른쪽 서브트리
왼쪽 서브트리→근 노드→ 오른쪽 서브트리
왼쪽 서브트리→ 오른쪽 서브트리→근 노드
오른쪽 서브트리가 왼쪽 서브트리보다 우선하는 경우
근 노드→ 오른쪽 서브트리→ 왼쪽 서브트리
오른쪽 서브트리→근 노드→ 왼쪽 서브트리
오른쪽 서브트리→ 왼쪽 서브트리→근 노드
이진트리의 노드 정의
struct node {
struct node *leftnode;
char data;
struct node *rightnode;
};
전위 운행법(root-left-right)의 알고리즘(polish 표기법)
이진 트리의 근 노드에서 출발하여 먼저 근 노드를 출력한 후 왼쪽
서브 트리로 이동하여 왼쪽 서브 트리의 근 노드를 출력한다.
이와 같이 왼쪽 서브 트리로 이동과 출력을 마지막 잎 노드에
도달할 때까지 반복한다. 이때 잎 노드는 서브 트리 중 가장 왼쪽
자식노드를 의미한다.
그런 후 잎 노드에 대한 부모 노드의 오른쪽 서브트리를 방문한다.
이때 왼쪽 서브트리의 방문이 모두 끝나면 근 노드의 오른쪽
서브트리를 방문한다. 오른쪽 서브트리의 방문은 위 과정을 반복한다.
전위 운행 알고리즘
Void preorder(struct node * NODE)
{
if (NODE != NULL)
{
printf(“%c”, NODE -> data); //근 노드 방문
preorder(NODE -> leftchild); //왼쪽 서브트리 방문
preorder(NODE -> rightchild; //오른쪽 서브트리 방문
}
}
중위 운행법(left-root-right)의 알고리즘
이진 트리의 근 노드에서 출발하여 먼저 왼쪽 서브트리에 대하여
순환적으로 노드들을 방문한 후 더 이상 왼쪽 서브트리의 노드가
없을 때까지 방문을 계속 한다.
그 다음 근 노드를 방문하고, 그후 오른쪽 서브트리를 순환적으로
방문하고 모든 노드의 방문이 끝나면 운행을 종료한다.
후위 운행법(left-right-root)의 알고리즘
먼저 왼쪽 서브트리에 대하여 순환적으로 노드들을 방문한 후 왼쪽
서브트리에서의 방문이 끝나면 오른쪽 서브트리를 순환적으로
방문한다.
이때 오른쪽 서브트리의 마지막 잎노드까지 모두 방문한 후
근 노드를 방문하여 운행을 종료한다. 이것은 원시 프로그램을
컴파일시 중간 부호 형태로 변환시킬 때 주로 사용하는 방법이다.
후위 운행법(left-right-root)의 알고리즘
후위 운행 알고리즘
Void postorder(struct node * NODE)
{
if (NODE != NULL)
{
postorder(NODE -> leftchild); //왼쪽 서브트리 방문
postorder(NODE -> rightchild; //오른쪽 서브트리 방문
printf(“%c”, NODE -> data); //근 노드 방문리 방문
}
}
