Algorithm/C++

[백준 BoJ] 1991 - 트리 순회

cgy12306 2021. 8. 4. 16:59
// https://www.acmicpc.net/problem/1991
// 트리 순회

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

typedef struct TreeNode{
	char name;
	struct TreeNode *left;
	struct TreeNode *right;
}TreeNode;

TreeNode *init(char name) {
	TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
	if (node == NULL) return NULL;
	node->name = name;
	node->left = NULL;
	node->right = NULL;
	return node;
}

void insert(TreeNode *node, char name, char right, char left) {
	if (right == '.') node->right = NULL;
	else node->right = init(right);

	if (left == '.') node->left = NULL;
	else node->left = init(left);
}

TreeNode *search(TreeNode *node, char name) {
	if (node == NULL) return NULL;
	if (node->name == name) {
		return node;
	}
	else {
		TreeNode *tmp = search(node->left, name);
		if (tmp) return tmp;
		tmp = search(node->right, name);
		return tmp;
	}
	return NULL;
}

void preorder(TreeNode *node) {
	cout << node->name;
	if(node->left)preorder(node->left);
	if(node->right)preorder(node->right);
}

void inorder(TreeNode *node) {
	if (node->left)inorder(node->left);
	cout << node->name;
	if (node->right)inorder(node->right);
}
void postorder(TreeNode *node) {
	if (node->left)postorder(node->left);
	if (node->right)postorder(node->right);
	cout << node->name;
}

void freedom(TreeNode *node) {
	if (node != NULL) {
		freedom(node->left);
		freedom(node->right);
		free(node);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;

	TreeNode *root;
	root = NULL;

	for (int i = 0; i < N; i++) {
		char name, right, left;
		cin >> name >> left >> right;
		if (root == NULL) {
			root = init(name);
			insert(root, name, right, left);
		}
		else {
			TreeNode *node = search(root, name);
			insert(node, name, right, left);
		}
	}

	preorder(root);
	cout << "\n";
	inorder(root);
	cout << "\n";
	postorder(root);

	freedom(root);
}

search 함수에서 return을 제대로 해주지 않으면 메모리 초과가 발생함