Trees are very useful data structures. With little effort, we can think of several situations trees are useful for. Think of ancestry trees, your computer file system, and how about a tree of all possible solutions to a chess game.
In their general form, trees are data structures in which data is stored in nodes. Nodes are connected together with edges.
One thing to keep in mind, there are no circles in trees. In other words, you can only get from one node to another only by one path. In fact, if there are multiple paths between any two nodes the data structure becomes a graph, but let’s save this for another discussion.
A rooted tree is a special case of trees in which we designate a node (any node) to be the root of the tree. This helps with computers because it is convenient to have a consistent reference for your data structure, similar to the head of a linked list.
In a rooted tree, every node has a parent except the root.
Now we need to define more terms to be able to discuss trees fluently:
- A path is any sequence of connected edges.
- A node p has a child node c, if c is the first node encountered on a path from p.
- A leaf is a node with no children.
- Siblings are all nodes with the same parent.
- Ancestors are all nodes on a path from node n to root. Including n. Think of a family tree.
- Length of a path is the number of edges in that path.
- Depth of a node n is the length of the path from n to the root.
- Height of a node n is the length of path from n to its deepest leaf. The height of a tree is the height of the root.
The diagram below helps you visualize the definitions above.
After observing the rooted tree diagram, we could imagine many applications to make use of trees. Also, from the diagram, we could envision a simple way to represent trees in computers and have computers do very interesting stuff using trees.
In the next post, we will discuss implementing trees in code. Then we will define several ways to iterate though or traverse a tree.
Stay tuned in to discuss tree types and how to make the best use of computer time and space using trees.