A tree is a hierarchical data structure that contains a set of nodes. The node is the the basic building block of a tree and to understand trees you have to understand nodes.
A node is a data structure that has a parent, can contain a value and can have 0 or more child nodes. A node with no child nodes is called a leaf node, or more commonly just a leaf.
A node with no parent is referred to as a root node.
Each node can have a child node of its own.
A node can have more than two children too.
By now you should grasp the basic structure of a tree, but what are they good for and where are they used? Well the good news is that trees are all around you. Your operating system’s directory structure is a tree, HTML and XML are both trees. Your filing cabinet could even be considered a tree. A linked list is also a form of tree, where each node has exactly one child node. Let’s take a look at some more trees.
You belong to a tree too!
and of course…
Implementation of Trees
Programming languages have varying levels of support for tree-like data structures. The abstract idea of a tree and the implementation of one are often very different things. Pretty much any nestable data structure can suffice for an ad-hoc tree implementation. For example here’s one of the simplest trees you can implement in Python.
class Node: def __init__(self, value=None, *args): self.value = value self.children = args # A tree can then be defined as tree = Node('root', Node(1), Node(2))
Scheme makes it quite a bit easier, both code and data are represented using trees (actually lists).
(define tree (cons 1 2)) tree ;>>> (1 . 2) (define nested-tree (cons 1 (cons 2 3))) nested-tree ;>>> (1 2 . 3)
If you’re wondering why the nested-tree looks like a list, remember that lists are a subset of trees.
I didn’t get to heavily into how trees are implemented in any particular language. Mostly this is because the implementations of tree data structures varies widely from one language to the next and sometimes there are even multiple implementations of trees in a single language.
Many decisions go into a tree implementation and the tools that work with them. Because of this there are many different types of trees, each with its own strengths and weaknesses and tools for manipulating them. Future WITH articles will will go deeper into trees, their implementations and characteristics.