Trees in Java

Every computer user who has worked with a hierarchical file system has seen tree displays. Of course, directories and files are only one of the many exam­ples of tree-like organizations. Many tree structures arise in everyday life, such as the hierarchy of countries, states, and cities shown in Figure 11.11.

As programmers, we often need to display tree structures. Fortunately, the Swing library has a JTree class for this purpose. The JTree class (together with its helper classes) takes care of laying out the tree and processing user requests for expanding and collapsing nodes. In this section, you will learn how to put the JTree class to use.

As with the other complex Swing components, we must focus on the common and useful cases and cannot cover every nuance. If you want to achieve something unusual, we recommend that you consult Graphic Java™, Third Edition, by David M. Geary or Core Swing by Kim Topley.

Before going any further, let’s settle on some terminology (see Figure 11.12). A tree is composed of nodes. Every node is either a leaf or it has child nodes. Every node, with the exception of the root node, has exactly one parent. A tree has exactly one root node. Sometimes you have a collection of trees, each with its own root node. Such a collection is called a forest.

1. Simple Trees

In our first example program, we will simply display a tree with a few nodes (see Figure 11.14). As with many other Swing components, you need to pro­vide a model of the data, and the component displays it for you. To construct a JTree, supply the tree model in the constructor:

TreeModet model = …;

var tree = new JTree(model);

How do you obtain a tree model? You can construct your own model by creating a class that implements the TreeModel interface. You will see later in this chapter how to do that. For now, we will stick with the DefaultTreeModel that the Swing library supplies.

To construct a default tree model, you must supply a root node.

TreeNode root = . . .;

var model = new DefaultTreeModel(root);

TreeNode is another interface. Populate the default tree model with objects of any class that implements the interface. For now, we will use the concrete node class that Swing supplies—namely, DefaultMutableTreeNode. This class imple­ments the MutableTreeNode interface, a subinterface of TreeNode (see Figure 11.13).

A default mutable tree node holds an object—the user object. The tree renders the user objects for all nodes. Unless you specify a renderer, the tree displays the string that is the result of the toString method.

In our first example, we use strings as user objects. In practice, you would usually populate a tree with more expressive user objects. For example, when displaying a directory tree, it makes sense to use File objects for the nodes.

You can specify the user object in the constructor, or you can set it later with the setUserObject method.

var node = new DefaultMutableTreeNode(“Texas”);

node.setUserObject(“California”);

Next, you need to establish the parent/child relationships between the nodes. Start with the root node and use the add method to add the children:

var root = new DefaultMutableTreeNode(“World”);

var country = new DefaultMutableTreeNode(“USA”);

root.add(country);

var state = new DefaultMutableTreeNode(“California”);

country.add(state);

Figure 11.14 illustrates how the tree will look.

Link up all nodes in this fashion. Then, construct a DefaultTreeModel with the root node. Finally, construct a JTree with the tree model.

 

var treeModel = new DefaultTreeModel(root);

var tree = new JTree(treeModel);

Or, as a shortcut, you can simply pass the root node to the JTree constructor. Then the tree automatically constructs a default tree model:

var tree = new JTree(root);

Listing 11.8 contains the complete code.

When you run the program, the tree first looks as in Figure 11.15. Only the root node and its children are visible. Click on the circle icons (the handles) to open up the subtrees. The line sticking out from the handle icon points to the right when the subtree is collapsed and down when the subtree is expanded (see Figure 11.16). We don’t know what the designers of the Metal look-and-feel had in mind, but we think of the icon as a door handle. You push down on the handle to open the subtree.

You can use the following magic incantation to turn off the lines joining parents and children (see Figure 11.18):

tree.putClientProperty(“JTree.lineStyle”, “None”);

Conversely, to make sure that the lines are shown, use

tree.putClientProperty(“JTree.lineStyle”, “Angled”);

Another line style, “Horizontal”, is shown in Figure 11.19. The tree is displayed with horizontal lines separating only the children of the root. We aren’t quite sure what it is good for.

By default, there is no handle for collapsing the root of the tree. If you like, you can add one with the call

tree.setShowsRootHandles(true);

Figure 11.20 shows the result. Now you can collapse the entire tree into the root node.

Conversely, you can hide the root altogether. You will thus display a forest—a set of trees, each with its own root. You still must join all trees in the forest to a common root; then, hide the root with the instruction

tree.setRootVisibte(fatse);

Look at Figure 11.21. There appear to be two roots, labeled “USA” and “Germany.” The actual root that joins the two is made invisible.

Let’s turn from the root to the leaves of the tree. Note that the leaves have an icon different from the other nodes (see Figure 11.22).

When the tree is displayed, each node is drawn with an icon. There are actu­ally three kinds of icons: a leaf icon, an opened nonleaf icon, and a closed nonleaf icon. For simplicity, we refer to the last two as folder icons.

The node renderer needs to know which icon to use for each node. By default, the decision process works like this: If the isLeaf method of a node returns true, then the leaf icon is used; otherwise, a folder icon is used.

The isLeaf method of the DefauttMutabteTreeNode class returns true if the node has no children. Thus, nodes with children get folder icons, and nodes without children get leaf icons.

Sometimes, that behavior is not appropriate. Suppose we added a node “Montana” to our sample tree, but we’re at a loss as to what cities to add. We would not want the state node to get a leaf icon because, conceptually, only the cities are leaves.

The JTree class has no idea which nodes should be leaves. It asks the tree model. If a childless node isn’t automatically a conceptual leaf, you can ask the tree model to use a different criterion for leafiness—namely, to query the “allows children” node property.

For those nodes that should not have children, call

node.setAttowsChitdren(fatse);

Then, tell the tree model to ask the value of the “allows children” property to determine whether a node should be displayed with a leaf icon. Use the setAsksAUowsChildren method of the DefaultTreeModel class to set this behavior:

modet.setAsksAUowsChitdren(true);

With this decision criterion, nodes that allow children get folder icons, and nodes that don’t allow children get leaf icons.

Alternatively, if you construct the tree from the root node, supply the setting for the “asks allows children” property in the constructor.

var tree = new JTree(root, true); // nodes that don’t allow children get teat icons

1.1 Editing Trees and Tree Paths

In the next example program, you will see how to edit a tree. Figure 11.23 shows the user interface. If you click the Add Sibling or Add Child button, the program adds a new node (with title New) to the tree. If you click the Delete button, the program deletes the currently selected node.

To implement this behavior, you need to find out which tree node is currently selected. The JTree class has a surprising way of identifying nodes in a tree. It does not deal with tree nodes but with paths of objects, called tree paths. A tree path starts at the root and consists of a sequence of child nodes (see Figure 11.24).

You might wonder why the JTree class needs the whole path. Couldn’t it just get a TreeNode and keep calling the getParent method? In fact, the JTree class knows nothing about the TreeNode interface. That interface is never used by the TreeModet interface; it is only used by the DefauttTreeModet implementation. You can have other tree models in which the nodes do not implement the TreeNode interface at all. If you use a tree model that manages other types of objects, those ob­jects might not have getParent and getChitd methods. They would of course need to have some other connection to each other. It is the job of the tree model to link nodes together. The JTree class itself has no clue about the nature of their linkage. For that reason, the JTree class always needs to work with complete paths.

The TreePath class manages a sequence of Object (not TreeNode!) references. A number of JTree methods return TreePath objects. When you have a tree path, you usually just need to know the terminal node, which you can get with the getLastPathComponent method. For example, to find out the currently selected node in a tree, use the getSetectionPath method of the JTree class. You will get a TreePath object back, from which you can retrieve the actual node.

TreePath setectionPath = tree.getSetectionPath();

var setectedNode = (DefauttMutabteTreeNode) setectionPath.getLastPathComponent();

Actually, since this particular query is so common, there is a convenience method that gives the selected node immediately:

var setectedNode = (DefauttMutabteTreeNode) tree.getLastSetectedPathComponent();

This method is not called getSetectedNode because the tree does not know that it contains nodes—its tree model deals only with paths of objects.

Once you have the selected node, you can edit it. However, do not simply add children to a tree node:

setectedNode.add(newNode); // No!

If you change the structure of the nodes, you change the model but the asso­ciated view is not notified. You could send out a notification yourself, but if you use the insertNodeInto method of the DefauttTreeModet class, the model class takes care of that. For example, the following call appends a new node as the last child of the selected node and notifies the tree view:

modet.insertNodeInto(newNode, setectedNode, setectedNode.getChitdCount());

The analogous call removeNodeFromParent removes a node and notifies the view:

modet.removeNodeFromParent(setectedNode);

If you keep the node structure in place but change the user object, you should call the following method:

modet.nodeChanged(changedNode);

The automatic notification is a major advantage of using the DefauttTreeModet. If you supply your own tree model, you have to implement automatic notification by hand. (See Core Swing by Kim Topley for details.)

When the view is notified of a change in the node structure, it updates the display but does not automatically expand a node to show newly added children. In particular, if a user in our sample program adds a new child node to a node for which children are currently collapsed, the new node is silently added to the collapsed subtree. This gives the user no feedback that the command was actually carried out. In such a case, you should make a special effort to expand all parent nodes so that the newly added node becomes visible. Use the makeVisible method of the JTree class for this purpose. The makeVisible method expects a tree path leading to the node that should become visible.

Thus, you need to construct a tree path from the root to the newly inserted node. To get a tree path, first call the getPathToRoot method of the DefauttTreeModet class. It returns a TreeNode[] array of all nodes from a node to the root node. Pass that array to a TreePath constructor.

For example, here is how you make the new node visible:

TreeNode[] nodes = model.getPathToRoot(newNode);

var path = new TreePath(nodes);

tree.makeVisible(path);

Now, suppose your tree is contained inside a scroll pane. After the tree node expansion, the new node might still not be visible because it falls outside the viewport. To overcome that problem, call

tree.scroUPathToVisibte(path);

instead of calling makeVisibte. This call expands all nodes along the path and tells the ambient scroll pane to scroll the node at the end of the path into view (see Figure 11.25).

By default, tree nodes cannot be edited. However, if you call

tree.setEditabte(true);

the user can edit a node simply by double-clicking, editing the string, and pressing the Enter key. Double-clicking invokes the default cell editor, which is implemented by the DefauttCettEditor class (see Figure 11.26). It is possible to install other cell editors, using the same process that you have seen in our discussion of table cell editors.

Listing 11.9 shows the complete source code of the tree editing program. Run the program, add a few nodes, and edit them by double-clicking. Observe how collapsed nodes expand to show added children and how the scroll pane keeps added nodes in the viewport.

2. Node Enumeration

Sometimes you need to find a node in a tree by starting at the root and visiting all children until you have found a match. The DefauttMutabteTreeNode class has several convenience methods for iterating through nodes.

The breadthFirstEnumeration and depthFirstEnumeration methods return enumeration objects whose nextElement method visits all children of the current node, using either a breadth-first or depth-first traversal. Figure 11.27 shows the traversals for a sample tree—the node labels indicate the order in which the nodes are traversed.

Breadth-first enumeration is the easiest to visualize. The tree is traversed in layers. The root is visited first, followed by all of its children, then the grandchildren, and so on.

To visualize depth-first enumeration, imagine a rat trapped in a tree-shaped maze. It rushes along the first path until it comes to a leaf. Then, it backtracks and turns around to the next path, and so on.

Computer scientists also call this postorder traversal because the search process visits the children before visiting the parents. The postOrderEnumeration method is a synonym for depthFirstEnumeration. For completeness, there is also a preOrderEnumeration, a depth-first search that enumerates parents before the children.

Here is the typical usage pattern:

Enumeration breadthFirst = node.breadthFirstEnumeration();

white (breadthFirst.hasMoreEtements())

do something with breadthFirst.nextElement();

Finally, a related method, pathFromAncestorEnumeration, finds a path from an ancestor to a given node and enumerates the nodes along that path. That’s no big deal— it just keeps calling getParent until the ancestor is found and then presents the path in reverse order.

In our next example program, we put node enumeration to work. The program displays inheritance trees of classes. Type the name of a class into the text field on the bottom of the frame. The class and all of its superclasses are added to the tree (see Figure 11.28).

In this example, we take advantage of the fact that the user objects of the tree nodes can be objects of any type. Since our nodes describe classes, we store Class objects in the nodes.

We don’t want to add the same class object twice, so we need to check whether a class already exists in the tree. The following method finds the node with a given user object if it exists in the tree:

public DefaultMutableTreeNode findUserObject(Object obj)

{

Enumeration e = root.breadthFirstEnumeration(); while (e.hasMoreElements())

{

DefaultMutableTreeNode node = (DefaultMutableTreeNode) e.nextElement();

if (node.getUserObject().equals(obj))

return node;

}

return null;

}

3. Rendering Nodes

In your applications, you will often need to change the way a tree component draws the nodes. The most common change is, of course, to choose different icons for nodes and leaves. Other changes might involve changing the font of the node labels or drawing images at the nodes. All these changes are possible by installing a new tree cell tenderer into the tree. By default, the JTree class uses DefaultTreeCettRenderer objects to draw each node. The DefaultTreeCettRenderer class extends the JLabet class. The label contains the node icon and the node label.

You can customize the display in three ways.

  • You can change the icons, font, and background color used by a DefaultTreeCettRenderer. These settings are used for all nodes in the tree.
  • You can install a renderer that extends the DefaultTreeCettRenderer class and vary the icons, fonts, and background color for each node.
  • You can install a renderer that implements the TreeCellRenderer interface to draw a custom image for each node.

Let us look at these possibilities one by one. The easiest customization is to construct a DefaultTreeCellRenderer object, change the icons, and install it into the tree:

var renderer = new DefaultTreeCellRenderer();

renderer.setLeafIcon(new ImageIcon(“blue-ball.gif”)); // used for leaf nodes

renderer.setClosedIcon(new ImageIcon(“red-ball.gif”)); // used for collapsed nodes

renderer.setOpenIcon(new ImageIcon(“yellow-ball.gif”)); // used for expanded nodes

tree.setCellRenderer(renderer);

You can see the effect in Figure 11.28. We just use the “ball” icons as place­holders—presumably your user interface designer would supply you with appropriate icons to use for your applications.

We don’t recommend that you change the font or background color for an entire tree—that is really the job of the look-and-feel.

However, it can be useful to change the font of some nodes in a tree to highlight them. If you look carefully at Figure 11.28, you will notice that the abstract classes are set in italics.

To change the appearance of individual nodes, install a tree cell renderer. Tree cell renderers are very similar to the list cell renderers we discussed earlier in this chapter. The TreeCettRenderer interface has a single method:

Component getTreeCettRendererComponent(JTree tree, Object value, boolean selected, boolean expanded,

boolean leaf, int row, boolean hasFocus)

The getTreeCeURendererComponent method of the DefaultTreeCellRenderer class returns this—in other words, a label. (The DefaultTreeCellRenderer class extends the JLabel class.) To customize the component, extend the DefauttTreeCettRenderer class. Override the getTreeCettRendererComponent method as follows: Call the superclass method so it can prepare the label data, customize the label properties, and finally return this.

class MyTreeCettRenderer extends DefauttTreeCettRenderer

{

public Component getTreeCeURendererComponent(JTree tree, Object value, boolean selected, boolean expanded, boolean leaf, int row, boolean hasFocus)

{

Component comp = super.getTreeCeURendererComponent(tree, value, selected,

expanded, leaf, row, hasFocus);

DefauttMutabteTreeNode node = (DefauttMutabteTreeNode) vatue;

look at node.getUserObject();

Font font = appropriate font;

comp.setFont(font);

return comp;

}

};

The ClassNameTreeCeURenderer in Listing 11.10 sets the class name in either the normal or italic font, depending on the ABSTRACT modifier of the Ctass object. We don’t want to set a particular font because we don’t want to change whatever font the look-and-feel normally uses for labels. For that reason, we use the font from the label and derive an italic font from it. Recall that only a single shared JLabet object is returned by all calls. We need to hang on to the original font and restore it in the next call to the getTreeCettRendererComponent method.

Also, note how we change the node icons in the CtassTreeFrame constructor.

4. Listening to Tree Events

Most commonly, a tree component is paired with some other component. When the user selects tree nodes, some information shows up in another window. See Figure 11.29 for an example. When the user selects a class, the instance and static variables of that class are displayed in the text area to the right.

To obtain this behavior, you need to install a tree selection listener. The listener must implement the TreeSetectionListener interface—an interface with a single method:

void vatueChanged(TreeSetectionEvent event)

That method is called whenever the user selects or deselects tree nodes. Add the listener to the tree in the normal way:

tree.addTreeSelectionListener(listener);

You can specify whether the user is allowed to select a single node, a contigu­ous range of nodes, or an arbitrary, potentially discontiguous, set of nodes. The JTree class uses a TreeSelectionModel to manage node selection. You need to retrieve the model to set the selection state to one of SINGLE_TREE_SELECTION, CONTIGUOUS_TREE_SELECTION, or DISCONTIGUOUS_TREE_SELECTION. (Discontiguous selection mode is the default.) For example, in our class browser, we want to allow selection of only a single class:

int mode = TreeSelectionModel.SINGLE_TREE_SELECTION;

tree.getSelectionModel().setSelectionMode(mode);

Apart from setting the selection mode, you need not worry about the tree selection model.

To find out the current selection, query the tree with the getSelectionPaths method:

TreePath[] selectedPaths = tree.getSelectionPaths();

If you restricted the user to single-item selection, you can use the convenience method getSelectionPath which returns the first selected path or null if no path was selected.

Listing 11.10 shows the frame class for the class tree program. The program displays inheritance hierarchies and customizes the display to show abstract classes in italics. (See Listing 11.11 for the cell renderer.) You can type the name of any class into the text field at the bottom of the frame. Press the Enter key or click the Add button to add the class and its superclasses to the tree. You must enter the full package name, such as java.util.ArrayList.

This program is a bit tricky because it uses reflection to construct the class tree. This work is done inside the addClass method. (The details are not that important. We use the class tree in this example because inheritance yields a nice supply of trees without laborious coding. When you display trees in your applications, you will have your own source of hierarchical data.) The method uses the breadth-first search algorithm to find whether the current class is already in the tree by calling the findUserObject method that we imple­mented in the preceding section. If the class is not already in the tree, we add the superclasses to the tree, then make the new class node a child and make that node visible.

When you select a tree node, the text area to the right is filled with the fields of the selected class. In the frame constructor, we restrict the user to single­item selection and add a tree selection listener. When the vatueChanged method is called, we ignore its event parameter and simply ask the tree for the current selection path. As always, we need to get the last node of the path and look up its user object. We then call the getFietdDescription method which uses reflection to assemble a string with all fields of the selected class.

 

5. Custom Tree Models

In the final example, we implement a program that inspects the contents of an object, just like a debugger does (see Figure 11.30).

 

Before going further, compile and run the example program. Each node cor­responds to an instance field. If the field is an object, expand it to see its in­stance fields. The program inspects the contents of the frame window. If you poke around a few of the instance fields, you should be able to find some familiar classes. You’ll also gain some respect for how complex the Swing user interface components are under the hood.

What’s remarkable about the program is that the tree does not use the DefauttTreeModet. If you already have data that are hierarchically organized, you might not want to build a duplicate tree and worry about keeping both trees synchronized. That is the situation in our case—the inspected objects are al­ready linked to each other through the object references, so there is no need to replicate the linking structure.

The TreeModet interface has only a handful of methods. The first group of methods enables the JTree to find the tree nodes by first getting the root, then the children. The JTree class calls these methods only when the user actually expands a node.

Object getRoot()

int getChitdCount(Object parent)

Object getChild(Object parent, int index)

This example shows why the TreeModet interface, like the JTree class itself, does not need an explicit notion of nodes. The root and its children can be any objects. The TreeModet is responsible for telling the JTree how they are connected.

The next method of the TreeModet interface is the reverse of getChitd:

int getIndexOfChitd(Object parent, Object chitd)

Actually, this method can be implemented in terms of the first three—see the code in Listing 11.12.

The tree model tells the JTree which nodes should be displayed as leaves:

boolean isLeaf(Object node)

If your code changes the tree model, the tree needs to be notified so it can redraw itself. The tree adds itself as a TreeModetListener to the model. Thus, the model must support the usual listener management methods:

void addTreeModelListener(TreeModelListener l)

void removeTreeModetListener(TreeModetListener t)

You can see the implementations for these methods in Listing 11.13.

When the model modifies the tree contents, it calls one of the four methods of the TreeModetListener interface:

void treeNodesChanged(TreeModetEvent e)

void treeNodesInserted(TreeModelEvent e)

void treeNodesRemoved(TreeModelEvent e)

void treeStructureChanged(TreeModelEvent e)

The TreeModelEvent object describes the location of the change. The details of assembling a tree model event that describes an insertion or removal event are quite technical. You only need to worry about firing these events if your tree can actually have nodes added and removed. In Listing 11.12, we show how to fire one event by replacing the root with a new object.

Finally, if the user edits a tree node, your model is called with the change:

void valueForPathChanged(TreePath path, Object newValue)

If you don’t allow editing, this method is never called.

If you don’t need to support editing, constructing a tree model is easily done. Implement the three methods:

Object getRoot()

int getChildCount(Object parent)

Object getChild(Object parent, int index)

These methods describe the structure of the tree. Supply routine implementa­tions of the other five methods, as in Listing 11.12. You are then ready to display your tree.

Now let’s turn to the implementation of the example program. Our tree will contain objects of type Variable.

For example, suppose you inspect the variable

Employee joe;

That variable has a type Employee.class, a name “joe”, and a value—the value of the object reference joe. In Listing 11.14, we define a class Variable that describes a variable in a program:

var v = new Variable(Employee.class, “joe”, joe);

If the type of the variable is a primitive type, you must use an object wrapper for the value.

new Variable(double.class, “salary”, new Double(salary));

If the type of the variable is a class, the variable has fields. Using reflection, we enumerate all fields and collect them in an ArrayList. Since the getFields method of the Class class does not return the fields of the superclass, we need to call getFields on all superclasses as well. You can find the code in the Variable constructor. The getFields method of our Variable class returns the array of fields. Finally, the toString method of the Variable class formats the node label. The label always contains the variable type and name. If the variable is not a class, the label also contains the value.

Let’s move on to the tree model. The first two methods are simple.

public Object getRoot()

{

return root;

}

public int getChildCount(Object parent)

{

return ((Variable) parent).getFields().size();

}

The getChild method returns a new Variable object that describes the field with the given index. The getType and getName methods of the Field class yield the field type and name. By using reflection, you can read the field value as f.get(parentValue). That method can throw an IllegalAccessException. However, we made all fields accessible in the Variable constructor, so this won’t happen in practice.

Here is the complete code of the getChild method:

public Object getChild(Object parent, int index)

{

ArrayList fields = ((Variable) parent).getFields();

var f = (Field) fields.get(index);

Object parentValue = ((Variable) parent).getValue(); try

{

return new Variable(f.getType(), f.getName(), f.get(parentValue));

}

catch (IllegalAccessException e)

{

return null;

}

}

These three methods reveal the structure of the object tree to the JTree component. The remaining methods are routine—see the source code in Listing 11.13.

There is one remarkable fact about this tree model: It actually describes an infinite tree. You can verify this by following one of the WeakReference objects. Click on the variable named referent. It leads you right back to the original object. You get an identical subtree, and you can open its WeakReference object again, ad infinitum. Of course, you cannot store an infinite set of nodes; the tree model simply generates the nodes on demand as the user expands the parents. Listing 11.12 shows the frame class of the sample program.

Source: Horstmann Cay S. (2019), Core Java. Volume II – Advanced Features, Pearson; 11th edition.

Leave a Reply

Your email address will not be published. Required fields are marked *