dranges.treerange

class Tree (T);

The basic node for a binary tree.

T t ;

Value stored on the node.

Tree!(T) left ;
Tree!(T) right ;

children

Tree!(T) tree (T)(T t);

Helper function to create a Tree!T with no child (a leaf).

Tree!(T) tree (T)(T t, Tree!(T) l, Tree!(T) r);

To create a Tree!T with children.

class NTree (T);

The basic node for a n-ary tree.

NTree!(T) ntree (T)(T t);

Helper function to create a NTree!T with no child (a leaf).

NTree!(T) ntree (T, R)(T t, R c);

To create a NTree!T with children.

bool isLeaf (T)(Tree!(T) t);

predicate to see if a node is a leaf (a node without children).

I reduceTree (alias fun, I, T)(I ifNull, Tree!(T) tr);

Reduce on a tree: recursively apply fun on the value and the children, to obtain a unique result.

int height (T)(Tree!(T) tr);
T[] preOrder (T)(Tree!(T) tr);
T[] inOrder (T)(Tree!(T) tr);
T[] postOrder (T)(Tree!(T) tr);
T max (T)(Tree!(T) tr);
T min (T)(Tree!(T) tr);
I opTree (string op, I, T)(I ifNull, Tree!(T) tr);

Small functions (one-liners) that use reduceTree, to calculate, respectively:

• The height (depth) of a binary tree
• The values in found in a depth-first pre-order iteration. They are returned as an array.
• The values in found in a depth-first in-order iteration. They are returned as an array.
• The values in found in a depth-first post-order iteration. They are returned as an array.
• The maximum value held by a node.
• The minimum value held by a node.
• The result of applying an binary operation on the node's value and the values given by treeReduce on the children (see the examples)

reduceTree is a greedy algorithm.

Examples:

auto t0 = tree(0);
auto t1 = tree(1, t0, tree(2));
auto t3 = tree(3, t1, tree(4));
//  t3 is:
//              3
//             / \
//            1   4
//           / \
//          0   2
assert(height(t3) == 3);
assert(preOrder(t3) == [3,1,0,2,4]);
assert(inOrder(t3) == [0,1,2,3,4]);
assert(postOrder(t3) == [0,2,1,4,3]);
assert(max(t3) == 4);
assert(min(t3) == 0);
assert(opTree!"+"(0,t3) == 3+1+4+2+0);

void transform (alias fun, T)(ref Tree!(T) tr);

Applies function fun to the values of node and then recursively to the children. It transforms the Tree in place.

TODO:
Maybe another version that can act on the entire Node, modifying the tree's structure.

enum TraversalMode ;

A enum that control the mode of traversal on a tree

Traversal!(tm,T) traversal (TraversalMode tm = TraversalMode.depthfirst, T)(T treelike);

Returns a range to iterate on a tree nodes. The mode of traversal is a template parameter and can be depthfirst (the default) or breadthfirst.

Note:
it iterates on the tree nodes, not the content of the nodes. Maybe I should change this.

Usage:

auto depthf = traversal(t);
auto breadthf = travseral!(TraversalMode.breadthfirst)(t);

AsTrie!(T) asTrie (T)(Tree!(T) tree);

Produces a range to iterate in a standard tree as if it was a trie: the elements are arrays of all elements traversed from the root to the current focus of iteration.

Example:

// t3 is the same tree used before for heigth/preorder, etc.
//
//              3
//             / \
//            1   4
//           / \
//          0   2
auto trie = asTrie(t3);
auto values = map!("array(map!\"a.t\"(a))")(trie); // The strange double map is to convert the nodes ot their values.
assert(equal(values, [[3], [3,1], [3,1,0], [3,1,2], [3,4]]));