10: Trees

Usually, because it combines the advantages of two other structures:
? An ordered array and
? A linked list.
You can search a tree quickly, as you can an ordered array, and you can also insert and delete items quickly, as
you can with a linked list.
In computer programs, nodes often represent such entities as people, car parts, airline reservations, and so on.
Edges are likely to be represented in a program by references, if the program is written in Java.
Typically, there is one node in the top row of a tree, with lines connecting to more nodes on the second row,
even more on the third, and so on. Thus, trees are small on the top and large on the bottom.
This may seem upside-down compared with real trees, but generally a program starts an operation at the small
end of the tree, and it’s (arguably) more natural to think about going from top to bottom, as in reading text.
There are different kinds of trees.
Tree Terminology
Many terms are used to describe particular aspects of trees. Fortunately, most of these terms are related to realworld
trees or to family relationships (as in parents and children), so they’re not hard to remember. Figure 2
shows many of these terms applied to a binary tree. H, E, I, J, and G are leaf nodes.
Figure 2: Tree terms.
College of Information Technology / Software Department
………………………………………………………..
Data Structures / Second Class / 2016-2017
LEC. 9
51
Path
Think of someone walking from node to node along the edges that connect them. The resulting sequence of
nodes is called a path.
Root
The node at the top of the tree is called the root. There is only one root in a tree. For a collection of nodes and
edges to be defined as a tree, there must be one path from the root to any other node. Figure 3 shows a nontree.
You can see that it violates this rule.