Trees (Stuff Formally Trained Programmers Know)
A quick introduction to the Tree data structure and recursion with examples of how to navigate them.
Join the DZone community and get the full member experience.
Join For Freethis post is one in a series about stuff formally trained programmers know–the rest of the series can be found here .
trees
this post will look at the mighty tree, which is more a pattern than a specific data structure. the reason to understand the pattern is that so many of the data structures we will look at in the future use it, and a good understanding of it provides a strong basis to work from.
as a computer user, though, you already have seen and used a tree structure—you may have just not known it. the most common form of it is the file system, where you have a root (i.e.
/
or
c:\
) and that has various folders under it. each folder itself can have folders, until you end at an empty folder or a file.
this is the way a tree structure works too: you start with a root, then move to nodes and finally end with leaves.
in the basic concept of a tree there are no rules on the nodes and the values they contain, so a node may contain zero, one, two, three or a hundred other nodes.
what makes a tree really powerful, is that it really is a collection of trees. i.e. if you take any node it is in itself a tree and so the algorithms used to work with a tree work with each node too. this enables you to work with a powerful computer science concept, recursion.
recursion
recursion is a concept that lacks a real world equivalent and so can be difficult to grasp initially. at its simplest, for these posts, it is a method or function which calls itself, until instructed to stop. for example, you might write a function called
getfiles
which takes in a path to a folder and returns an array of filenames. inside
getfiles
it loops over all the files in the folder and adds them to a variable to return. then it loops over all the folders in that folder and for each folder it finds, it calls
getfiles
again.
function getfiles(path){
var result = [];
fs.readdirsync(path).each(file => result.push(file)); // get all files using node, and push them to the result array.
var directories = fs.getdirectoriessync(path); // not real node call - for example.
directories.each(directory =>{
var files = getfiles(directory); // calling itself.
files.each(file => result.push(file));
});
return result;
}
function ienumerable<string> getallfiles(string path) // changed to getallfiles so it doesn't get too confusing with the built in getfiles
{
var result = new list<string>();
result.addrange(directory.getfiles(path));
foreach (var directory in directory.getdirectories(path))
{
result.addrange(getallfiles(directory)); // recursively calling itself
}
return result;
}
implementations
it doesn't make sense to talk about coding implementations at this point since this is more a pattern than a structure and we would need a lot more information on what we want to achieve to do actually go through a code implementation. that said, it is interesting to see where trees are used: - file systems - document object models (like html or xml)
references
Published at DZone with permission of Robert Maclean, DZone MVB. See the original article here.
Opinions expressed by DZone contributors are their own.
Comments