[백준] 1991번 트리 순회 (C++) - preorder, inorder, postorder

발상

트리 순회에는 전위 순회 (postorder), 중위 순회 (inorder), 후위 순회 (postorder) 이 있다.

전위 순회 : node -> left -> right

중위 순회 : left -> node -> right

후위 순회 : left -> right -> node

모두 node 자신의 방문순서를 기준으로 생각하면 된다. 

 

각각의 수도코드는 다음과 같다. 

<postorder>

void postorder{
	cout << node->char;
	if(node->left != NULL) postorder(node->left);
    	if(node->right != NULL) postorder(node->right);
}

<inorder>

void inorder{
	if(node->left != NULL) inorder(node->left);
   	cout << node->char;
    	if(node->right != NULL) inorder(node->right);
}

<postorder>

void inorder{
	if(node->left != NULL) inorder(node->left);
    	if(node->right != NULL) inorder(node->right);
        cout << node->char;
}

 

*포인터 개념 복습

& : 주소 연산자 : 변수 앞에 붙을 경우, 해당 변수의 주소값을 반환함.

* : 참조 연산자 : 변수값 또는 주소 앞에 붙어 해당하는 값을 반환함. 포인터 선언 시에 사용하기도 함

 

선언 : 타입* 포인터이름 = &해당변수이름 / 타입* 포인터이름 = 해당주소값

소스코드

#include <iostream>
#include <vector>

using namespace std;

struct node{
	char c;
	node* left = NULL;
	node* right = NULL;
};
void preorder(node* A){
	cout << A->c;
	if(A->left != NULL) preorder(A->left);
	if(A->right != NULL) preorder(A->right);
}
void inorder(node* A){
	if(A->left != NULL) inorder(A->left);
	cout << A->c;
	if(A->right != NULL) inorder(A->right);
}
void postorder(node* A){
	if(A->left != NULL) postorder(A->left);
	if(A->right != NULL) postorder(A->right);
	cout << A->c;
}
int main(){
	cin.tie(NULL); ios::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<node> nod(26);
	node *root;
	
	for(int i=0; i<N; i++){
		char left, right, me;
		cin >> me >> left >> right;
		nod[me-'A'].c = me; 
		if(left != '.') nod[me-'A'].left = &nod[left-'A'];
		if(right != '.') nod[me-'A'].right = &nod[right-'A'];
	}
	preorder(&nod[0]);
	cout << "\n";
	inorder(&nod[0]);
	cout << "\n";
	postorder(&nod[0]);
	return 0;
}

 

포인터와 구조체를 사용하여 해결하였다. (풀이에 https://eunchanee.tistory.com/260 를 참고하였음을 밝힌다.)

상세히 살펴보면 다음과 같다. 

 

struct node{
	char c;
	node* left = NULL;
	node* right = NULL;
};

우선 구조체로 node를 선언했다. 3가지 요소가 있다.

우선 해당 값을 저장하는 char c, left node의 '주소' 를 저장하는 포인터 변수 left (자료형 node), 마찬가지로 right node의 주소를 저장하는 포인터 변수 right (자료형 node). 

 

void preorder(node* A){
	cout << A->c;
	if(A->left != NULL) preorder(A->left);
	if(A->right != NULL) preorder(A->right);
}
void inorder(node* A){
	if(A->left != NULL) inorder(A->left);
	cout << A->c;
	if(A->right != NULL) inorder(A->right);
}
void postorder(node* A){
	if(A->left != NULL) postorder(A->left);
	if(A->right != NULL) postorder(A->right);
	cout << A->c;
}

preorder, inorder, postorder 함수 부분이다. 윗부분 수도코드와 같은 형태이다. 

->는 구조체 포인터에 접근할 때 사용하는 연산자이다. 이를 통해서 *A에서 바로 접근할 수 있다. 

변수로 node* A, 즉 A의 주소값을 받는다. 이것을 이용해 A 내부의 요소에 접근할 수 있다. 

 

int main(){
	cin.tie(NULL); ios::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<node> nod(26);
	
	for(int i=0; i<N; i++){
		char left, right, me;
		cin >> me >> left >> right;
		nod[me-'A'].c = me; 
		if(left != '.') nod[me-'A'].left = &nod[left-'A'];
		if(right != '.') nod[me-'A'].right = &nod[right-'A'];
	}
	preorder(&nod[0]);
	cout << "\n";
	inorder(&nod[0]);
	cout << "\n";
	postorder(&nod[0]);
	return 0;
}

마지막으로 메인함수이다.

우선 N값을 받고, <node> 가 삽입되는 크기가 26인 vector를 선언한다. (알파벳이 26개이기 때문. 각 번호의 vector은 해당 알파벳 node 값을 저장한다.) 

 

for문을 이용해서 모든 node의 값을 받아주고, me, left, right 값을 해당 nod[me-'A'] 의 알맞은 요소에 할당해준다. 이 때 left, right 값은 주소를 할당해 주어야 하므로 &를 붙여준다. 

 

마지막으로 각각의 함수를 실행시키면 끝. 이 때도 마찬가지로 함수의 변수가 주소값이므로 &를 붙인 root, nod[0] 값을 넣어 주어야 한다.