Trees are a very useful data structure. Many different kinds of trees are used in Computer Science. We shall study just a few of these.
Nature Lover’s View Of A Tree
root branches leaves
Computer Scientist’s View
branches leaves root nodes
Branches meet at nodes.
Linear Lists And Trees
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.
C++’s classes.
Object is at the top of the hierarchy.
Subclasses of Object are next, and so on.
Hierarchical Data And Trees
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 at the lowest level of the hierarchy are the leaves.
great grand child of root grand children of root children of root Object Number Throwable OutputStream Integer Double Exception FileOutputStream RuntimeException root
Definition
A tree t is a finite nonempty set of elements.
One of these elements is called the root.
The remaining elements, if any, are partitioned into trees, which are called the subtrees of t.
Subtrees
Object Number Throwable OutputStream Integer Double Exception FileOutputStream RuntimeException root
Leaves
Object Number Throwable OutputStream Integer Double Exception FileOutputStream RuntimeException
Some texts start level numbers at 0 rather than at 1.
Root is at level 0.
Its children are at level 1.
The grand children of the root are at level 2.
And so on.
We shall number levels with the root at level 1.
Object Number Throwable OutputStream Integer Double Exception FileOutputStream RuntimeException 3 2 1 1 0 0 1 0 0 Degree of tree = 3.
Note that it is possible to have a tree whose degree is (say) 3 and whose root has a
degree that is < 3.
Binary Tree
Finite (possibly empty) collection of elements.
A nonempty binary tree has a root element.
The remaining elements (if any) are partitioned into two binary trees.
These are called the left and right subtrees of the binary tree.
Differences Between A Tree & A Binary Tree
No node in a binary tree may have a degree more than 2, whereas there is no limit on the degree of a node in a tree.
A binary tree may be empty; a tree cannot be empty.
The subtrees of a binary tree are ordered; those of a tree are not ordered.
Differences Between A Tree & A Binary Tree
a b a b Are different when viewed as binary trees.
Are the same when viewed as trees. The subtrees of a binary tree are ordered; those of a tree are not ordered.
Arithmetic Expressions
(a + b) * (c + d) + e – f/g*h + 3.25
Expressions comprise three kinds of entities.
Operators (+, -, /, *).
Operands (a, b, c, d, e, f, g, h, 3.25, (a + b), (c + d), etc.).
Delimiters ((, )).
Operator Degree
Number of operands that the operator requires.
Binary operator requires two operands.
a + b
c / d
e - f
Unary operator requires one operand.
+ g
- h
Comments