An oriented tree is either empty or is a node connected to zero or more non-empty oriented trees with directed edges.
North America
Canada
Alberta
Edmonton
Calgary
Quebec
Mexico
Sonora
Colima
Jalisco
Guadalajara
USA
California
Los Angeles
Sunland
Hollywood
San Pedro
Eagle Rock
Hawai`i
Po`ipu
Alaska
+---------------+----+
0 | — | |
+---------------+----+
1 | Mexico | 5 |
+---------------+----+
2 | Los Angeles | 17 |
+---------------+----+
3 | Po`ipu | 15 |
+---------------+----+
4 | Hollywood | 2 |
+---------------+----+
5 | North America | 0 |
+---------------+----+
6 | Edmonton | 8 |
+---------------+----+
7 | San Pedro | 2 |
+---------------+----+
8 | Alberta | 11 |
+---------------+----+
9 | Quebec | 11 |
+---------------+----+
10 | Calgary | 8 |
+---------------+----+
11 | Canada | 5 |
+---------------+----+
12 | Eagle Rock | 2 |
+---------------+----+
13 | Colima | 1 |
+---------------+----+
14 | Sonora | 1 |
+---------------+----+
15 | Hawai`i | 19 |
+---------------+----+
16 | Guadalajara | 20 |
+---------------+----+
17 | California | 19 |
+---------------+----+
18 | Alaska | 19 |
+---------------+----+
19 | USA | 5 |
+---------------+----+
20 | Jalisco | 1 |
+---------------+----+
21 | Sunland | 2 |
+---------------+----+
Each cell contains four links: parent, first child, next sibling, and previous sibling.
Many operations are simple getters and setters, but many require systematically traversing the tree. Two popular approaches are:
Rather than creating a tree class, we normally expose the tree node objects to clients. Here is a simple node interface. Note the use of the visitor pattern in the traversal methods.
package edu.lmu.cs.rtoal.collections;
import java.util.List;
/**
* A simple interface for trees.
*/
public interface SimpleTreeNode<E> {
/**
* Returns the data stored in this node.
*/
E getData();
/**
* Replaces the data object stored in this node with the given data.
*/
void setData(E data);
/**
* Returns the parent of this node, or null if this node is a root.
*/
SimpleTreeNode<E> getParent();
/**
* Returns the children of this node as a list of nodes. The returned
* list is read-only to prevent callers from inserting garbage into
* the actual list of children in the tree!
*/
List<? extends SimpleTreeNode<E>> getChildren();
/**
* Removes child from its current parent and inserts it
* at the given index of this node. Indices start at 0.
* @exception IndexOutOfBoundsException if the index is
* out of bounds.
* @exception IllegalArgumentException if the child is
* an ancestor of this node, since that would make
* a cycle in the tree.
*/
void insertChildAt(int index, SimpleTreeNode<E> child);
/**
* Removes this node, and all its descendants, from whatever
* tree it is in. Does nothing if this node is a root.
*/
void removeFromParent();
/**
* Visits the nodes in this tree in preorder.
*/
void traversePreorder(Visitor<E> visitor);
/**
* Visits the nodes in this tree in postorder.
*/
void traversePostorder(Visitor<E> visitor);
/**
* Visits the nodes in this tree in breadth-first order.
*/
void traverseBreadthFirst(Visitor<E> visitor);
/**
* Simple visitor interface.
*/
public interface Visitor<E> {
void visit(SimpleTreeNode<E> node);
}
}
A linked implementation
package edu.lmu.cs.rtoal.collections;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
* A simple class for tree nodes, implemented with direct links
* to its parent and its list of children.
*/
public class ChildListTreeNode<E> implements SimpleTreeNode<E> {
private E data;
private ChildListTreeNode<E> parent = null;
private LinkedList<ChildListTreeNode<E>> children =
new LinkedList<ChildListTreeNode<E>>();
/**
* Constructs a node as the root of its own one-element tree.
* This is the only public constructor. The only trees that
* clients can make directly are simple one-element trees.
*/
public ChildListTreeNode(E data) {
this.data = data;
}
/**
* Returns the data stored in this node.
*/
public E getData() {
return data;
}
/**
* Modifies the data stored in this node.
*/
public void setData(E data) {
this.data = data;
}
/**
* Returns the parent of this node, or null if this node is a root.
*/
public SimpleTreeNode<E> getParent() {
return parent;
}
/**
* Returns the children of this node as a list of nodes. The returned
* list is read-only to prevent callers from inserting garbage into
* the actual list of children in the tree!
*/
public List<? extends SimpleTreeNode<E>> getChildren() {
return Collections.unmodifiableList(children);
}
/**
* Removes child from its current parent and inserts it
* at the given index of this node. Indices start at 0.
* @exception IndexOutOfBoundsException if the index is
* out of bounds.
* @exception IllegalArgumentException if the child is
* an ancestor of this node, since that would make
* a cycle in the tree.
* @exception ClassCastException if child is not a
* ChildListTreeNode.
*/
public void insertChildAt(int index, SimpleTreeNode<E> child) {
// Ensure the child is not an ancestor.
for (ChildListTreeNode node = this; node != null; node = node.parent) {
if (node == child) {
throw new IllegalArgumentException();
}
}
// Ensure that the child is an instance of ChildListTreeNode.
ChildListTreeNode<E> childNode = (ChildListTreeNode<E>)child;
// Add the child to this node's child list, unhook child from
// its old parent and reparent to this node.
children.add(index, childNode);
if (childNode != null) {
childNode.removeFromParent();
childNode.parent = this;
}
}
/**
* Removes this node, and all its descendants, from whatever
* tree it is in. Does nothing if this node is a root.
*/
public void removeFromParent() {
if (parent != null) {
parent.children.remove(this);
this.parent = null;
}
}
/**
* Visits the nodes in this tree in preorder.
*/
public void traversePreorder(SimpleTreeNode.Visitor<E> visitor) {
visitor.visit(this);
for (SimpleTreeNode<E> child: children) {
child.traversePreorder(visitor);
}
}
/**
* Visits the nodes in this tree in postorder.
*/
public void traversePostorder(SimpleTreeNode.Visitor<E> visitor) {
for (SimpleTreeNode<E> child: children) {
child.traversePostorder(visitor);
}
visitor.visit(this);
}
/**
* Visits the nodes in this tree in breadth-first order.
*/
public void traverseBreadthFirst(SimpleTreeNode.Visitor<E> visitor) {
Queue<ChildListTreeNode<E>> queue = new LinkedList<ChildListTreeNode<E>>();
queue.offer(this);
while (!queue.isEmpty()) {
visitor.visit(queue.remove());
for (ChildListTreeNode<E> node: children) {
queue.offer(node);
}
}
}
}
And finally, a unit test:
package edu.lmu.cs.rtoal.collections;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNull;
import static org.junit.Assert.fail;
import org.junit.Test;
/**
* Unit test for the tree nodes implemented with the child list.
*/
public class ChildListTreeNodeTest {
@Test
public void testEmptyTree() {
SimpleTreeNode<String> root = new ChildListTreeNode<String>("root");
assertEquals(root.getData(), "root");
assertNull(root.getParent());
assertEquals(root.getChildren().size(), 0);
}
@Test
public void testSomeInserts() {
SimpleTreeNode<String> root = new ChildListTreeNode<String>("root");
root.setData("animal");
assertEquals(root.getData(), "animal");
root.insertChildAt(0, new ChildListTreeNode<String>("bird"));
assertEquals(root.getChildren().size(), 1);
SimpleTreeNode<String> bird =
root.getChildren().get(0);
bird.insertChildAt(0, new ChildListTreeNode<String>("sparrow"));
try {
bird.insertChildAt(2, new ChildListTreeNode<String>("raven"));
fail();
} catch (Exception e) {
assertTrue(true);
}
bird.insertChildAt(0, new ChildListTreeNode<String>("raven"));
bird.insertChildAt(2, new ChildListTreeNode<String>("finch"));
bird.insertChildAt(1, new ChildListTreeNode<String>("cardinal"));
bird.insertChildAt(4, new ChildListTreeNode<String>("hawk"));
bird.insertChildAt(2, new ChildListTreeNode<String>("cassowary"));
SimpleTreeNode sparrow = (SimpleTreeNode)bird.getChildren().get(3);
assertEquals(sparrow.getData(), "sparrow");
sparrow.removeFromParent();
assertEquals(bird.getChildren().size(), 5);
}
// TODO: This tester is nowhere near finished.
}