[BOJ5639] 이진 검색 트리

[BOJ5639] 이진 검색 트리

문제 링크

문제설명

• 전위순회로 주어진 노드 키값을 통해, 후위순회로 노드 키값을 출력하는 문제이다.
• scanf에서 EOF 사용법이 필요한 문제였다.

코드리뷰

• 그동안 이진탐색트리를 공부한 부분에 대해 복습하기 위해 풀어본 문제로, 배열을 이용해서도 쉽고 빠르게 풀 수 있지만, 동적할당과 포인터를 이용하여 트리를 직접 구현하여 풀었다.
• 노드의 개수가 최대 10000개였고, 이진탐색트리의 삽입연산을 최악의 경우로 계속 수행한다하여도 1초안에 충분히 나올 수 있다는 계산을 하였고, 삽입 연산을 이용하여 트리를 만들었다.
• 루트에서 시작하여 계속해서 데이터 값을 받을 때마다 노드 삽입 연산을 진행하였다.
• 그 후, 동적할당 해제는 후위순회를 하면서 데이터값을 출력할때 마다 해주었다.

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

typedef struct _tree {
	_tree *parent;
	_tree *lnext;
	_tree *rnext;
	int data;
}Tree;

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

void postorder(Tree * tmp) {
	if (tmp == NULL) return;
	postorder(tmp->lnext);
	postorder(tmp->rnext);
	printf("%d\n", tmp->data);
	free(tmp);
}

int main() {
	int tmp;
	Treepoint * newtree = (Treepoint*)malloc(sizeof(Treepoint));
	newtree->cur = NULL; newtree->root = NULL; 
	while (scanf("%d", &tmp) != EOF) {
		Tree * newnode = (Tree*)malloc(sizeof(Tree));
		if (newtree->root == NULL) { //루트
			newnode->data = tmp;
			newnode->lnext = NULL;
			newnode->rnext = NULL;
			newnode->parent = NULL;
			newtree->root = newnode;
			newtree->cur = newnode;
		}
		else if (newtree->root != NULL) {
			Tree * ppos = NULL;
			while (1) {
				if (tmp < newtree->cur->data) {
					if (newtree->cur->lnext == NULL) {
						newnode->data = tmp;
						newnode->lnext = NULL;
						newnode->rnext = NULL;
						ppos = newtree->cur;
						ppos->lnext = newnode;
						break;
					}
					newtree->cur = newtree->cur->lnext;
				}
				else if (tmp > newtree->cur->data) {
					if (newtree->cur->rnext == NULL) {
						newnode->data = tmp;
						newnode->lnext = NULL;
						newnode->rnext = NULL;
						ppos = newtree->cur;
						ppos->rnext = newnode;
						newnode->parent = ppos;
						break;
					}
					newtree->cur = newtree->cur->rnext;
				}
			}
			newtree->cur = newtree->root;
		}
	}
	postorder(newtree->root);
	free(newtree);
	return 0;
}