using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace ConsoleApplication1
{
class Tree: IEnumerable
{
private int[] l;
private int[] r;
private int[] x;
private int head = -1;
private int root = -1;
public Tree(int capacity = 10)
{
this.Capacity = capacity;
Count = 0;
}
public int Capacity
{
get
{
return ((l == null)? 0 : l.Count());
}
private set
{
int size = Capacity;
Array.Resize(ref l, value);
Array.Resize(ref r, value);
Array.Resize(ref x, value);
for (int i = value - 1; i >= size; --i)
{
l[i] = r[i] = -1;
x[i] = head;
head = i;
}
}
}
public int Count
{
get;
private set;
}
private int getRoom()
{
if (head == -1) Capacity *= 2;
int freeplace = head;
head = x[head];
return freeplace;
}
public bool addVertex(int value)
{
if (Count == 0) //root = -1;
{
root = getRoom();
x[root] = value;
return true;
}
int cur = root;
while (true)
{
if (x[cur] == value)
{
return false;
}
if (x[cur] > value)
{
if (l[cur] != -1)
{
cur = l[cur];
}
else
{
l[cur] = getRoom();
x[l[cur]] = value;
return true;
}
}
else
{
if (r[cur] != -1)
{
cur = r[cur];
}
else
{
r[cur] = getRoom();
x[r[cur]] = value;
return true;
}
}
}
}
public void deleteVertex(int value)
{
int cur = root;
while (cur != -1)
{
}
}
public bool containsVertex(int val)
{
int cur = root;
while (cur != -1 && x[cur] != val)
{
cur = ((val < x[cur]) ? l[cur] : r[cur]);
}
return cur != -1;
}
public IEnumerator GetEnumerator()
{
if (root == -1) yield break;
Stack<int> s = new Stack<int>();
s.Push(root);
while (s.Count != 0)
{
int v = s.Peek();
if (l[v] == -1)
{
yield return x[v];
s.Pop();
if (r[v] != -1) s.Push(r[v]);
}
else //l[v] != -1
{
s.Push(l[v]);
}
}
}
}
class Program
{
static void Main(string[] args)
{
}
}
}