Contents  Introduction  Recursion  Introduction to Trees  General Trees  Adding, Removing  and Processing  Nodes  Conclusion  Source code  Printable version  Discuss this article  in the forums The Series  Introduction  Binary Trees

Introduction to Trees

Trees are used for so much in computer programming. They can be used for improving database search times (binary search trees, 2-3 trees, AVL trees, 2-3-4 trees, red-black trees), Game programming (minimax trees, decision trees, pathfinding trees), 3d graphics programming (BSP trees, quadtrees, octrees), Arithmetic Scripting languages (arithmetic precedence trees), Data compression (Huffman trees), and even file system's (B-trees, sparse indexed trees, trie trees). This article will go through the basic tree structures first (general trees), and then go into the specifics of some of the more popular trees, but not all of those listed above. A few of the trees above are quite complex and go beyond the scope of this article.

Computer Representations of Trees

Imagine a linked list. The simplest implementation uses only one class, a Node, and each node points to the next node in the list. In more sophisticated implementations, the node may even point to the previous node in the list as well. This implementation treats any given node as the start of a list when accessed externally by the client. The more abstracted implementations use a general container class that points to its first node.

The box represents the Linked List class, and the circles are the nodes. Trees are the same way in that they are made up of a collection of nodes. As with linked lists, a tree can be referenced by any one of it’s nodes, or a general tree container class. Whichever implementation you choose is all up to you and your needs. This tutorial does not assume one particular way over another, but all tree diagrams I will draw in this document do not show the container (box) class for reasons of clarity and brevity. It looks better without the box getting in the way.

Parts of a Tree

Trees have one discrete starting point. This is called the root node. As with a linked list, each node points to another node, but the difference is that a tree node can point to more than one node, whereas a linked list node can only point to one node. Each of the nodes that any given node points to is called a child node, with the possible exception of a parent node. Some tree implementations maintain pointers to their parents to ease traversal, but it is not explicitly required by a tree. Any node that does not have any children is called a leaf node. Here is a pictorial representation of a theoretical tree:

Note that computer trees are typically drawn from the Root-down. Node 1 would be considered the root, and 2, 3, and 4 are children of the root. Node 1 is their parent. Note also that node 2 is a parent to 5 and 6, and 4 is a parent to 7. Thus nodes 2 and 4 act as both children and parents. Nodes 3, 5, 6 and 7 are leaf nodes. It is important to note that every node in the tree is also a tree by itself. We usually call these sub-trees. Take, for example, node number 2. Node 2 is the root of a sub-tree that only has three nodes. Node's 5, 6 and 7 are all sub-trees with no children.

Hierarchy of a tree

When you think of a linked list, it is typically a long horizontal string of nodes, each one connected to the next. This gives it a shape roughly analogous to a straight memory array. However, trees cannot be easily thought of in terms of a straight line, so a tree has what are called Height Levels. The root node has a level of 0 (or 1, depending on how you count), and all children of any given node have a height level of one greater than the parent. All children of any given node have the same height level.

Here is an example of height levels:

Next : General Trees