Java Reference
In-Depth Information
Chapter 17
Binary Trees
Introduction
17.1 Binary Tree Basics
Node and Tree Classes
In this chapter we will explore a new data structure known as a binary
tree . Like linked lists, binary trees are composed of interconnected nodes.
But unlike linked lists, which involve a one-dimensional (straight line)
sequence, binary trees can branch in two directions, which gives them a
two-dimensional structure.
17.2 Tree Traversals
Constructing and Viewing a Tree
17.3 Common Tree Operations
Sum of a Tree
Counting Levels
Counting Leaves
A surprising number of data relationships can be represented using binary
trees.Any relationship that involves a division into two paths can be rep-
resented with a binary tree.Thus, binary trees can store information that
involves a yes/no relationship, a high/low relationship, or a first and second
relationship. For example, arithmetic expressions have operators like
and * that have a first operand and a second operand. Binary trees are a
natural structure for storing such relationships. Such trees are often
referred to as expression trees because they capture the structure of the
arithmetic expressions they represent.
17.4 Binary Search Trees
The Binary Search Tree Property
Building a Binary Search Tree
The Pattern x = change(x)
Searching the Tree
Binary Search Tree Complexity
17.5 SearchTree<E>
Because binary trees are linked structures, they share many of the useful
properties of linked lists. It is fairly easy to grow or shrink a binary tree by
rearranging the links of the nodes.
After looking at basic binary tree terminology and basic binary tree oper-
ations, we will explore a particular kind of binary tree known as a binary
search tree. Binary search trees are used to capture high/low relationships
and provide an efficient structure for keeping track of data that have a
natural ordering.The TreeSet and TreeMap structures that are part of
the collections framework are implemented as binary search trees.
As we study binary trees, we will find that recursion comes into play quite
often. Many binary tree operations are best written recursively.
981
 
 
Search WWH ::




Custom Search