DFS - 전위순회, 중위순회, 후위순회

전위순회, 중위순회, 후위순회란?

이진 트리(Binary Tree)를 순회하는 방법을 얘기한다.

전위순회는 루트 -> 왼쪽 자식 -> 오른쪽 자식

중위순회는 왼쪽 자식 -> 루트 -> 오른쪽 자식

후위순회는 왼쪽 자식 -> 오른쪽 자식 -> 루트를 의미한다.

 

아래 1부터 7까지 가지는 Tree를 순회하며 출력해보자.

1에서 7까지의 트리

DFS를 표현하면 다음과 같다. 다음은 전위 순회를 의미한다.

#include <iostream>
#include <string>
using namespace std;

void ch(int x){
	if (x>7){
		return;
	}
	else{
		cout<<x<<" ";
		ch(2*x);
		ch(2*x+1);
	}
}

int main(int argc, char** argv) {
	ch(1);
    return 0;
}

 

cout<<x<<" ";의 위치에 따라 달라진다.

 

전위 순회

cout<<x<<" ";
ch(2*x);
ch(2*x+1);

 

중위 순회

cout<<x<<" ";
ch(2*x);
ch(2*x+1);

 

후위 순회

ch(2*x);
ch(2*x+1);
cout<<x<<" ";