Working with Object Trees: Part Two
Pages: 1, 2, 3
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
