Collections - Java Software Solutions: Foundations of Program Design - page 631

SR 13.12 What is a stack?
SR 13.13 Show the contents of a stack after the following operations are per-
formed. Assume the stack is initially empty.

push (5);
push (21);
pop();
push (72);
push (37);
push (15);
pop();

SR 13.14 What is the Stack class?

13.4 Non-Linear Data Structures

Some data structures are considered to be non-linear data structures, because
their data is not organized linearly. This section examines two types of non-linear
structures: trees and graphs.

Trees
A tree is a non-linear data structure that consists of a

root node and
potentially many levels of additional nodes that form a hierarchy. All
nodes other than the root are called

KEY CONCEPT
A tree is a non-linear data structure
that organizes data into a hierarchy.

internal nodes . Nodes that have no
children are called leaf nodes . Figure 13.8 depicts a tree. Note that we
draw a tree "upside down," with the root at the top and the leaves at
the bottom.

In a general tree like the one in Figure 13.8, each node could have many child
nodes. As we mentioned in Chapter 9, the inheritance relationships among classes
can be depicted using a general tree structure.
In a binary tree , each node can have no more than two child nodes. Binary trees
are useful in various programming situations and usually are easier to implement
than general trees. Technically, binary trees are a subset of general trees, but they
are so important in the computing world that they usually are thought of as their
own data structure.
The operations on trees and binary trees vary, but minimally include adding
and removing nodes from the tree or binary tree. Because of their non-linear
nature, trees and binary trees are implemented nicely using references as dynamic
links. However, it is possible to implement a tree data structure using a fixed
representation such as an array.