#include <iostream>
using namespace std;
struct Cell
{
bool full;
int data;
Cell* left;
Cell* right;
};
bool Add(int step, int data, Cell *&ptr)
{
step--;
if (!ptr)
{
ptr = new Cell;
ptr->full = 0;
ptr->data = 0;
ptr->left = 0;
ptr->right = 0;
}
if (ptr->full)
{
return 1;
}
bool dir = 0;
if (step)
{
dir = Add(step, data, ptr->left);
}
if (dir && step)
{
dir = Add(step, data, ptr->right);
}
if (!ptr->full && !step)
{
ptr->data = data;
ptr->full = 1;
}
return dir;
}
bool Print(Cell *&ptr)
{
bool dir = 0;
if (ptr->full)
{
cout<< ptr->data << endl;
return 1;
}
if (ptr->left)
{
dir = Print(ptr->left);
}
if (dir && ptr->right)
{
dir = Print(ptr->right);
}
return dir;
}
void Del(Cell *&ptr)
{
if (ptr->right)
{
Del(ptr->right);
}
if (ptr->left)
{
Del(ptr->left);
}
delete ptr;
ptr = 0;
}
int main()
{
Cell* root = 0;
Add(2, 1, root);
Add(4, 0, root);
Add(4, 12, root);
Add(5, 2, root);
Add(5, 11, root);
Add(5, 31, root);
Add(6, 21, root);
Print(root);
Del(root);
Add(2, 1, root);
Add(4, 0, root);
Add(4, 12, root);
Add(5, 2, root);
Add(5, 11, root);
Add(5, 31, root);
Add(6, 21, root);
Print(root);
}
