Tree
Tree
Linked lists are linear structures and it is difficult to
use them to organize a hierarchical representation
of objects.
Although stacks and queues reflect some hierarchy,
they are limited to only one dimension.
To overcome this limitation, we create a new data
type called a tree that consists of nodes and arcs.
Unlike natural trees, these trees are depicted upside
down with the root at the top and the leaves at the
bottom.
Tree
Linear lists are useful for serially ordered data.
(e0, e1, e2, …, en-1)
Days of week.
Months in a year.
Students in this class.
Trees are useful for hierarchically ordered data.
Employees of a corporation.
President, vice presidents, managers, and so on.
Java’s classes.
Object is at the top of the hierarchy.
Subclasses of Object are next, and so on.
Tree
The root is a node that has no parent; it can have on
ly child nodes. Leaves, on the other hand, have no c
hildren.
A tree can be defined recursively as the following:
1. Am empty structure is an empty tree
2. If t1, t2, …, tk are disjoint trees, then the structure whose ro
ot has its children the roots of t1, t2, …, tk is also a tree
3. Only structures generated by rules 1 and 2 are trees.
Tree
The element at the top of the hierarchy is the
root.
Elements next in the hierarchy are the
children of the root.
Elements next in the hierarchy are the
grandchildren of the root, and so on.
Elements that have no children are leaves.
