5639 이진검색트리

1. 문제분석

 

트리를 전위순회(preorder)한 결과가 주어질 때,

후위순회(postorder)한 결과를 출력한다.

 

      1

2           3

 

있으면

전위순회(preorder) : 1 2 3

후위순회(postorder) : 2 3 1

중위순회(inorder) : 2 1 3 (참고)

 

 

아이디어

"preorder 입력이 주어지는데, 이 순서대로 이진검색트리(이하 BST)에 삽입하면

 BST에 성질에 맞게 입력이 된다. 따라서 이 결과를 preorder로 출력하면 된다."

 

 

2. 시간, 메모리 분석

 

- "노드의 수 10,000개 이하"

  for each node i    // O(N)

      BST_insert(i)    // O(N)

 

 따라서 O(N^2) = 10000 * 10000 = 1억 (1초) OK!

 

- 256MB....

 각 node 1만개를 만들어도, 10000 * 4bytes = 40000

 40000/1024 = 39KB...

 사실 여기에 다른 멤버변수랑 멤버함수도 들어가겠지.. 대략적인 메모리는 어떻게 계산하는지 알고싶다.

 

3. 해결

 

1. 트리 구조체를 만든다.
2. 전위 순회 입력을 이진트리에 입력한다.
3. 입력된 트리를 다시 후위순위로 출력한다.

4. Source code

 

#include <iostream>
using namespace std;

class BSTNode {
private:
	int key;
	BSTNode *l, *r;
public:
	BSTNode(int key=0) {
		this->key = key;
		this->l = NULL; this->r = NULL;
	}
	~BSTNode() { delete l; delete r; }
	int get_key() { return key; }
	void set_key(int key_changed) { this->key = key_changed; }
	BSTNode* get_left() { return l; }
	BSTNode* get_right() { return r; }
	void set_left(int key) { this->l = new BSTNode(key); }
	void set_right(int key) { this->r = new BSTNode(key); }

};

class BST {
private:
	BSTNode *root;
public:
	BST() { root = new BSTNode(); }
	~BST() { delete root; }

	BSTNode* get_root() { return root; }

	// O(N) : worst case
	void insert_node(BSTNode *root, int key) {
		if (root->get_key() == 0) {
			root->set_key(key);
			return;
		}
		if (key < root->get_key()) {
			if (root->get_left() == NULL) root->set_left(key);
			else insert_node(root->get_left(), key);
		}
		else {
			if (root->get_right() == NULL) root->set_right(key);
			else insert_node(root->get_right(), key);
		}
	}
	// O(2N) : 모든 edge의 수(leaf는 2개의 edge가 있다고 가정) = 2 * V
	void postorder(BSTNode *root) {
		if (root == NULL) return;
		postorder(root->get_left());
		postorder(root->get_right());
		printf("%d\n", root->get_key());
	}
};

int main() {
	int n;
	BST *Bst = new BST;
	while (scanf("%d", &n) != EOF) {
		Bst->insert_node(Bst->get_root(), n);
	}
	Bst->postorder(Bst->get_root());
	delete Bst;
	return 0;
}