Web DevCenter    
 Published on Web DevCenter (http://www.oreillynet.com/javascript/)
 See this if you're having trouble printing code examples


Working with Object Trees: Part Two

by Budi Kurniawan
05/04/2001

When working with objects in JavaScript, you don't have much choice other than to use the "array object." I described the basic concepts of the array object in my previous article. In this article, I'll explain the operations that you need to work with an object tree, such as create an object, append a child object to the root, search an object in the object tree, append an object to another object, and delete an object.

Creating an object

Of our interest is finding a way to make an array behave like an object. The createObject function in Listing 9 is a function that will return an object (which is technically an Array object, of course).


Listing 9: The createObject function to create an object


<script language="JavaScript">
function createObject() {
  var anArray = new Array();
  return anArray;
}
</script>


Alternatively, you can write a function that creates an object with predefined properties. For example, the createDog function in Listing 10 creates a dog object with a name and fur color.


Listing 10: A function that creates an object with predefined properties


<script language="JavaScript">
function createDog(name, color) {
  var dog = new Array();
  dog[0] = name;
  dog[1] = color;
  return dog;
}
</script>


A hierarchy of objects

Having a function to create objects, now you can have a hierarchy of objects. A hierarchy of objects means parent-child relationships among your objects. Consider, for instance, a Windows directory system. First you have a drive called the C drive. The C drive has a folder under it called Program Files. The Program Files folder is the child object of the C drive. The C drive is the parent of the Program Files folder. The Program Files folder in turn can have its own child objects.

In a hierarchy like this, there is always an object that does not have a parent. In the directory system example, it is the C drive. In many contexts, it is simply called the root. The root plays an important role because it is the entry point of the hierarchy. Every single operation will involve the root. For example, if you have a family tree of your dogs and you want to search for a dog called "Boni," the search starts from the root.

Appending a child object to another object

To create an object tree, you must have at least two objects, and you must create a parent-child relationship between them. Say, for example, a Dog object has a name, a color, and zero or more child Dog objects. You can use an array to represent the Dog object. The first and second elements are reserved for the name and color, and then the third and successive elements are for each child Dog object.

Therefore, a Dog object has at least two elements, i.e., its name and color. A Dog with no child object will only have two elements. A Dog with one child object has three elements: name, color, and a reference to another Dog object. If the Dog has two child objects, it then has the fourth element for yet another Dog object.

The important point here is to be able to create a Dog object and create a relationship between a parent and a child Dog object. You have seen the function to create an object in the previous section; now you need another function to append an object as a child object to another object. Just call this function append. The code for the append function is given in Listing 11.


Listing 11: The append function


<script language="JavaScript">
function append(parent, child) {
  parent[parent.length] = child;
}
</script>


Working with Object Trees

Go to Part one of this series

This function accepts two arguments: the object that will be the parent and the object that will be the child in the relationship. Since an array is completely dynamic, you can easily create a new element for the child object. The length property returns the number of elements, but the element index starts with 0. Therefore, the length property returns the index that is the next element in the array. For example, the code in Listing 12 creates two Dog objects called doggy and puppy and then creates a parent-child relationship between them.


Listing 12: Creating a parent object and a child object


<script language="JavaScript">

function createDog(name, color) {
  var dog = new Array();
  dog[0] = name;
  dog[1] = color;
  return dog;
}
function append(parent, child) {
  parent[parent.length] = child;
}

var doggy = createDog("boli", "black");
var puppy = createDog("boni", "white");
append(doggy, puppy);

</script>


If you are curious about the parent-child relationship between the two objects, paste this at the end of the code:


for (var i = 0; i<doggy.length; i++) {
  alert(doggy[i] );
}

Running the code in a Web browser, it will display three alert windows. The first alert window will display "boli," the second "black," and the third "boni,white."

Navigating the tree

Just assume that you have a family tree of Bo, the famous family dog. To simplify things, also assume that a dog only has one parent in the tree. Bo had two puppies: Boli and Boy. While Boy stayed a bachelor for the rest of his life, Boli later had two other puppies: Boni and Bulbul. Boni later had Spotty and Mary.

The dog family tree is visualized here.

Bo  -- Boli    -- Bulbul
               -- Boni    -- Spotty
                          -- Mary
    -- Boy

To create this tree, you need to first create individual dogs. And then, you need to build the tree structure by appending a child dog to its parent object. Listing 13 is the code to build Bo's family tree.


Listing 13: Creating a family tree


<html>
<script language="JavaScript">
function createDog(name, color) {
  var dog = new Array();
  dog[0] = name;
  dog[1] = color;
  return dog;
}
function append(parent, child) {
  parent[parent.length] = child;
}
var bo = createDog("bo", "brown");
var boli = createDog("boli", "black and white");
var boy = createDog("boy", "brown");
var bulbul = createDog("bulbul", "brown");
var boni = createDog("boni", "black and white");
var spotty = createDog("spotty", "black and white");
var mary = createDog("boni", "black and white");
append(bo, boli);
append(bo, boy);
append(boli, bulbul);
append(boli, boni);
append(boni, spotty);
append(boni, mary);
</script>
</html>


Now, let's demonstrate how to navigate the tree by printing each dog's name. To navigate, you need to learn about the generation of each dog. The generation starts from 1. Bo is the root, thereby she is the first generation in the tree. Navigating the tree basically means you start from the root, which is the only object in the first generation. If the root has descendants (obviously it does, hence the tree), the descendants are the second generation. You then loop through each member of the second generation. For each member in the second generation, find the descendants. The descendants of the second generation are the third generation. Listing 14 shows how to navigate an object tree using a recursive function.


Listing 14: Navigating an object tree


<html>
<script language="JavaScript">
function navigate(dog, generation) {
  var name = dog[0];
  document.write(name + "<BR>");
  generation++;
  for (var j=2; j<dog.length; j++ )  // has descendants
    navigate(dog[j], generation);
}

navigate(bo, 1);
</script>
</html>

The result of the code in Listing 14 when you run it in a Web browser is as follows.

bo
boli
bulbul
boni
spotty
mary
boy

Searching for an object in the object tree

In the previous section you have learned how you can navigate an object tree. Navigation works from the root towards the objects in the next generations. The same principle is used when you search for a particular object in the tree. You begin the search from the root, and you continue until you find a match. Sometimes, once you find a match, you can return the object without continuing the navigation until the last object.

For example, the code in Listing 15 builds an object tree like the above and then searches for a dog called bulbul. When found, the name and the color of the dog is displayed, and the function raises the flag found. This flag, when true, stops the search.


Listing 15: Searching for an object in an object tree


<html>
<head>
<title>Searching for Bulbul</title>
</head>
<body>
<script language="JavaScript">

function createDog(name, color) {
  var dog = new Array();
  dog[0] = name;
  dog[1] = color;
  return dog;
}

function append(parent, child) {
  parent[parent.length] = child;
}

var bo = createDog("bo", "brown");
var boli = createDog("boli", "black and white");
var boy = createDog("boy", "brown");
var bulbul = createDog("bulbul", "brown");
var boni = createDog("boni", "black and white");
var spotty = createDog("spotty", "black and white");
var mary = createDog("mary", "black and white");
append(bo, boli);
append(bo, boy);
append(boli, bulbul);
append(boli, boni);
append(boni, spotty);
append(boni, mary);

var found = false;
function search(dog, generation, name) {
  if (name == dog[0]) {
    found = true;
    alert("name:" + dog[0] + "\ncolor:" + dog[1]);
  }
  else if (!found) {
    generation++;
    for (var j=2; j<dog.length; j++ )   // has descendants
      if (!found)
        search(dog[j], generation, name);
  }
}

search(bo, 1, "bulbul");

</script>
</body>
</html>


Note that the search function is called by passing the root (bo), the generation (1), and the name of the search criteria ("bulbul").

Displaying an object tree

Displaying an object tree is also an important task. You can modify the code in Listing 15 to create a new function that displays an object tree. This modified code is given in Listing 16.


Listing 16: Displaying an object tree


<html>
<head>
<title>Displaying an object tree
</head>
<body>
<script language="JavaScript">

function createDog(name, color) {
  var dog = new Array();
  dog[0] = name;
  dog[1] = color;
  return dog;
}

function append(parent, child) {
  parent[parent.length] = child;
}

var bo = createDog("bo", "brown");
var boli = createDog("boli", "black and white");
var boy = createDog("boy", "brown");
var bulbul = createDog("bulbul", "brown");
var boni = createDog("boni", "black and white");
var spotty = createDog("spotty", "black and white");
var mary = createDog("mary", "black and white");
append(bo, boli);
append(bo, boy);
append(boli, bulbul);
append(boli, boni);
append(boni, spotty);
append(boni, mary);


function navigate(dog, generation) {
  var name = dog[0];
  for (var i=1; i<generation; i++)
    document.write("<IMG BORDER=1 SRC=images/blank.gif>");
  document.write(name + "<BR>");
  generation++;
  for (var j=2; j<dog.length; j++ )   // has descendants
    navigate(dog[j], generation);
}

navigate(bo, 1);

</script>
</body>


The result displayed in the Web browser is shown in Figure 1.


Figure 1: Displaying an object tree

Deleting a child object

Listing 17 lists the code for deleting an object in an object tree using the deleteElement function. However, use deleteElement with caution. For example, with the Dog family tree, the array index 0 and 1 are reserved for the name and fur color. Deleting the array index 0 or 1 will make your tree lose its structure. However, using deleteElement wisely can result in a safe object deletion, as demonstrated in the code in Listing 17. It deletes boni's third element ("spotty") from the tree.


Listing 17: Deleting a child object


<html>
<head>
<title>Deleting a child object</title>
</head>
<body>
<script language="JavaScript">

function createDog(name, color) {
  var dog = new Array();
  dog[0] = name;
  dog[1] = color;
  return dog;
}

function append(parent, child) {
  parent[parent.length] = child;
}

var bo = createDog("bo", "brown");
var boli = createDog("boli", "black and white");
var boy = createDog("boy", "brown");
var bulbul = createDog("bulbul", "brown");
var boni = createDog("boni", "black and white");
var spotty = createDog("spotty", "black and white");
var mary = createDog("mary", "black and white");
append(bo, boli);
append(bo, boy);
append(boli, bulbul);
append(boli, boni);
append(boni, spotty);
append(boni, mary);

function deleteElement(array, n) {
  //delete the nth element of array
  var length = array.length;
  if (n >= length || n<0)
    return;

  for (var i=n; i<length-1; i++)
    array[i] = array[i+1];
  array.length--;
}

function navigate(dog, generation) {
  var name = dog[0];
  for (var i=1; i<generation; i++)
    document.write("<IMG BORDER=1 SRC=images/blank.gif>");
  document.write(name + "<BR>");
  generation++;
  for (var j=2; j<dog.length; j++ )   // has descendants
    navigate(dog[j], generation);
}

navigate(bo, 1);
deleteElement(boni, 2);
navigate(bo, 1);


</script>
</body>
</html>


Figure 2 shows the object tree before and after the deletion.


Figure 2: The object tree before and after the deletion

Notice that spotty is missing from the second tree.

Event handling in an object tree

You can add an event handler to the tree so your application can respond to a mouseclick or a mouseover on an object. For example, the code in Listing 18 adds a function called handler that responds to a user click on an object. The response is a simple alert window displaying the name of the dog.


Listing 18: Adding event handling to an object tree


<html>
<head>
<title>Event handling in an object tree
</head>
<body>
<script language="JavaScript">

function createDog(name, color) {
  var dog = new Array();
  dog[0] = name;
  dog[1] = color;
  return dog;
}

function append(parent, child) {
  parent[parent.length] = child;
}

var bo = createDog("bo", "brown");
var boli = createDog("boli", "black and white");
var boy = createDog("boy", "brown");
var bulbul = createDog("bulbul", "brown");
var boni = createDog("boni", "black and white");
var spotty = createDog("spotty", "black and white");
var mary = createDog("mary", "black and white");
append(bo, boli);
append(bo, boy);
append(boli, bulbul);
append(boli, boni);
append(boni, spotty);
append(boni, mary);

function handler(name) {
  alert(name);
}

function navigate(dog, generation) {
  var name = dog[0];
  for (var i=1; i<generation; i++)
    document.write("<IMG BORDER=1 SRC=images/blank.gif>");
  document.write("<A HREF=\"javascript:handler('" + name + "')\">" +
    name + "</A><BR>");
  generation++;
  for (var j=2; j<dog.length; j++ )   // has descendants
    navigate(dog[j], generation);
}

navigate(bo, 1);

</script>
</body>
</html>


Now, instead of plain text, each object is represented by a hyperlink that can respond to the user click, as shown in Figure 3.


Figure 3: Demonstration of event handling in an object tree

Sometimes you want to change the look of the object tree when responding to the user event. For example, in a folder tree, you probably want to display an open folder icon for the folder clicked by the user. However, this poses another problem because the tree must be redrawn. The trick is to store your JavaScript code in another page. The example in Listing 19 uses a frame to store the JavaScript code and draws the object tree in a different document.


Listing 19: An example


<html>
<script language="JavaScript">

function createDog(name, color) {
  var dog = new Array();
  dog[0] = name;
  dog[1] = color;
  return dog;
}

function append(parent, child) {
  parent[parent.length] = child;
}

var bo = createDog("bo", "brown");
var boli = createDog("boli", "black and white");
var boy = createDog("boy", "brown");
var bulbul = createDog("bulbul", "brown");
var boni = createDog("boni", "black and white");
var spotty = createDog("spotty", "black and white");
var mary = createDog("mary", "black and white");
append(bo, boli);
append(bo, boy);
append(boli, bulbul);
append(boli, boni);
append(boni, spotty);
append(boni, mary);

var dogClicked="";
function handler(name) {
  dogClicked = name;
  var doc = frames[0].document;
  doc.clear();
  redraw(bo, 1, doc);
  doc.close();
}

function redraw(dog, generation, doc) {
  var name = dog[0];
  for (var i=1; i<generation; i++)
    doc.write("<IMG BORDER=1 SRC=images/blank.gif>");
  doc.write("<A HREF=\"javascript:parent.handler('" +
    name + "')\">"); 
  if (name==dogClicked)
    doc.write("<I><B>" + name + "</B></I>");
  else
    doc.write(name);
  doc.write("</A><BR>");
  generation++;
  for (var j=2; j<dog.length; j++ )   // has descendants
    redraw(dog[j], generation, doc);
}


</script>

<frameset onLoad="redraw(bo, 1, frames[0].document);
 frames[0].document.close()" rows="100%, *">
<frame name=frame1 src=frame1.html>
<frame name=frame2 src=frame2.html>
</frameset>

</html>


Note: A Netscape browser will complain if frame1.html or frame2.html is blank. Therefore, write a blank string to make it happy. Also, you need to close the document at the Frameset's onLoad event, otherwise Internet Explorer will behave unexpectedly, such as refusing to clear the document. The object tree that can change appearance is shown in Figure 4. In this figure, bulbul is printed in italic because it's the selected dog.


Figure 4: An object tree that can change its appearance.

Summary

The Array object is the only data structure available when you need to work with objects in JavaScript. Thanks to the flexibility of the Array object, you can assign an array as an element of another array. This enables you to have a linked list or an object tree.

As you have seen, object trees have many applications. Equipped with functions to create objects, append an object to another object, and delete an object, you can manipulate your object tree easily. Other functions that you need badly when using an object tree are navigate, display, and search, all of which have been demonstrated in this article.

Budi Kurniawan is a senior J2EE architect and author.


Return to the JavaScript and CSS DevCenter.

Copyright © 2009 O'Reilly Media, Inc.