66 lines
1.9 KiB
D
66 lines
1.9 KiB
D
import std.stdio, std.algorithm, std.range, std.string;
|
|
|
|
const struct Tree(T) {
|
|
T value;
|
|
Tree* left, right;
|
|
}
|
|
|
|
alias VisitRange(T) = InputRange!(const Tree!T);
|
|
|
|
VisitRange!T preOrder(T)(in Tree!T* t) /*pure nothrow*/ {
|
|
enum self = mixin("&" ~ __FUNCTION__.split(".").back);
|
|
if (t == null)
|
|
return typeof(return).init.takeNone.inputRangeObject;
|
|
return [*t]
|
|
.chain([t.left, t.right]
|
|
.filter!(t => t != null)
|
|
.map!(a => self(a))
|
|
.joiner)
|
|
.inputRangeObject;
|
|
}
|
|
|
|
VisitRange!T inOrder(T)(in Tree!T* t) /*pure nothrow*/ {
|
|
enum self = mixin("&" ~ __FUNCTION__.split(".").back);
|
|
if (t == null)
|
|
return typeof(return).init.takeNone.inputRangeObject;
|
|
return [t.left]
|
|
.filter!(t => t != null)
|
|
.map!(a => self(a))
|
|
.joiner
|
|
.chain([*t])
|
|
.chain([t.right]
|
|
.filter!(t => t != null)
|
|
.map!(a => self(a))
|
|
.joiner)
|
|
.inputRangeObject;
|
|
}
|
|
|
|
VisitRange!T postOrder(T)(in Tree!T* t) /*pure nothrow*/ {
|
|
enum self = mixin("&" ~ __FUNCTION__.split(".").back);
|
|
if (t == null)
|
|
return typeof(return).init.takeNone.inputRangeObject;
|
|
return [t.left, t.right]
|
|
.filter!(t => t != null)
|
|
.map!(a => self(a))
|
|
.joiner
|
|
.chain([*t])
|
|
.inputRangeObject;
|
|
}
|
|
|
|
void main() {
|
|
alias N = Tree!int;
|
|
const tree = new N(1,
|
|
new N(2,
|
|
new N(4,
|
|
new N(7)),
|
|
new N(5)),
|
|
new N(3,
|
|
new N(6,
|
|
new N(8),
|
|
new N(9))));
|
|
|
|
tree.preOrder.map!(t => t.value).writeln;
|
|
tree.inOrder.map!(t => t.value).writeln;
|
|
tree.postOrder.map!(t => t.value).writeln;
|
|
}
|