Trees (Stuff Formally Trained Programmers Know)

this 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

• wikipedia: tree structure
• stackoverflow: why is there no tree class in .net?
• wikipedia: recursion
• wikipedia: recursion (computer science)