45 lines
1.1 KiB
D
45 lines
1.1 KiB
D
const struct Node(T) {
|
|
T v;
|
|
Node* l, r;
|
|
}
|
|
|
|
T[] preOrder(T)(in Node!T* t) pure nothrow {
|
|
return t ? t.v ~ preOrder(t.l) ~ preOrder(t.r) : [];
|
|
}
|
|
|
|
T[] inOrder(T)(in Node!T* t) pure nothrow {
|
|
return t ? inOrder(t.l) ~ t.v ~ inOrder(t.r) : [];
|
|
}
|
|
|
|
T[] postOrder(T)(in Node!T* t) pure nothrow {
|
|
return t ? postOrder(t.l) ~ postOrder(t.r) ~ t.v : [];
|
|
}
|
|
|
|
T[] levelOrder(T)(in Node!T* t) pure nothrow {
|
|
static T[] loop(in Node!T*[] a) pure nothrow {
|
|
if (!a.length) return [];
|
|
if (!a[0]) return loop(a[1 .. $]);
|
|
return a[0].v ~ loop(a[1 .. $] ~ [a[0].l, a[0].r]);
|
|
}
|
|
return loop([t]);
|
|
}
|
|
|
|
void main() {
|
|
alias N = Node!int;
|
|
auto 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))));
|
|
|
|
import std.stdio;
|
|
writeln(preOrder(tree));
|
|
writeln(inOrder(tree));
|
|
writeln(postOrder(tree));
|
|
writeln(levelOrder(tree));
|
|
}
|