The Tree Data Structure
What Is a Tree?
A tree is a finite set of one or more nodes in which
A tree is a data structure used to model data such that related data is in close proximity called branches. A tree can also be used to model hierarchical data.
Figure 1. A Family Tree
Let's look at Figure 1. There are 3 sub-trees from the root, Clara. These sub-trees -- Esther, Augustus, and James, are disjoint, that means they cannot have any nodes that belong to more than one of the sub-trees. Each node can have only 1 parent. Notice that when we divide the tree into sub-trees, each of the nodes becomes the root of the sub-tree. Normally, we draw trees with the root at the top, but we don't have to draw them that way. Each node represents some item of information. The relationship between nodes is shown using a line called a branch. A tree may be referred to by the name of its root node.
The degree of a node is the number of sub-trees of the node. The degree of a tree is the maximum degree of the nodes of the tree. A node with degree zero is a terminal node or leaf node. A node that has sub-trees is the parent of its sub-trees, and the sub-trees are children of its parent. Children of the same parent are called siblings. The ancestors of a node are all the nodes along the path from the root to the node. The descendents of a node are all the nodes in its sub-trees.
We define levels of a tree by letting root be at level 1. (Some texts may define root at level 0, but you will see later why it may be preferable to let root be at level 1 instead.) All subsequent nodes have the level of its parent plus 1. The height or depth of a tree is the maximum level of all nodes in the tree.
Tree Representation
There are many ways to represent a tree. We can represent it pictorially as the example above shows. We can also use a list representation. With the list representation, the tree is a list in which each sub-tree is also a list. Below is the list representation of the sub-tree Esther.
Esther (Andrew, Ramona(Rod, Regina, JB(Charles, Peta, Loni), Sharon), Raymond)
How can we represent trees in memory? One way is using the left child and right sibling methodology. With this method, each node has a reference to its leftmost child and closest right sibling. Let's use the tree in Figure 2 below as an example.
Figure 2. Tree Example
The table below outlines the left child and right sibling for each node.
|
Node |
Left Most Child |
Closest Right Sibling |
|
A |
B |
- |
|
B |
E |
C |
|
E |
K |
F |
|
K |
- |
L |
|
F |
- |
- |
|
L |
- |
- |
|
C |
G |
D |
|
G |
- |
- |
|
D |
H |
- |
|
H |
M |
I |
|
M |
- |
- |
|
I |
- |
J |
|
J |
- |
- |
If this table were drawn pictorially, we would have the following
Notice that with this approach, we can convert any n-ary tree to a degree 2 tree. (The degree of a tree can be expressed as n-ary where n is the degree of the tree.) If a tree is of degree 2, it is called a bi-nary or binary tree.
Self Test
Answer these questions using Figure 2.