7장 트리 - (2) 트리의 순회

1. 트리의 순회(Tree Traversal)

- 트리의 모든 노드를 방문하는 순서이다.

- 그래프의 경우에는 DFS와 BFS가 있었다.

- 트리에서도 위의 두 방법을 사용할 수 있지만, 트리에서만 사용할 수 있는 세 방법이 있다.

- 프리오더, 인오더, 포스트오더 또는 전위 순회, 중위 순회, 후위 순회

- 세 방법의 차이는 루트 방문을 언

제 하냐의 차이이다.

1) 프리오더

 -노드 방문

 -왼쪽 자식 노드를 루트로 하는 서브 트리 프리오더

 -오른쪽 자식 노드를 루트로 하느 서비 트리 프리

오더

 -그래프의 DFS 탐색과 순서가 같다.

2) 인오더

 -왼쪽 자식 노드를 루트로 하는 서브 트리 인오더 

 -노드 방문

 -오른쪽 자식 노드를 루트로 하느 서비 트리 인오더

3) 포스트오더

 -왼쪽 자식 노드를 루트로 하는 서브 트리 포스트오더

 -오른쪽 자식 노드를 루트로 하느 서비 트리 포스트오더

 -노드 방문

 

위 그림에서 프리오더, 인오더, 포스트오더 순으로 트리를 방문해보자

- 프리오더 : A->B->D->E->C->F->G 

- 인오더 : D->B->E->A->F->C->G

- 포스트오더 : D->E->B->F->G->C->A

위 그림에서 프리오더, 인오더, 포스트오더 순으로 트리를 방문해보자

- 프리오더 : A->B->D->E->G->C->F

- 인오더 : D->B->G->E->A->C->F

- 포스트오더 : D->G->E->B->F->C->A

2. 문제

-트리 순회(1991번)

#include <iostream>

using namespace std;

int a[26][2]; // a[i][0] 는 i노드의 왼쪽 자식, a[i][1] 은 i노드의 오른쪽 자식을 저장

void preorder(int x) {

if (x == -1) {

return;

}

printf("%c", x + 'A');

preorder(a[x][0]);

preorder(a[x][1]);

}

void inorder(int x) {

if (x == -1) {

return;

}

inorder(a[x][0]);

printf("%c", x + 'A');

inorder(a[x][1]);

}

void postorder(int x) {

if (x == -1) {

return;

}

postorder(a[x][0]);

postorder(a[x][1]);

printf("%c", x + 'A');

}

int main(void) {

int n;

cin >> n;

for (int i = 0; i < n; i++) {

char node;

cin >> node;

char left, right;

cin >> left >> right;

a[node - 'A'][0] = -1;

a[node - 'A'][1] = -1;

if(left!='.')

a[node - 'A'][0] = left - 'A';

if(right!='.')

a[node - 'A'][1] = right - 'A';

}

preorder(0);

cout << '\n';

inorder(0);

cout << '\n';

postorder(0);

cout << '\n';

return 0;

}