O'Reilly logo

A Concise Introduction to Data Structures using Java by Mark J. Johnson

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 8

Trees

Trees are non-linear, hierarchical, and recursive data structures with a wide range of applications. In fact, we have already seen call trees in Section 7.2 as a useful model for tracking recursive computations.

8.1 Definitions and Examples

A tree is a (possibly empty) set of elements called nodes with one node designated as the root. The root is connected via edges to some number of child nodes, each of which is itself the root of a subtree. Thus, trees are naturally recursive. A leaf is a node with no children; an internal node is any non-leaf. A branch in a tree is a path of connected edges starting at the root and ending in a leaf. Trees are usually drawn with the root at the top.

For example, in the tree below, 31 is the ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required