[BOJ1991] 트리 순회

[BOJ1991] 트리 순회

문제 링크

문제 설명

• 트리의 노드들을 입력 받고 전위, 중위, 후위 순회를 한 결과를 출력하는 문제이다.
• 노드의 개수를 처음에 입력 받고, 그 개수만큼 노드의 값, 그 노드의 왼쪽 노드 값, 오른쪽 노드 값을 입력받는다.
• 만약 왼쪽이나 오른쪽 자식으로 노드가 없다면 . 을 입력 받는다.

코드 리뷰

• 동적할당과 리스트로 구현하는 것을 매번 연습 중인데, 현재노드의 값을 입력받으며 동시에 왼쪽 자식 노드, 오른쪽 자식 노드의 값까지 입력받다보니 동적할당 받기가 난해했다. 그래서 처음 노드의 개수만큼 노드들을 동적할당 받아두고, next 포인터변수로 연결시켜 놨다.
• 그 후 노드 개수만큼 노드값들을 입력받을때, 자식노드들을 연결시켰다.
• 전위, 중위, 후위 순회 순으로 출력을 하므로 후위순회를 하면서 노드들을 동적할당해제 시켰다.
• 전위,중위,후위 순회에 대한 설명은 어느 자료구조책에나 기본으로 다 나오는 개념이므로 생략하겠다.

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

typedef struct _treenode{
	char c;
	_treenode *left;
	_treenode *right;
	_treenode *next;
}treenode;

typedef struct {
	treenode *root;
	treenode *cur;
}Tree;

void preorder(treenode * plist) {
	cout << plist->c;
	if(plist->left != NULL) preorder(plist->left);
	if(plist->right != NULL) preorder(plist->right);	
}
void inorder(treenode * plist) {
	if (plist->left != NULL) inorder(plist->left);
	cout << plist->c;
	if (plist->right != NULL) inorder(plist->right);
}
void postorder(treenode * plist) {
	if (plist->left != NULL) postorder(plist->left);
	if (plist->right != NULL) postorder(plist->right);
	cout << plist->c;
	free(plist);
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N;
	cin >> N;
	Tree *tree = (Tree*)malloc(sizeof(Tree));
	tree->root = NULL; tree->cur = NULL;
	for (int n = 0; n < N; n++) {
		if (n == 0) {
			treenode *newnode = (treenode*)malloc(sizeof(treenode));
			tree->root = newnode;
			tree->cur = newnode;
			newnode->c = 'A';
		}
		else {
			treenode *newnode = (treenode*)malloc(sizeof(treenode));
			tree->cur->next = newnode;
			tree->cur = newnode;
			newnode->c = 'A' + n;
		}
	}
	tree->cur->next = NULL;
	for (int n = 0; n < N; n++) {
		tree->cur = tree->root;
		char ctmp, ltmp, rtmp;
		cin >> ctmp >> ltmp >> rtmp;
		while(1) {
			if (tree->cur->c == ctmp) {
				break;
			}
			tree->cur = tree->cur->next;
		}
		treenode *tmp = tree->cur;
		tree->cur = tree->root;
		if (ltmp != '.' && rtmp != '.') {
			while (tree->cur != NULL) {
				if (tree->cur->c == ltmp) {
					tmp->left = tree->cur;
					break;
				}
				tree->cur = tree->cur->next;
			}
			tree->cur = tree->root;
			while (tree->cur != NULL) {
				if (tree->cur->c == rtmp) {
					tmp->right = tree->cur;
					break;
				}
				tree->cur = tree->cur->next;
			}
		}
		else if (ltmp == '.' && rtmp != '.') {
			tmp->left = NULL;
			while (tree->cur != NULL) {
				if (tree->cur->c == rtmp) {
					tmp->right = tree->cur;
					break;
				}
				tree->cur = tree->cur->next;
			}
		}
		else if (ltmp != '.' && rtmp == '.') {
			tmp->right = NULL;
			while (tree->cur != NULL) {
				if (tree->cur->c == ltmp) {
					tmp->left = tree->cur;
					break;
				}
				tree->cur = tree->cur->next;
			}
		}
		else {
			tmp->left = NULL;
			tmp->right = NULL;
		}
	}
	preorder(tree->root);
	cout << "\n";
	inorder(tree->root);
	cout << "\n";
	postorder(tree->root);
	cout << "\n";
	free(tree);
	return 0;
}