Logo

Programming-Idioms

  • Perl
  • Erlang

Idiom #9 Create a Binary Tree data structure

The structure must be recursive because left child and right child are binary trees too. A node has access to children nodes, but not to its parent.

-type binary_tree(T) ::
	#{ data := T
	 , left := binary_tree(T)
	 , right := binary_tree(T)
	 }.

We just define the type here. Next step would be to implement a module with the required functions to access it and even make it opaque.
use Moops;
class Tree::Binary {
    has 'left', is => 'ro', isa => Maybe[InstanceOf['Tree::Binary']];
    has 'right', is => 'ro', isa => Maybe[InstanceOf['Tree::Binary']];
    has 'val', is => 'ro', isa => Int;
}
my $t = Tree::Binary->new(
    val => 42,
    left => Tree::Binary->new(val => 23),
    right => Tree::Binary->new(
        val => 1729,
        right => Tree::Binary->new(val => -1)
    )
);
__END__
      42
    ↙    ↘
  23     1729
 ↙  ↘   ↙    ↘
∅    ∅ ∅     -1
type Tree_Node;
type Tree_Node_Access is access Tree_Node;
type Tree_Node is record
   Value: Integer;
   Left, Right: Tree_Node_Access;
end record;

New implementation...
< >
programming-idioms.org