Three new containers are added for multiway trees; two correspond to the existing unbounded definite and unbounded indefinite forms for existing structures such as Lists and Maps in Ada 2005. There is also a bounded form corresponding to the newly introduced bounded containers for the existing structures discussed above. As expected their names are

These containers have all the operations required to operate on a tree structure where each node can have multiple child nodes to any depth. Thus there are operations on subtrees, the ability to find siblings, to insert and remove children and so on. It will be noted that many of the operations on trees are similar to corresponding operations on lists.

We will look in detail at the unbounded definite form by giving its specification interspersed with some explanation. It starts with the usual generic parameters.

This is much as expected and follows the same pattern as the start of the list container in the previous section.

A tree consists of a set of nodes linked together in a hierarchical manner. Nodes are identified as usual by the value of a cursor. Nodes can have one or more child nodes; the children are ordered so that there is a first child and a last child. Nodes with the same parent are siblings. One node is the root of the tree. If a node has no children then it is a leaf node.

All nodes other than the root node have an associated element whose type is Element_Type. The whole purpose of the tree is of course to give access to these element values in a structured manner.

The function "=" compares two trees and returns true if and only if they have the same structure of nodes and corresponding nodes have the same values as determined by the generic parameter "=" for comparing elements. Similarly, the function Equal_Subtree compares two subtrees.

The function Node_Count gives the number of nodes in a tree. All trees have at least one node, the root node. The function Is_Empty returns true only if the tree consists of just this root node. Note that A_Tree = Empty_Tree, Node_Count(A_Tree) = 1 and Is_Empty(A_Tree) always have the same value. The function Subtree_Node_Count returns the number of nodes in the subtree identified by the cursor. If the cursor value is No_Element then the result is zero.

The functions Is_Root and Is_Leaf indicate whether a node is the root or a leaf respectively. If a tree is empty and so consists of just a root node then that node is both the root and a leaf so both functions return true.

The function Depth returns 1 if the node is the root, and otherwise indicates the number of ancestor nodes. Thus a node which is an immediate child of the root has depth equal to 2. The function Root returns the cursor designating the root of a tree. The procedure Clear removes all elements from the tree so that it consists just of a root node.

These subprograms have the expected behaviour similar to other containers.

These types and functions are similar to those for the other containers and were explained in Section 6.3 on iteration and also in the previous section (Section 8.3).

The subprograms Assign and Copy behave as expected and were explained in Section 8.2 on Bounded and unbounded containers. The procedure Move moves all the nodes from the source to the target after first clearing the target; it does not make copies of the elements so after the operation the source only has a root node.

The procedures Delete_Leaf and Delete_Subtree check that the cursor value designates a node of the container and raise Program_Error if it does not. Program_Error is also raised if Position designates the root node and so cannot be removed. In the case of Delete_Leaf, if the node has any children then Constraint_Error is raised. The appropriate nodes are then deleted and Position is set to No_Element.

The procedure Swap interchanges the values in the two elements denoted by the two cursors. The elements must be in the given container (and must not denote the root) otherwise Program_Error is raised.

These search for an element in the container with the given value Item. The function Contains returns false if the item is not found; the other functions return No_Element if the item is not found. The function Find searches the whole tree starting at the root node, Find_In_Subtree searches the subtree rooted at the node given by Position including the node itself; these searches are in depth-first order. The function Ancestor_Find searches upwards through the ancestors of the node given by Position including the node itself.

Depth-first order is explained at the end of the section.

These apply the procedure designated by the parameter Process to each element of the whole tree or the subtree. This includes the node at the subtree but not at the root; iteration is in depth-first order.

The first of these is called if we write

and iterates over the whole tree in the usual depth-first order. In order to iterate over a subtree we write

and this iterates over the subtree rooted at the cursor position given by S.

If we use the other new form of loop using of thus

then this also calls Iterate since the aspect Default_Iterator of the type Tree (see above) is Iterate. However, we cannot iterate over a subtree using this mechanism.

The function Child_Count returns the number of child nodes of the node denoted by Parent. This count covers immediate children only and not grandchildren.

The function Child_Depth indicates how many ancestors there are from Child to Parent. If Child is an immediate child of Parent then the result is 1; if it is a grandchild then 2 and so on.

These three procedures enable one or more new child nodes to be inserted. The parent node is given by Parent. If Parent already has children then the new nodes are inserted before the child node identified by Before; if Before is No_Element then the new nodes are inserted after all existing children. The second procedure is similar to the first but also returns a cursor to the first of the added nodes. The third is like the second but the new elements take their default values. Note the default value of one for the number of new nodes.

These insert the new children before or after any existing children.

This procedure simply deletes all the children, grandchildren, and so on of the node designated by Parent.

This copies the complete subtree rooted at Source into the tree denoted by Tree as a subtree of Parent at the place denoted by Before using the same rules as Insert_Child. Note that this makes a complete copy and creates new nodes with values equal to the corresponding existing nodes. Note also that Source might be within Tree but might not. There are the usual various checks.

These are similar to the procedures Splice applying to lists. They enable nodes to be moved without copying. The destination is indicated by Parent or Target_Parent together with Before as usual indicating where the moved nodes are to be placed with respect to existing children of Parent or Target_Parent.

The first Splice_Subtree moves the subtree rooted at Position in the tree Source to be a child of Parent in the tree Target. Note that Position is updated to be the appropriate element of Target. We can use this procedure to move a subtree within a tree but an attempt to create circularities raises Program_Error.

The second Slice_Subtree is similar but only moves a subtree within a container. Again, circularities cannot be created.

The procedures Splice_Children are similar but move all the children and their descendants of Source_Parent to be children of Target_Parent.

Hopefully, the purpose of these is self-evident.

These apply the procedure designated by the parameter Process to each child of the node given by Parent. The procedure Iterate_Children starts with the first child and ends with the last child whereas Reverse_Iterate_Children starts with the last child and ends with the first child. Note that these do not iterate over grandchildren.

This is called if we write

and iterates over all the children from Parent.First_Child to Parent.Last_Child. Note that we could also insert reverse thus

in which case the iteration goes in reverse from Parent.Last_Child to Parent.First_Child. The observant reader will note that this function returns Reversible_Iterator'Class and so can go in either direction whereas the functions Iterate and Iterate_Subtree described earlier use Forward_Iterator'Class and cannot be reversed.

The above descriptions have not described all the situations in which something can go wrong and so raise Constraint_Error or Program_Error. Generally, the former is raised if a source or target is No_Element; the latter is raised if a cursor does not belong to the appropriate tree. In particular, as mentioned above, an attempt to create an illegal tree such as one with circularities using Splice_Subtree raises Program_Error. Remember also that every tree has a root node but the root node has no element value; attempts to remove the root node or read its value or assign a value similarly raise Program_Error.

The containers for indefinite and bounded trees are much as expected.

In the case of the indefinite tree container the generic formal type is

The other significant difference is that the procedure Insert_Child without the parameter New_Item is omitted; this is because indefinite types do not have a default value.

In the case of the bounded tree container the changes are similar to those for the other containers. One change is that the package has pragma Pure; the other changes concern the capacity. The type Tree is

and the function Copy is

And of course the exception Capacity_Error is raised in various circumstances.

Applications of trees are usually fairly complex. The tree structure for depicting the analysis of a program for a whole language such as even Ada 83 has an enormous variety of nodes corresponding to the various syntactic structures. And trees depicting human relationships are complex because of multiple marriages, divorces, illegitimacy and so on. So we content ourselves with a couple of small examples.

A tree representing a simple algebraic expression involving just the binary operations of addition, subtraction, multiplication and division applied to simple variables and real literals is straightforward. Nodes are of three kinds, those representing operations have two children giving the two operands, and those representing variables and literals have no children and so are leaf nodes.

We can declare the element type thus

Note that the variables are (as typically in mathematics) represented by single letters. So the expression

is represented by nodes with elements such as

So now we can declare a suitable tree thus

and then build it by the following statements

This puts in the first real node as a child of the root which is designated by the cursor C. There are no existing children so Before is No_Element. The New_Item is as mentioned earlier. Finally, the cursor C is changed to designate the position of the newly inserted node.

We can then insert the two children of this node which represent the mathematical operations + and –.

These calls are to a different overloading of Insert_Child and have not changed the cursor. The second call also has Before equal to No_Element and so the second child goes after the first child. We now change the cursor to that of the first newly inserted child and then insert its children which represent x and 3. Thus

And then we can complete the tree by inserting the final two nodes thus

Of course a compiler will do all this recursively and keep track of the cursor rather more neatly than we have in this manual illustration.

The resulting tree should be as in Figure 1.

We can assume that the variables are held in an array which might be as follows

We can then evaluate the tree by a recursive function such as

Finally, we obtain the value of the tree by

Remember that the node at the root has no element so hence the call of First_Child.

An alternative approach would be to use tagged types with a different type for each kind of node rather than the variant record. This would be much more flexible and would have required the use of the unbounded indefinite container Ada.Containers.Indefinite_Multiway_Trees.

As a more human example we can consider the family tree of the Tudor Kings and Queens of England. We start with Henry VII, who had four children, Arthur, Margaret, Henry VIII and Mary. See Figure 2.

Arthur died young, Margaret married James IV of Scotland and had James (who was thus James V of Scotland), Henry VIII had three children, namely Edward VI, Mary I and Elizabeth I. And Mary had Frances. Henry VII was succeeded by Henry VIII and he was succeeded by his three children.

Remember the rules of primogeniture. The heir is the eldest son if there are sons; if not then the heir is the eldest daughter. If there are no offspring at all then we go back a generation and try again. Hence Edward VI became king despite being younger than Mary.

Since Edward, Mary and Elizabeth had no children we go back to the descendants of the other children of Henry VII. Margaret, her son James, and his daughter Mary Queen of Scots were all dead by then, so the throne of England went to the son of Mary who became James I of England and VI of Scotland and thus united the two thrones. So the Tudor line died with Elizabeth (Good Queen Bess).

Incidentally, Frances, the daughter of Mary, the fourth child of Henry VII, had a daughter, Lady Jane Grey; she was Queen for 9 days but lost her head over a row with Mary I.

Representing this is tricky, especially with people such as Henry VIII having so many wives. But the essence could be represented by a tree with a simple element type thus

With such a structure and the dates, starting from Henry VII and using the rules of primogeniture, one should be able to trace the monarchs (apart from poor Lady Jane Grey who would I am sure much rather not have been involved).

The overall tree structure is shown in Figure 2.

With the obvious connections we can define useful functions such as

More of a challenge is to define a function Is_Successor using the rules described above. The reader can contemplate these and other family relationships and attempt to construct the Tudor tree.

Finally, an explanation of depth-first order. The general principle is that child nodes are visited in order before their parent. We can symbolically write this as

and the whole thing is triggered by calling Do_Node(Root). Remember that the root node has no element. The result is that the first element to be processed is that of the leftmost leaf.

Thus in the tree illustrated below in Figure 3, the elements are visited in order A, B, C, D, and so on. Note that the root has no element and so is not visited.

© 2011, 2012, 2013 John Barnes Informatics.

Sponsored in part by: