[백준 / C언어] 1991번: 트리 순회

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

1991번: 트리 순회

 

난이도: solved.ac 실버 1

 

 

처음엔 배열을 이용해 트리를 만드려다가 트리가 한쪽으로 쏠려있는 경우에 배열의 크기가 2^26 - 1가 될 수 있으므로 Linked List(연결리스트)로 만들어주었다

 

그리고 두 가지 방식으로 풀어보았는데 두 코드 모두 아래의 순서로 진행된다

 

1) root 노드를 따로 만들어줌

2) 나머지 자식 노드들을 만들어 tree에 연결시켜 줌

3) preoreder, inorder, postorder로 탐색해 각각 출력해 줌

 

 

1. 첫 번째 방식: 자식 노드가 없는 상태인 '.'도 '.'가 저장되어 있는 노드로 만들었을 때

#include<stdio.h>
#include<stdlib.h>

typedef struct _Node {
	char alph;
	struct _Node* left;
	struct _Node* right;
} Node;

Node* MakeNode(char);
int Find(Node* node, Node* new);
void preorder(Node* node);
void inorder(Node* node);
void postorder(Node* node);

int main() {
	int N, i;
	scanf("%d", &N);

	char parent, l_child, r_child;
	scanf(" %c %c %c", &parent, &l_child, &r_child);
	Node* root = MakeNode(parent);
	Node* left = MakeNode(l_child);
	Node* right = MakeNode(r_child);
	root->left = left;
	root->right = right;
	
	for (i = 1; i < N; i++) {
		scanf(" %c %c %c", &parent, &l_child, &r_child);
		Node* new = MakeNode(parent);
		Node* left = MakeNode(l_child);
		Node* right = MakeNode(r_child);
		new->left = left;
		new->right = right;
		Find(root, new);
	}
	preorder(root);
	printf("\n");
	inorder(root);
	printf("\n");
	postorder(root);
	return 0;
}

Node* MakeNode(char parent) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->alph = parent;
	newNode->left = NULL;
	newNode->right = NULL;
	return newNode;
}

int Find(Node* node, Node* new) {
	if (node->left == NULL)
		return 0;
	if (node->right == NULL)
		return 0;
	if (node->left->alph == new->alph) {
		free(node->left);
		node->left = new;
	}
	else if (node->right->alph == new->alph) {
		free(node->right);
		node->right = new;
	}
	else {
		if(node->left->alph != '.')
			Find(node->left, new);
		if (node->right->alph != '.')
			Find(node->right, new);
	}
}

void preorder(Node* node) {
	printf("%c", node->alph);
	if(node->left->alph != '.')
		preorder(node->left);
	if (node->right->alph != '.')
		preorder(node->right);
}

void inorder(Node* node) {
	if (node->left->alph != '.')
		inorder(node->left);
	printf("%c", node->alph);
	if (node->right->alph != '.')
		inorder(node->right);
}

void postorder(Node* node) {
	if (node->left->alph != '.')
		postorder(node->left);
	if (node->right->alph != '.')
		postorder(node->right);
	printf("%c", node->alph);
}

 

 

2. 두 번째 방식: 자식 노드가 없는 상태인 '.'를 NULL로 만들었을 때

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

typedef struct _Node {
	char alph;
	struct _Node* left;
	struct _Node* right;
} Node;

Node* MakeNode(char);
int connect(Node* node, Node* new);
void preorder(Node* node);
void inorder(Node* node);
void postorder(Node* node);

int main() {
	int N, i;
	scanf("%d", &N);
	getchar();
	char parent, l_child, r_child;
	scanf("%c %c %c", &parent, &l_child, &r_child);
	getchar();

	/* 첫 root 노드 삽입 */
	Node* root = MakeNode(parent);
	if (l_child != '.') {
		Node* left = MakeNode(l_child);
		root->left = left;
	}
	if (r_child != '.') {
		Node* right = MakeNode(r_child);
		root->right = right;
	}

	for (i = 1; i < N; i++) {
		scanf("%c %c %c", &parent, &l_child, &r_child);
		getchar();
		Node* new = MakeNode(parent);
		if (l_child != '.') {
			Node* left = MakeNode(l_child);
			new->left = left;
		}
		if (r_child != '.') {
			Node* right = MakeNode(r_child);
			new->right = right;
		}
		connect(root, new);
	}
	preorder(root);
	printf("\n");
	inorder(root);
	printf("\n");
	postorder(root);
	return 0;
}

Node* MakeNode(char parent) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->alph = parent;
	newNode->left = NULL;
	newNode->right = NULL;
	return newNode;
}

int connect(Node* node, Node* new) {
	if (node->left != NULL) {
		if (node->left->alph == new->alph) {
			free(node->left);
			node->left = new;
		}
		else
			connect(node->left, new);
	}
	if (node->right != NULL) {
		if (node->right->alph == new->alph) {
			free(node->right);
			node->right = new;
		}
		else
			connect(node->right, new);
	}
}

void preorder(Node* node) {
	printf("%c", node->alph);
	if (node->left != NULL)
		preorder(node->left);
	if (node->right != NULL)
		preorder(node->right);
}

void inorder(Node* node) {
	if (node->left != NULL)
		inorder(node->left);
	printf("%c", node->alph);
	if (node->right != NULL)
		inorder(node->right);
}

void postorder(Node* node) {
	if (node->left != NULL)
		postorder(node->left);
	if (node->right != NULL)
		postorder(node->right);
	printf("%c", node->alph);
}