[백준][C++] 1991번: 트리 순회

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

 

입력된 트리 노드 정보를 통해 전, 중, 후위 순회를 출력하는 문제이다.

 

입력된 노드 정보들로 트리를 만들 수 있느냐가 이 문제에 핵심인 것 같다.

 

두 가지 자료구조로 트리를 만들어줬다.

먼저 배열을 사용해 트리를 만들어봤다.

데이터 타입으로 문자를 저장하는 이차원 배열을 사용해 왼쪽 자식은 이차원의 0번째 인덱스에, 오른쪽 자식은 이차원의 1번째 인덱스에 저장했다. 이렇게 트리를 만들어주고 자식 노드에 '.'도 저장되므로 재귀함수를 통해 '.'를 만나면 재귀함수를 종료해줬다.

 

#include <iostream>

using namespace std;

char nodes[26][2];

void preorder(char s) {
	if(s == '.') return;
	
	cout << s;
	preorder(nodes[s - 'A'][0]);
	preorder(nodes[s - 'A'][1]);
}

void inorder(char s) {
	if(s == '.') return;
	
	inorder(nodes[s - 'A'][0]);
	cout << s;
	inorder(nodes[s - 'A'][1]);
}

void postorder(char s) {
	if(s == '.') return;
	
	postorder(nodes[s - 'A'][0]);
	postorder(nodes[s - 'A'][1]);
	cout << s;
}

int main(void) {
	int N;
	cin >> N;
	
	for(int i=0; i<N; i++) {
		char parent, left, right;
		cin >> parent >> left >> right;
		nodes[parent - 'A'][0] = left;
		nodes[parent - 'A'][1] = right;
	}
	
	preorder('A');
	cout << "\n";
	inorder('A');
	cout << "\n";
	postorder('A');
	cout << "\n";
}

 

 

알게 된 것은 문자를 이용해 인덱싱을 할 수 있다는 것이다.

항상 정수로만 인덱싱을 하여 이 부분을 전혀 떠오를 수 없었는데 문제에서 알파벳 A-Z까지 한정적으로 사용하므로 입력받은 문자를 인덱싱에 사용할 수 있었다.

 

다음은 포인터를 사용해 트리를 만들었다.

여기서 노드 정보를 저장하기위해 node라는 새로운 데이터 타입을 정의해줬고 이 노드들을 연결하여 트리를 만들어주기 위해

node를 가리키는 포인터 변수 treePointer를 정의해 사용했다.

 

#include <iostream>

using namespace std;

typedef struct node *treePointer;
typedef struct node {
	char data;
	treePointer leftChild = NULL, rightChild = NULL;
} node;

void preorder(treePointer ptr) {
	if(ptr) {
		cout << ptr->data;
		preorder(ptr->leftChild);
		preorder(ptr->rightChild);
	}
}

void inorder(treePointer ptr) {
	if(ptr) {
		inorder(ptr->leftChild);
		cout << ptr->data;
		inorder(ptr->rightChild);
	}
}

void postorder(treePointer ptr) {
	if(ptr) {
		postorder(ptr->leftChild);
		postorder(ptr->rightChild);
		cout << ptr->data;
	}
}

int main(void) {
	int n;
	cin >> n;
	node nodes[26];
	
	for(int i=0; i<n; i++) {
		char parent, left, right;
		cin >> parent >> left >> right;
		nodes[parent-'A'].data = parent;
		if(left != '.') nodes[parent-'A'].leftChild = &nodes[left-'A'];
		if(right != '.') nodes[parent-'A'].rightChild = &nodes[right-'A'];
	}
	
	preorder(&nodes[0]);
	cout << endl;
	inorder(&nodes[0]);
	cout << endl;
	postorder(&nodes[0]);
}

 

 

항상 루트 노드인 A부터 순회를 시작하므로 첫 번째 노드의 주소값을 매개변수로 순회를 해주었다.

포인터 변수에 저장된 값은 가리키는 것의 주소값이므로 포인트에 값을 저장하기 위해서는 가리키고 싶은 데이터의 주소값이 있어야 한다. 즉, &연산자 사용!