Rooted Binary Trees

The following function
DrawTree(t : Tree, title : string)
draws the rooted binary tree specified by t. In Darwin, we can define tree structures using the structured types Tree and Leaf. Here each vertex (node or point) in our Tree structure consists of a left child, a distance from the root of the tree to this vertex and a right child, in that order. The left and right children consist of either another Tree structure or a Leaf structure. A Leaf structure contains a label followed by the distance from it to the root of the tree. The following code creates a Darwin tree for the tree shown in Figure .

> f := Tree(Leaf('A', 33), 18, Leaf('B', 25));
> g := Tree(Leaf('C', 33), 25, Leaf('D', 32));
> h := Tree(g, 6, Leaf('E', 31));
> root := Tree(f, 0, h);

> DrawTree(root, '   A small tree   ');

  

Figure: An example of a rooted tree in Darwin.

Often it is more convenient to draw phylogenetic trees ``upside down''. To accomplish this, we negate the distances of our tree. Figure .

> f := Tree(Leaf('A', -33), -18, Leaf('B', -25));
> g := Tree(Leaf('C', -33), -25, Leaf('D', -32));
> h := Tree(g, -6, Leaf('E', -31));
> root := Tree(f, 0, h);

> DrawTree(root, 'An upside down tree');