Java Reference
In-Depth Information
Chapter 8
Introduction to Binary Trees
In this chapter, we will explain the following:
•
The difference between a tree and a binary tree
•
How to perform pre-order, in-order, and post-order traversals of a binary tree
•
How to represent a binary tree in a computer program
•
How to build a binary tree from given data
•
What a binary search tree is and how to build one
•
How to write a program to do a word-frequency count of words in a passage
•
How to use an array as a binary tree representation
•
How to write some recursive functions to obtain information about a binary tree
•
How to delete a node from a binary search tree
8.1 Trees
A
tree
is a finite set of nodes such that the following are both true:
•
There is one specially designated node called the
root
of the tree.
•
The remaining nodes are partitioned into
m
³ 0 disjoint sets T
1
, T
2
, …, T
m
, and each of these
sets is a tree.
The trees T
1
, T
2
, …, T
m
, are called the
subtrees
of the root. We use a recursive definition since recursion is an innate
characteristic of tree structures. Figure
8-1
illustrates a tree. By convention, the root is drawn at the top, and the tree
grows downward.
Search WWH ::
Custom Search