11.4 TREE

Purpose:

General tree representation is useful in representing multiple level hierarchies, and is also important for many algorithms based on the divide-and-conquer approach. All the objects in the tree must be of the same type.

SINGLE_ and DOUBLE_TREE:

Both TREES behave identically, except that the DELETE operation is faster for the DOUBLE_TREE. In applications where DELETE is not frequently used, SINGLE_TREE is the better choice (it is faster, and needs less memory).

Order of objects:

All the children of any node form a RING. The child pointer from the parent represents the start pointer of the RING. Repeated use of add() loads the nodes in reverse order. set() can be used after each add() - refer to TRIANGLE - if the order is not to be reversed.

Adding new nodes:

add() adds a new child;
set() resets the beginning of the given subtree;
app() appends a new sibling to the right of a given node.
ins() (for DOUBLE_TREE only) inserts a new sibling to the left of a given node.

Deleting nodes:

del() disconnects the given node from its parent, but if there are any subtrees on it, it leaves them on the node. If you call del() on the root of a tree, nothing happens. del() can be used while traversing the set with the iterator. To disconnect a whole tree, move recursively bottom up like this:

ZZ_HYPER_SINGLE_TREE(myTree,Node);
void deleteTree(Node *root){
    Node *ep;
    Node* child=myTree.child(root);
    if(!child)myTree.del(root);
    else {
        myTree_iterator it(root);
        while(ep= ++it)deleteTree(ep);
    }
}

Moving around the TREE:

The iterator traverses the subnodes of a given node.

id_iterator it(parent);
while(obj= ++it){
...
};

This can be used recursively to traverse the whole tree (breadth first, depth first, whatever you prefer). See, for example, function prt3() in test12a.c.

par(), child(), fwd() and bwd() (for DOUBLE_TREES only) allow you to move around the tree. fwd() moves to the right, bwd() moves to the left. Remember that because each set of siblings is a RING, repeated calls to bwd() will lead to an infinite loop, unless proper termination is arranged. The iterator provides automatic termination when reaching the starting point.

Syntax:

ZZ_HYPER_SINGLE_TREE(id,TYPE);
ZZ_HYPER_DOUBLE_TREE(id,TYPE);		 These statements declare a tree, with children of each node linked into a singly/doubly linked ring.
void id.add(TYPE *parent,TYPE *newChild); Adds a new child under the given parent.
void id.app(TYPE *obj,TYPE *newObj); Appends a new object after the given object (under the same parent node).
void id.del(TYPE *objToRemove); Disconnects the given object from its parent and siblings, but it leaves its children and possibly a whole subtree.
TYPE* id.fwd(type *obj); Returns the next sibling under the same parent (fwd=FORWARD).
TYPE* id.par(TYPE *obj); Returns the parent of the given object.
TYPE* id.child(TYPE *obj); Returns the child of the given object.
void id.set(newFirstChild); Sets the object as the first child under the same parent.
TYPE *parent,*obj;
id_iterator it(parent); while(obj= ++it){ ... };		 Traverses all children of the given parent. Value of obj should not be modified from within the loop. Object can be deleted from the tree while traversing.

Commands available only for the DOUBLE_TREE:

void id.ins(TYPE *obj,TYPE *newSibling); Inserts a new sibling prior to the given object (under the same parent).
TYPE* id.bwd(TYPE *obj); Returns the previous (bwd=BACKWARD) child under the same parent.
TYPE *parent,*obj;
id_iterator it(parent); while(obj=it--){ ... };		 Works just like the other loop above, except that it traverses the set in reverse order.

Examples:

  1. Calculation of current and wire width in complicated tree-like power networks on a VLSI chip (test10a.c).
  2. NIAL-like language that manipulates objects and arrays of objects hierarchically arranged in a tree (test12a.c).
  3. Resetting the order of the subtrees with set() (test10b.c).

 

Previous Section 11.3 AGGREGATION Next Section 11.5 GRAPH