Java Reference
In-Depth Information
Here is a diagram of a simple binary tree of integer values.
12
18
7
23
4
13
As we did with linked lists, we refer to each different data value as a node. This
tree has a total of six nodes. Some people joke that computer scientists view the
world upside down, so imagine turning the diagram around the other way:
23
4
13
18
7
12
Viewed upside down, the diagram looks more like a tree. At the bottom of this
structure is a node storing the value
12
. We refer to this value as the
root
of the tree.
All nodes are connected either directly or indirectly to the root node. In this diagram,
the nodes that store the values
12
,
18
, and
7
have connections branching out and up.
These nodes are referred to as
branch nodes
. The nodes storing the values
23
,
4
, and
13
are at the top of this tree and have nothing above them. They are referred to as leaf
nodes
or
leaves
of the tree.
Before we try to formally define these terms, let's begin with a formal definition
of a binary tree.
Binary Tree
A binary tree is either
• an empty tree or
• a root node (typically storing some data) that refers to two other trees
known as the left subtree and the right subtree.
The key phrase in this definition is “subtree.” The tree is composed of smaller
trees. This definition is recursive. The base case or simple case is an empty tree that
has no nodes at all. The recursive case describes a tree of the following form:
Search WWH ::
Custom Search