#include <iostream>
template <class Value>
struct AbstractTreeElement
{
virtual AbstractTreeElement<Value>* Insert(Value) = 0;
virtual void Print() = 0;
};
template <class Value>
struct TreeNode : AbstractTreeElement<Value>
{
Value value;
AbstractTreeElement<Value>* left;
AbstractTreeElement<Value>* right;
TreeNode(Value value, AbstractTreeElement<Value>* left, AbstractTreeElement<Value>* right)
: value(value), left(left), right(right) { }
TreeNode<Value>* Insert(Value inserted) override
{
if (inserted < value)
{
left = left->Insert(inserted);
return this;
}
if (value < inserted)
{
right = right->Insert(inserted);
return this;
}
//inserted == value, and then
//throw new std::exception(".!.");
//or dont react to this
return this;
}
void Print() override
{
left->Print();
std::cout << value << " ";
right->Print();
}
};
template <class Value>
struct EmptyNode : AbstractTreeElement<Value>
{
TreeNode<Value>* Insert(Value insertedValue) override
{ return new TreeNode<Value>(insertedValue, new EmptyNode<Value>(), this); }
void Print() override { }
};
template <class Value>
struct Tree
{
AbstractTreeElement<Value>* root;
Tree() : root(new EmptyNode<Value>) { }
void Insert(Value value)
{
root = root->Insert(value);
}
void Print()
{
root->Print();
}
};
int main()
{
Tree<int> tree;
tree.Insert(4);
tree.Insert(6);
tree.Insert(1);
tree.Insert(5);
tree.Insert(2);
tree.Insert(3);
tree.Insert(0);
tree.Print();
return 0;
}
