[C] 백준 - 5639번: 이진 검색 트리

8월 24일(목) - 트리 (5639번)

5639번: 이진 검색 트리

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 이진 탐색 트리와 관련해서는 insert_node 함수와 new_node 함수는 교재의 풀이를 참고

 

- 입력의 수에 대한 제한이 없으므로, EOF이기 전까지는 계속 입력으로 &data를 받는다

- insert_node와 new_node의 내용은 교재 활용

- 출력은 postorder함수에서 후위순회한 결과를 출력한다

 

12월 30일(금) - 트리 정리

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 1

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

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

typedef struct Treenode {
	int key;
	struct Treenode* left;
	struct Treenode* right;
}Treenode;

Treenode* new_node(int item)
{
	Treenode* tmp = (Treenode*)malloc(sizeof(Treenode));
	tmp->key = item;
	tmp->left = NULL;
	tmp->right = NULL;
	
	return tmp;
}

Treenode* insert_node(Treenode* node, int key)
{
	if (node == NULL)
	{
		return new_node(key);
	}

	else if (key < node->key)
	{
		node->left = insert_node(node->left, key);
	}

	else if (key > node->key)
	{
		node->right = insert_node(node->right, key);
	}

	return node;
}

void postorder(Treenode* root)
{
	if (root != NULL)
	{
		postorder(root->left);
		postorder(root->right);
		printf("%d\n", root->key);
	}
}

int main(void)
{
	int data;
	Treenode* tree = NULL;

	while (scanf("%d", &data) != EOF)
	{
		tree = insert_node(tree, data);
	}

	postorder(tree);
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 2

(풀이출처 -> https://www.acmicpc.net/source/62861407)

#include <stdio.h>
int li[10001];
void post(int l, int r) {
	if (l > r) return;
	int m = r + 1;
	for (int i = l + 1; i <= r; i++) 
		if (li[l] < li[i]) {
			m = i; break;
		}
	post(l + 1, m - 1);
	post(m, r);
	printf("%d\n", li[l]);
}
int main(void) {
	int x, cnt = 0;
	while (scanf("%d", &x) != EOF) li[cnt++] = x;
	post(0, cnt-1);
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ