Previous Tutorial Next
Tutorial - Tree/Forest
General forest
In the ch.bfh.algo framework there is no class for representing one tree. Nevertheless, all algorithms using trees can be written using the Forest interface.
Using the forest interface, one can create one or many trees. The user will create nodes,. the nodes are inserted as the roots of independant trees. It is afteward possible to branche some trees as new subtrees of one tree.
public static Forest initForest(){
Forest f = new DefaultForest();
// Insert a new root
Position pA = f.insert("A");
Position pB = f.insert("B");
Position pC = f.insert("C");
Position pD = f.insert("D");
Position pE = f.insert("E");
Position pF = f.insert("F");
Position pG = f.insert("G");
Position pH = f.insert("H");
Position pI = f.insert("I");
Position pJ = f.insert("J");
Position pK = f.insert("K");
Position pL = f.insert("L");
Position pM = f.insert("M");
f.link(pA,pC);
f.link(pA,pD);
f.link(pD,pE);
f.link(pD,pF);
f.link(pD,pG);
f.link(pB,pH);
f.link(pB,pI);
f.link(pB,pJ);
f.link(pK,pL);
f.link(pL,pM);
return f;
}
In the previous example, we created 13 nodes and inserted links in order to create trees.
Visit a tree/forest
To visit a forest, we can get the list of its roots (method f.roots) and visit for each node its parent (f.parent(node)) and the list of its childeren (f.children(node)). Since these lists are iterable, it is therfor easy to write a loop visiting all the children of a node: for(Position child : f.children(tmpNode)).
The following example presents an algorithm visiting the forest, i.e. displaying the trees where the depth of a node is represented by its indentation.
public static void displayForest(Forest f){
LinkedSequence> s =
new LinkedSequence>();
LinkedSequence depthList = new LinkedSequence();
int depth=0;
for(Position root : f.roots()){
depth=0;
s.add(root);
depthList.add(depth);
while(!s.isEmpty()){
Position tmpNode = s.delete(s.last());
depth = depthList.delete(depthList.last());
System.out.println(createXSpaces(depth)+tmpNode.element());
for(Position child : f.children(tmpNode)){
s.add(child);
depthList.add(depth+1);
}
}
}
We can slso manipulate a tree, that means, cutting a branche and the putting it at another place. These operations are all O(1), because, we do not have to notify to the nodes that they belong to a new tree, since they remain in the same forest. We will use the methods f.cut(node) to transform the node into a new root (i.e. cut the tree rooted in node) and f.link(newParent,newChild) that creates a new link between the newParent and the newChild.
public static void transferChildren(Forest f,
Position p1,
Position p2){
for(Position child : f.children(p1)){
f.cut(child);
f.link(p2,child);
}
return;
}
Binary Trees/Forest
The framework does also support Binary trees (or forest). A binary tree is a tree, some methods throw a NotImplementedException.
public static BinaryForest initBinaryForest(){
BinaryForest f = new DefaultBinaryForest();
Position pA = f.insert("A");
Position pB = f.insert("B");
Position pC = f.insert("C");
Position pD = f.insert("D");
Position pE = f.insert("E");
Position pF = f.insert("F");
Position pG = f.insert("G");
Position pH = f.insert("H");
Position pI = f.insert("I");
Position pJ = f.insert("J");
Position pK = f.insert("K");
Position pL = f.insert("L");
Position pM = f.insert("M");
f.linkLeft(pA,pB);
f.linkRight(pA,pC);
f.linkLeft(pB,pD);
f.linkRight(pB,pE);
f.linkLeft(pC,pF);
f.linkRight(pC,pG);
f.linkRight(pG,pH);
f.linkRight(pH,pI);
f.linkLeft(pJ,pK);
f.linkRight(pJ,pL);
return f;
}
The manipulation of a binary forest can be done using the methods used for forests. But we also have the specific binary methods: f.childRight(node) and
f.childLeft(node).
The following recursive function is used to display the content of a binary tree.
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);
}
}
Example class:
Previous Tutorial Next
Copyright Berner Fachhochschule-TI 2007