Drawing Binary Trees

The first example is an applet for drawing binary trees. We will understand through this example the following concepts: constraint definitions and unification of components. This example also illustrates how small components can be combined to build larger ones. The following shows the code for drawing the tree as depicted in Figure (a):

class Tree {
     dj Circle root, lc, rc;
     dj Line l1,l2;

     sameSize({root,lc,rc});
     positionNodes(root,lc,rc);
     l1.point1==root.center;
     l1.point2==lc.center;
     l2.point1==root.center;
     l2.point2==rc.center;
 }

 constraint positionNodes(Circle root, Circle lc, Circle rc){
     root.centerX == (lc.centerX + rc.centerX)/2; 
                            // symmetric
     left(lc,rc);
     lc.centerY == rc.centerY;
     root.centerY == rc.centerY-50-rc.diameter;
 }

  

Figure: Binary trees.

The tree is composed of three circles and two lines. The constraint sameSize is a built-in constraint that takes an array of components and ensures the components are of the same size. The argument of the constraint {root,lc,rc} is an anonymous array. Anonymous arrays are very useful for grouping components and imposing some constraints on them.

The constraint positionNodes is a user-defined constraint. A constraint definition is similar in syntax to a method declaration, but it starts with the keyword constraint and its body is a sequence of constraints. The constraint positionNodes ensures that the root is located horizontally at the center of the two children and vertically 50 pixels above the two children.

The four equality constraints in the end of the class BinaryTree ensure that line l1 connects the root and the left child, and line l2 connects the root and the right child.

Now we are ready to combine three small trees to build the big tree as depicted in Figure (b). The following shows the code:

 class BigTree {
     dj Tree t0,t1,t2;

     t0.lc == t1.root;
     t0.rc == t2.root;
     left(t1,t2);
 }

This big tree is made up of three small trees, t0, t1, t2. The left child of t0 is the same as the root of t1, and the right child of t0 is the same as the root of t2. We see from this example that we can not only constrain attributes, but also unify components. Two components are unifiable if they belong to the same class and each attribute in one component is unifiable with its counterpart in the other component. The last constraint left(t1,t2) is necessary because otherwise t1 and t2 may overlap each other.