77 lines
2.1 KiB
D
77 lines
2.1 KiB
D
import std.stdio, std.traits;
|
|
|
|
const final class Node(T) {
|
|
T data;
|
|
Node left, right;
|
|
|
|
this(in T data, in Node left=null, in Node right=null)
|
|
const pure nothrow {
|
|
this.data = data;
|
|
this.left = left;
|
|
this.right = right;
|
|
}
|
|
}
|
|
|
|
// 'static' templated opCall can't be used in Node
|
|
auto node(T)(in T data, in Node!T left=null, in Node!T right=null)
|
|
pure nothrow {
|
|
return new const(Node!T)(data, left, right);
|
|
}
|
|
|
|
void show(T)(in T x) {
|
|
write(x, " ");
|
|
}
|
|
|
|
enum Visit { pre, inv, post }
|
|
|
|
// 'visitor' can be any kind of callable or it uses a default visitor.
|
|
// TNode can be any kind of Node, with data, left and right fields,
|
|
// so this is more generic than a member function of Node.
|
|
void backtrackingOrder(Visit v, TNode, TyF=void*)
|
|
(in TNode node, TyF visitor=null) {
|
|
alias trueVisitor = Select!(is(TyF == void*), show, visitor);
|
|
if (node !is null) {
|
|
static if (v == Visit.pre)
|
|
trueVisitor(node.data);
|
|
backtrackingOrder!v(node.left, visitor);
|
|
static if (v == Visit.inv)
|
|
trueVisitor(node.data);
|
|
backtrackingOrder!v(node.right, visitor);
|
|
static if (v == Visit.post)
|
|
trueVisitor(node.data);
|
|
}
|
|
}
|
|
|
|
void levelOrder(TNode, TyF=void*)
|
|
(in TNode node, TyF visitor=null, const(TNode)[] more=[]) {
|
|
alias trueVisitor = Select!(is(TyF == void*), show, visitor);
|
|
if (node !is null) {
|
|
more ~= [node.left, node.right];
|
|
trueVisitor(node.data);
|
|
}
|
|
if (more.length)
|
|
levelOrder(more[0], visitor, more[1 .. $]);
|
|
}
|
|
|
|
void main() {
|
|
alias N = node;
|
|
const tree = N(1,
|
|
N(2,
|
|
N(4,
|
|
N(7)),
|
|
N(5)),
|
|
N(3,
|
|
N(6,
|
|
N(8),
|
|
N(9))));
|
|
|
|
write(" preOrder: ");
|
|
tree.backtrackingOrder!(Visit.pre);
|
|
write("\n inorder: ");
|
|
tree.backtrackingOrder!(Visit.inv);
|
|
write("\n postOrder: ");
|
|
tree.backtrackingOrder!(Visit.post);
|
|
write("\nlevelorder: ");
|
|
tree.levelOrder;
|
|
writeln;
|
|
}
|