6. 전위순회, 중위순회, 후위순회

 

    6번 문제   

 

 

---

 

    내가 풀이한 답   

 

• 전위순회(Preorder): 부모노드를 먼저 방문하고 자식 노드를 방문
• 중위순회(Inorder): 왼쪽 자식을 먼저 방문하고 부모노드를 방문
• 후위순회(Postorder): 자식 노드를 먼저 방문하고 부모노드를 방문

 

 

 

 위의 그림과 같이 각 노드의 왼쪽에 있는 빨간색 점을 선으로 쭉 이어보면 전위순회가 완성된다. 중위순회와 후위순회도 마찬가지로 각각 초록색, 파란색 점을 선으로 이어보면 구할 수 있다.  

#include <iostream>
using namespace std;
 
//전위순회
void pre(int v, int n){
	if(v > n) return;
	else {
		cout << v << " ";
		pre(v*2, n);
		pre(v*2+1, n);
	}
}
 
//중위순회
void mid(int v, int n){
	if(v > n) return;
	else {
		mid(v*2, n);
		cout << v << " ";
		mid(v*2+1, n);
	}
}
 
//후위순회
void aft(int v, int n){
	if(v > n) return;
	else {
		aft(v*2, n);
		aft(v*2+1, n);
		cout << v << " ";
	}
}
 
int main() {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	
	int n;
	cin >> n;
	
	pre(1, n);
	cout << endl;
	mid(1, n);
	cout << endl;
	aft(1, n);
 
	return 0;
}

 

 

---

 

    사이트의 답안   

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;	
void D(int x){
	if(x>7) return;
	else{
		printf("%d ", x);
		D(x*2);
		D(x*2+1);
	}
}	
int main(){
	freopen("input.txt", "rt", stdin);
	D(1);
	return 0;
}