[자료구조]이진트리(BinaryTree) 순회
스택, 큐, 리스트는 선형구조이므로 노드에 방문할 때 앞에서 뒤로 차례대로 접근하면 쉽게 방문이 가능했다. 하지만 트리는 계층구조이므로 노드 방문의 방법이 여러가지 있다.
하나의 이진트리는 여러 개의 이진트리(서브트리)로 구성되어 있어서 순회를 구현할 때 순환(recursion)적인 방법으로 구현하면 쉽게 구현할 수 있다.
1. 전위순회 ( preorder)
화살표 방향으로 루트, 왼쪽 서브트리, 오른쪽 서브트리 순으로 순회한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
void preorder() {
printf("\n preorder: ");
preorder(root);
}
// preorder() 을 호출하면 root를 매개변수로 하는 preorder(root)을 호출한다.
// 함수 오버로딩
void preorder(BinaryNode* node) {
if (node != NULL) {
printf(" [%c] ", node->getData());
preorder(node->getLeft());
preorder(node->getright());
}
}
// Root 값을 출력하고 왼쪽 서브트리를 매개변수로 함수 호출, 호출이 끝나면
// 오른쪽 서브트리를 매개변수로 함수 호출.
|
cs |
2. 중위순회 ( inorder )
화살표 방향으로 왼쪽 서브트리, 루트, 오른쪽 서브트리 순으로 순회한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
void inorder() {
printf("\n inorder: ");
inorder(root);
}
// inorder() 을 호출하면 root를 매개변수로 하는 inorder(root)을 호출한다.
// 함수 오버로딩
void inorder(BinaryNode* node) {
if (node != NULL) {
inorder(node->getLeft());
printf(" [%c] ", node->getData());
inorder(node->getright());
}
}
// 왼쪽 서브트리를 매개변수로 하는 inorder을 재귀적으로 호출하고
// 호출이 끝나면 값을 출력하고 오른쪽 서브트리를 매개변수로 하는
// inorder을 호출한다.
|
cs |
3. 후위순회 ( postoreder)
화살표 방향으로 왼쪽 서브트리, 오른쪽 서브트리, 루트 순으로 순회한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
void postorder() {
printf("\n postorder: ");
postorder(root);
}
// postorder() 을 호출하면 root를 매개변수로 하는 postorder(root)을 호출한다.
// 함수 오버로딩
void postorder(BinaryNode* node) {
if (node != NULL) {
postorder(node->getLeft());
postorder(node->getright());
printf(" [%c] ", node->getData());
}
}
// 왼쪽, 오른쪽 서브트리를 매개변수로 하는 함수 호출이 다 끝난 후
// 값을 출력한다.
|
cs |
4. 레벨순회 ( level order)
각 노드를 레벨 순으로 검사하는 순회 방법이다. 루트노드의 레벨이 1이고 아래로 내려갈수록 레벨은 증가한다. 레벨 순회는 선형자료구조 큐를 사용한다.
1. 루트노드가 입력된 큐에서 dequeue()를 시킨다.
2. dequeue() 된 노드의 자손노드를 left, right 순으로 enqueue() 시킨다.
3. dequeue()를 하고 그 노드의 자손노드를 left, right 순으로 enqueue() 시킨다.
4. 자손노드가 없을 경우에는 enqueue() 시키지 않는다.
5. 큐가 빌 때까지 반복
레벨순회를 위해서는 BinaryNode* 를 저장하는 큐가 필요하다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
void levelorder() {
printf("\n level oreder: ");
if (!isEmpty()) {
CircularQueue q;
// 노드를 삽입할 큐 초기화.
q.enqueue(root);
// 루트를 큐에 삽입.
while (!q.isEmpty()) {
BinaryNode* n = q.dequeue();
// 큐에 있는 노드를 dequeue() 시키고 n이 가르킴.
if (n != NULL) {
printf(" [%d] ", n->getData());
// n의 값 출력
q.enqueue(n->getLeft());
// n의 왼쪽 노드 큐에 삽입
q.enqueue(n->getright());
// n의 오른쪽 노드 큐에 삽입
}
// 큐가 빌 때까지 반복
}
printf("\n");
}
}
|
cs |
5. 결과
다음 그림과 같이 이진트리가 구성되었을 경우
