121 lines
2.8 KiB
Text
121 lines
2.8 KiB
Text
import extensions;
|
|
import extensions'routines;
|
|
import system'collections;
|
|
|
|
singleton DummyNode
|
|
{
|
|
get generic()
|
|
= EmptyEnumerable;
|
|
}
|
|
|
|
class Node
|
|
{
|
|
rprop int Value;
|
|
rprop Node Left;
|
|
rprop Node Right;
|
|
|
|
constructor new(int value)
|
|
{
|
|
Value := value
|
|
}
|
|
|
|
constructor new(int value, Node left)
|
|
{
|
|
Value := value;
|
|
Left := left;
|
|
}
|
|
|
|
constructor new(int value, Node left, Node right)
|
|
{
|
|
Value := value;
|
|
Left := left;
|
|
Right := right
|
|
}
|
|
|
|
Preorder = new Enumerable::
|
|
{
|
|
Enumerator enumerator() = CompoundEnumerator.new(
|
|
SingleEnumerable.new(Value),
|
|
(Left ?? DummyNode).Preorder,
|
|
(Right ?? DummyNode).Preorder);
|
|
};
|
|
|
|
Inorder = new Enumerable::
|
|
{
|
|
Enumerator enumerator()
|
|
{
|
|
if (nil != Left)
|
|
{
|
|
^ CompoundEnumerator.new(Left.Inorder, SingleEnumerable.new(Value), (Right ?? DummyNode).Inorder)
|
|
}
|
|
else
|
|
{
|
|
^ SingleEnumerable.new(Value).enumerator()
|
|
}
|
|
}
|
|
};
|
|
|
|
Postorder = new Enumerable::
|
|
{
|
|
Enumerator enumerator()
|
|
{
|
|
if (nil == Left)
|
|
{
|
|
^ SingleEnumerable.new(Value).enumerator()
|
|
}
|
|
else if (nil == Right)
|
|
{
|
|
^ CompoundEnumerator.new(Left.Postorder, SingleEnumerable.new(Value))
|
|
}
|
|
else
|
|
{
|
|
^ CompoundEnumerator.new(Left.Postorder, Right.Postorder, SingleEnumerable.new(Value))
|
|
}
|
|
}
|
|
};
|
|
|
|
LevelOrder = new Enumerable::
|
|
{
|
|
Queue<Node> queue := class Queue<Node>.allocate(4).push:self;
|
|
|
|
Enumerator enumerator() = new Enumerator::
|
|
{
|
|
bool next() = queue.isNotEmpty();
|
|
|
|
get()
|
|
{
|
|
Node item := queue.pop();
|
|
Node left := item.Left;
|
|
Node right := item.Right;
|
|
|
|
if (nil != left)
|
|
{
|
|
queue.push(left)
|
|
};
|
|
if (nil != right)
|
|
{
|
|
queue.push(right)
|
|
};
|
|
|
|
^ item.Value
|
|
}
|
|
|
|
reset()
|
|
{
|
|
NotSupportedException.raise()
|
|
}
|
|
|
|
enumerable() = queue;
|
|
};
|
|
};
|
|
}
|
|
|
|
public program()
|
|
{
|
|
var tree := Node.new(1, Node.new(2, Node.new(4, Node.new(7)), Node.new(5)), Node.new(3, Node.new(6, Node.new(8), Node.new(9))));
|
|
|
|
console.printLine("Preorder :", tree.Preorder);
|
|
console.printLine("Inorder :", tree.Inorder);
|
|
console.printLine("Postorder :", tree.Postorder);
|
|
console.printLine("LevelOrder:", tree.LevelOrder)
|
|
}
|