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.
Each node has the form (root subtree subtree ...)
(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))
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.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.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.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.
}