17.4 Tree Nodes and Paths

You probably noticed that the DefaultTreeModel class depends on TreeNode and TreePath objects. In a tree, a TreeNode represents an individual piece of data stored at a particular point in a tree, and a path represents a collection of these pieces that are directly related to each other (in an ancestor/descendant relationship). Let's look at the classes that make up the typical nodes and paths.

17.4.1 The TreeNode Interface

A TreeNode is the basic unit of a tree. This interface defines the minimum properties and access routines a typical tree model expects to see in its nodes.

17.4.1.1 Properties

The TreeNode interface contains the properties listed in Table 17-6. The TreeNode properties are straightforward and deal with the structure of the node. The parent property holds a valid value for every node in a tree, except the root. The childAt property lets you access a particular child in the tree. The childCount property contains the number of children associated with this node, if it allows children. If the node does not allow children, it is probably a leaf, but it is also possible to have a mutable tree node that has no children, or does not allow children, and yet is not a leaf. (An empty directory with no write permissions would be an example of such a node.)

Table 17-6. TreeNode properties

Property	Data type	get	is	set	Default value
allowsChildren	boolean	·
childAti	TreeNode	·
childCount	int	·
leaf	boolean		·
parent	TreeNode	·
iindexed

Notice that the children are not properties of a TreeNode. This is not to say that a TreeNode does not have children, but rather the accessor methods do not fit the "property" definition.

17.4.1.2 Child access methods

public int getIndex(TreeNode node)

public Enumeration children( )

Access the children associated with a particular node. You can pick the child by node via getIndex( ); you can also use the childAt property accessor, getChildAt( ), to pick a child by index number. If you want all the nodes under a parent, the children( ) method returns an enumeration of those nodes.

17.4.2 The MutableTreeNode Interface

The MutableTreeNode interface extends the TreeNode interface to include basic manipulation methods for the children and the user data. If you set about defining your own nodes, this is a good place to start.

17.4.2.1 Properties

The MutableTreeNode class contains the properties listed in Table 17-7. MutableTreeNode adds write access to the parent property from the TreeNode interface and gives you access to user data. You should note, however, that setParent( ) expects a MutableTreeNode while getParent( ) simply returns a TreeNode. The userObject property contains the data that makes a TreeNode interesting. You can use this property to store any arbitrary object. All other properties are inherited without change.

Table 17-7. MutableTreeNode properties

Property	Data type	get	is	set	Default value
parento	MutableTreeNode	·		·
userObject	Object			·
ooverridden See also properties of the TreeNode interface (Table 17-6).

17.4.2.2 Mutation methods

The mutation methods of MutableTreeNode allow you to access and modify the node's children as well as its parent:

public void insert(MutableTreeNode child, int index)

Insert a child into the children array maintained by the node. The position of the new child is given by index. If you want to append a child, the index should be the node's getChildCount( ) + 1.

public void remove(int index)

public void remove(MutableTreeNode node)

Remove a child from the node; the child may be specified by its index or by the child node itself.

public void removeFromParent( )

Remove the node from its parent. This assumes that the parent is also a mutable node and allows the removal of children.

17.4.3 The DefaultMutableTreeNode Class

DefaultMutableTreeNode inherits many of its properties from the MutableTreeNode and TreeNode interfaces. It supplies the default values shown in Table 17-8. The properties that are not inherited describe relationships of various nodes and paths in a tree. We felt it would be easiest to explain these properties as methods. The properties are listed in Table 17-8 for completeness, but you should read the section on structure methods for details on their uses.

Table 17-8. DefaultMutableTreeNode properties

Property	Data type	get	is	set	Default value
allowsChildreno	boolean	·		·	false
childAti, o	TreeNode	·
childCounto	int	·			0
depth	int	·			0
firstChild	TreeNode	·			null
firstLeaf	DefaultMutableTreeNode	·			null
lastChild	TreeNode	·			null
lastLeaf	DefaultMutableTreeNode	·			null
leafo	boolean		·		true
leafCount	int	·			0
level	int	·			0
nextLeaf	DefaultMutableTreeNode	·			null
nextNode	DefaultMutableTreeNode	·			null
nextSibling	DefaultMutableTreeNode	·			null
parento	MutableTreeNode*	·		·	null
path	TreeNode[]	·			Array with this node as the sole element
previousLeaf	DefaultMutableTreeNode	·			null
previousNode	DefaultMutableTreeNode	·			null
previousSibling	DefaultMutableTreeNode	·			null
root	TreeNode	·			null
root	boolean		·		false
siblingCount	int	·			0
userObjecto	Object	·		·	null
userObjectPath	Object[]	·		·	null
iindexed, ooverridden *The get method for the parent property returns a TreeNode object. See also properties of the MutableTreeNode class (Table 17-7).

17.4.3.1 Constant

The DefaultMutableTreeNode class contains one constant, as shown in Table 17-9.

Table 17-9. DefaultMutableTreeNode constant

Constant	Type	Description
EMPTY_ENUMERATION	Enumeration	The enumeration methods listed later in this chapter return this constant if the enumeration you ask for is empty.

17.4.3.2 Constructors

public DefaultMutableTreeNode( )

public DefaultMutableTreeNode(Object userObject)

public DefaultMutableTreeNode(Object userObject, boolean allowsChildren)

Build new tree nodes that carry an optional userObject. You can also specify whether this child should be allowed to contain children. If you set allowsChildren to false, an IllegalStateException is thrown any time you try to insert or add a child to this node. By default, the user object is null, and children are allowed.

17.4.3.3 Structure methods

The structure methods listed here provide easy ways to modify and query the structure of a tree. You can check the relation of a given node to any other node and even retrieve specific relatives (children, parent, siblings) of a node. Many of these methods could be considered accessors for various properties; we thought it would be easier to discuss and contrast their behavior if we listed them as methods. In our discussion, we'll refer frequently to the tree made out of letters in Figure 17-3. Figure 17-8 shows a JTree built with the same structure using DefaultMutableTreeNode nodes and the DefaultTreeModel.

Figure 17-8. The JTree representation of the tree in Figure 17-3

public void add(MutableTreeNode child)

Remove the node child from its current position (if any) and append it to the end of the child array for this node. It throws IllegalStateException if this node does not allow children and throws IllegalArgumentException if child is null.

public TreeNode getChildAfter(TreeNode child)

Retrieve the next child for this node after the specified child. If child is the last node in the child array, it returns null. If child does not exist at this node, an IllegalArgumentException is thrown. (For node A, the child after B is C, and the child after C is D.)

public TreeNode getChildBefore(TreeNode child)

Retrieve the previous child for this node after the specified child. If child is the first node in the child array, it returns null. If child does not exist at this node, an IllegalArgumentException is thrown. (For node A, the child before node B is null, and the child before node C is B.)

public int getDepth( )

Return the depth of the tree starting from this node. This is an expensive operation because you must traverse the entire tree starting at this node to get the correct answer. (For node A, the depth is 6; for node G, the depth is 3.)

public TreeNode getFirstChild( )

Retrieve the first child in the child array of this node. If this node does not have any children, it throws a NoSuchElementException. (For node I, the first child is O.)

public DefaultMutableTreeNode getFirstLeaf( )

Get the first leaf that is a descendant of this node. If this node has no children, it is itself a leaf, so it returns this. (For node B, the first leaf is Q; for node W, the first leaf is W.)

public int getIndex(TreeNode child)

Return the index of child in the node's child array. It returns -1 if child does not exist at this node. (For node S, the index of W is 0. For node S again, the index of T is -1.)

public TreeNode getLastChild( )

Retrieve the last child in the child array of this node. If this node does not have any children, it throws a NoSuchElementException. (For node I, the last child is P.)

public DefaultMutableTreeNode getLastLeaf( )

Get the last leaf that is a descendant of this node. If this node has no children, it is itself a leaf, so it returns this. (For node B, the last leaf is K; for node D, the last leaf is P.)

public int getLeafCount( )

Return the number of leaves that are descendants of this node. If this node has no children, it is itself a leaf, so it returns 1. If a node has children, however, it is not a leaf, so it does not count itself. (For both nodes C and G, the leaf count is 3.)

public int getLevel( )

Return the current level of this node with relation to the root of the tree (i.e., its distance from the root). If this node is the root, its level is 0. (For node A, the level is 0; for node M, the level is 3.)

public DefaultMutableTreeNode getNextLeaf( )

Return the next node in the parent's tree that is a leaf. If this is the last node in its parent's tree, it returns null. It does not matter whether this node is a leaf or not. (For node H, the next leaf is Z.)

public DefaultMutableTreeNode getNextNode( )

Return the next node in the tree, where "next" is defined in terms of a preorder traversal of the tree. If this node is the last in a preorder traversal, it returns null. See the preorderEnumeration( ) method later in this chapter for a more detailed discussion of preorder traversals. (For node E, the next node is J; for node T, the next node is D.)

public DefaultMutableTreeNode getNextSibling( )

Return the next child in this parent's child array. If this node is the last (or only) child, it returns null. (For node Q , the next sibling is R; for node D, the next sibling is null.)

public TreeNode[] getPath( )

Return the path from the root to this node as an array of TreeNode objects. (The path for node R is A B E J R.)

public DefaultMutableTreeNode getPreviousLeaf( )

Return the previous node in the parent's tree that is a leaf. If this is the first node in the parent's tree, it returns null. It does not matter whether this node is a leaf or not. (For node H, the previous leaf is null; for node T, the previous leaf is X.)

public DefaultMutableTreeNode getPreviousNode( )

Return the previous node in the tree, where "previous" is defined in terms of a preorder traversal of the tree. If this node is the first in a preorder traversal, it returns null. See the preorderEnumeration( ) method later in the chapter for a more detailed discussion of preorder traversals. (For node E, the previous node is B; for node C, the previous node is K.)

public DefaultMutableTreeNode getPreviousSibling( )

Return the previous child in this parent's child array. If this node is the first (or only) child, it returns null. (For node Q , the previous sibling is null; for node D, the previous sibling is C.)

public TreeNode getRoot( )

Retrieve the root of the tree this node belongs to. Any given tree has exactly one root, where a root is defined as the node with a null parent. (For any node in the example tree, including A, the root is A.)

public TreeNode getSharedAncestor(DefaultMutableTreeNode node2)

Find the closest shared ancestor for this node and the given node2. If node2 is a descendant of this node, this node is the common ancestor (and vice versa). The "worst" case for two nodes in the same tree would be to have the root as the only shared ancestor. If node2 is not in this node's tree, it returns null. (For nodes J and K, the shared ancestor is B; for nodes J and V, the shared ancestor is A.)

public int getSiblingCount( )

Return the number of siblings for this node. Since a node is its own sibling, this method returns the child count for this node's parent. (For node Q , the sibling count is 2; for node K, the sibling count is 1.)

public Object[] getUserObjectPath( )

Return all user objects along the path from the root to this node. It may contain nulls if some nodes along the path have no user object. Recall that a user object is any arbitrary piece of data you wish to store with a node. In a filesystem tree that stores file and folder names as user objects, for example, this method returns an array of String objects where each string represents a directory in the path, and the last string represents the selected file.

public void insert(MutableTreeNode node, int index)

Insert a new node as a child to this node at the given index. If index is larger than getChildCount( ) + 1, it generates an ArrayIndexOutOfBoundsException. If node is null or is an ancestor of this node, it generates an IllegalArgumentException. If this node doesn't accept children (allowsChildren is false), it generates an IllegalStateException.

public boolean isLeaf( )

Return true if this node has no children. This method does not check the allowsChildren property. (Node B returns false; node R returns true.)

public boolean isNodeAncestor(TreeNode node2)

Return true if node2 is an ancestor of this node. (E, B, and A are all ancestors of node E.)

public boolean isNodeChild(TreeNode node2)

Return true if node2 is in this node's child array. (For node G, L returns true while S returns false.)

public boolean isNodeDescendant(DefaultMutableTreeNode node2)

Return true if node2 is a descendant of this node. (For node G, both L and S return true, but C and H return false.)

public boolean isNodeRelated(DefaultMutableTreeNode node2)

Return true if node2 is in the same tree as this node. (Any two nodes listed in our example are part of the same tree, so they all return true.)

public boolean isNodeSibling(TreeNode node2)

Return true if node2 is a sibling of this node. (For node Q , R is a sibling, but S is not.)

public boolean isRoot( )

Return true if this node is the root of its tree. "Rootness" is determined by having a null parent. (A is the root of the tree.)

public void remove(int index)

public void remove(MutableTreeNode node)

Remove a child from this node. In the first version, if an invalid index number is given, you receive an ArrayIndexOutOfBoundsException. In the second version, if the node given does not exist as a child, you receive an IllegalArgumentException. The child is given a null parent after removal.

public void removeAllChildren( )

Remove all the children attached to this node. It does nothing if no children exist.

public void removeFromParent( )

Remove this node from its parent. This works like a call to getParent( ). remove(this) by creating a new tree rooted at this node.

17.4.3.4 Enumeration methods

If you want to look at all the nodes in a tree, you should use one of the following enumeration methods to get that list of nodes. The enumeration does not build a copy of the tree, but it does keep track of where you are in the tree, and when you call the nextElement( ) method, you get the correct next element according to the traversal you picked. The code to traverse (or search) a tree looks something like this:

Enumeration e = root.breadthFirstEnumeration( );
while (e.hasMoreElements( )) {
    DefaultMutableTreeNode node = (DefaultMutableTreeNode)e.nextElement( );
    System.out.print(node.getUserObject( ) + " ");
    // Or do something else more interesting with the node
}
System.out.println( );

public Enumeration breadthFirstEnumeration( )

A breadth-first traversal starts looking at the root node, then goes to its children, in ascending index order. After each child is looked at, the traversal moves on to the children of the root's first child and so on. The tree in Figure 17-3 produces the following breadth-first output:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

A breadth-first traversal works if you are searching a very large tree for some item, and you expected to find the item near the top of the tree.

public Enumeration depthFirstEnumeration( )

public Enumeration postorderEnumeration( )

Depth-first (sometimes called postorder) traversals start with the root, go to its first child, go to that node's first child, and so on. The first node it actually "looks" at is the first leaf it hits. Then it backs up one level and goes to other children of that first leaf's parent. In our example, the depth-first traversal produces this output:

Q R J E K F B W X S L T M G C N H Z Y U V O P I D A

A depth-first traversal is useful if you expect to find the leaves of a tree interesting and want to start working with them quickly. For example, in a filesystem, a depth-first enumeration would get you to a file object right away.

public Enumeration preorderEnumeration( )

Preorder traversals start at the root, look at it, then move on to the first child, look at it, then move on to its first child, look at it, and so on. The preorder output of the example looks like this:

A B E J Q R F K C G L S W X M T D H N I O U Y Z V P

A preorder traversal is useful for dumping out a tree that represents some parsed data. In the filesystem example, such a traversal would be useful if you need information about each node as you traverse before you look at any of its children. A breadth-first search would give you all of the top-level directories first, which is not what we want. A depth-first search would not let us look at a directory until we had already seen its children—also not what we want.

public Enumeration children( )

public Enumeration pathFromAncestorEnumeration(TreeNode ancestor)

These last two enumerations do not give you the entire tree, but rather an interesting piece of it. The children( ) call is inherited from TreeNode and gives an enumeration of the immediate children of this node. The pathFromAncestorEnumeration( ) gives you a list of all the nodes from the root down to this node. (The children of A are B, C, and D. The path from the ancestor for node N is A D H N.)

public Enumeration getExpandedDescendants(TreePath parent)

Return an enumeration of all currently expanded nodes that are descendants of parent. If parent is null or is not expanded itself, null is returned.

17.4.4 The TreePath Class

If you look at a collection of these node objects from one node to one of its descendants, you have a path. The TreePath class is straightforward, but it does have some convenience methods for comparing and dealing with paths. A TreePath is a read-only object. If you want to change the structure of the path, you need to interact with the model, not the path. (These paths serve as a "view" of a tree branch but are not part of an existing tree.)

17.4.4.1 Properties

The TreePath class has five simple properties. The values of these properties, shown in Table 17-10, are set by the constructor, and after that are read-only.

Table 17-10. TreePath properties

Property	Data type	get	is	set	Default value
lastPathComponent	Object	·
parentPath	TreePath	·
path	Object[]	·
pathComponenti	Object	·
pathCount	int	·
iindexed

The path property is the array of tree nodes from the root to another node. Since the path is an Object array and not a TreeNode array, you can still use a TreePath to describe a path in a tree with custom nodes, such as our expression tree. The parentPath is a TreePath leading up to (and including) the parent of this node. pathCount is the number of nodes in the path property. lastPathComponent lets you access the last node on the path, and the indexed property, pathComponent, lets you retrieve any node.

17.4.4.2 Constructors

public TreePath(Object singlePath)

public TreePath(Object[] path)

Build a TreePath object out of one or several Objects. If you want a path represented by just one node, you can use the first version of the constructor. Typically, paths consist of several nodes from the root down to some interesting node, in which case you'd use the second version. A TreePath should reflect all the nodes from the root down, but there is no check involved if you tried to create a "partial" path from an ancestor node that was not necessarily the root. However, other classes dealing with TreePath objects expect the first entry in the path to be the root of the tree.

protected TreePath( )

This constructor is provided for subclasses that may choose to use other arguments to initialize a path.

protected TreePath(TreePath parent, Object lastElement)

protected TreePath(Object[] path, int length)

These constructors create new TreePath objects by returning the path with a length of the root to lastElement or of length nodes long, respectively. If you want to create a TreePath by lengthening a given path, see the pathByAddingChild( ) method below.

17.4.4.3 Miscellaneous methods

public boolean isDescendant(TreePath path)

Return true if path is a descendant of this path. The given path is considered a descendant of this path if path contains all the nodes found in this path. This differs from equals( ) in that path could be longer than this path and still be a descendant. If this path is null, it returns false.

public TreePath pathByAddingChild(Object child)

Return a new TreePath object created by appending child to this path. The child argument cannot be null.