ch.bfh.algo
Interface BinaryForest<E>

All Superinterfaces:

Collection<E>, Container<E>, Forest<E>, Iterable<E>

All Known Subinterfaces:

GenericBinaryForest<E,P>

All Known Implementing Classes:

DefaultBinaryForest, GenericBinaryForestGraph

public interface BinaryForest<E>
extends Forest<E>

The BinaryForest interface extends the Forest interface. It defines a forest which contains only binary trees. In this implementation. A node can have 0 children (it is called a leaf), 1 child or 2 children. To each child is assigned a position, left or right, so for each node, we have one or zero left child and one or zero right child. Here is an example of use of a binary forest. We have a recursive algorithm for displaying all the trees of a binary forest.

    static void displayRecBinaryForest(BinaryForest f,Position p, int depth){
        if(f.childLeft(p)!= null){
            displayRecBinaryForest(f,f.childLeft(p),depth+1);
        }
        System.out.println(createXSpaces(depth)+p.element());
        if(f.childRight(p)!= null){
            displayRecBinaryForest(f,f.childRight(p),depth+1);
        }
    }

    public static void displayBinaryForest(BinaryForest f){
        System.out.println("--------");
        for(Position root : f.roots()){
            displayRecBinaryForest(f,root,0);
            System.out.println("--------");
        }
    } 
 

All implementations of that interface should throw an UnsupportedOperationException when the following methods are executed: link, linkAfter and linkBefore.

Version:

1.0

Author:

Juerg Kraehenbuehl (code) and Emmanuel Benoist (Javadoc)

Method Summary

Position<E>	childLeft(Position<?> parent) Access the left child of a given node (the parent).
Position<E>	childRight(Position<?> parent) Access the right child of a given node (the parent).
void	linkLeft(Position<?> parent, Position<?> child) Creates a link (parent-child relationship) between a node, the parent, and another node, the child The child should not have any parent, i.e.
void	linkRight(Position<?> parent, Position<?> child) Creates a link (parent-child relationship) between a node, the parent, and another node, the child The child should not have any parent, i.e.

Methods inherited from interface ch.bfh.algo.Forest

children, cut, link, linkAfter, linkBefore, parent, roots

Methods inherited from interface ch.bfh.algo.Container

delete, element, encloses, insert, positionIterator, replace, swap

Methods inherited from interface java.util.Collection

add, addAll, clear, contains, containsAll, equals, hashCode, isEmpty, iterator, remove, removeAll, retainAll, size, toArray, toArray

Method Detail

childLeft

Position<E> childLeft(Position<?> parent)
                      throws InvalidAccessorException

Access the left child of a given node (the parent).

Parameters:

parent - the node of which we want the left child

Returns:

the left child of the parent

Throws:

InvalidAccessorException - if the position is not a valid node of this forest.

childRight

Position<E> childRight(Position<?> parent)
                       throws InvalidAccessorException

Access the right child of a given node (the parent).

Parameters:

parent - the node of which we want the right child

Returns:

the right child of the parent

Throws:

InvalidAccessorException - if the position is not a valid node of this forest.

linkLeft

void linkLeft(Position<?> parent,
              Position<?> child)
              throws InvalidAccessorException

Creates a link (parent-child relationship) between a node, the parent, and another node, the child The child should not have any parent, i.e. it is a root.

Parameters:

parent - The node receiving a new left child

child - The node becoming the new left child

Throws:

InvalidAccessorException - if the position is not a valid node of this forest.

linkRight

void linkRight(Position<?> parent,
               Position<?> child)
               throws InvalidAccessorException

Creates a link (parent-child relationship) between a node, the parent, and another node, the child The child should not have any parent, i.e. it is a root.

Parameters:

parent - The node receiving a new left child

child - The node becoming the new left child

Throws:

InvalidAccessorException - if the position is not a valid node of this forest.