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