#include <stdio.h>
#define NIL (0)
class TreeNode {
public:
	TreeNode *left;
	TreeNode *right;
	int data;
	TreeNode(int x,TreeNode *root) {
		if (root == NIL) {
			left = this; right = this;
		} else {
			left = root; right = root;
		}
		data = x;
	}
	void insert(int x,TreeNode *root);
	void print();
};
class Tree {
public:
	TreeNode *root;
	Tree() { root = NIL; }
	void insert(int x) {
		if (root == NIL) {
			root = new TreeNode(x,NIL);
			return;
		}
		root->insert(x,root);
	}
	void print() {
		root->print();
	}
};
void TreeNode::insert(int x,TreeNode *root)
{
	if (x%2 == 0) {
		if (right == root) {
			right = new TreeNode(x,root);
		} else {
			right->insert(x,root);
		}
	} else {
		if (left == root) {
			left = new TreeNode(x,root);
		} else {
			left->insert(x,root);
		}
	}
}
void TreeNode::print()
{
	TreeNode *node = this;
	for (int i = 0 ; i < 5; i++) {
		printf("%d\n",node->data);
		node = node->right;
	}
}
void main()
{
	Tree *pTree = new Tree();
	int key[5] = { 0, 1, 2, 3, 4 }; // key °ª ´ëÄ¡
	for(int i = 0; i < 5; i++) {
		pTree->insert(key[i]);
	}
	pTree->print();
}