Data Structures Demystified (Demystified)

If you are going to our school (Columbia University), you travel down the road a bit before seeing a fork in the road. You then have two choices: bear left and you ll be on campus; bear right and you ll be lost. What does this have to do with a tree data structure? Everything. A tree data structure is similar to the road because it provides you with a series of forks in the road that lead you down a path to reach a decision. In this chapter, you ll learn about the concept of trees, and we ll show you how to build your own tree data structure.

A Tree

When you read the word tree in the title of this chapter, you probably imagined your favorite tree covered with a full coat of green leaves. However, this doesn t truly represent the tree that we ll be talking about. Instead, envision a tree barren of leaves , where all you can see are branches stretched in all directions. Each stem terminates with only two branches, similar to a fork in the road. Those branches lead to other stems and other forks.

This type of tree is a binary tree. Binary means two, as you learned when you studied the binary numbering systems in your first computer course. The binary numbering system consists of two digits, zero and one.

A binary tree is a tree where each stem has not more than two branches (see Figure 10-1). Typically, the stem has two branches, but there can be situations when the stem has one branch or simply terminates, resulting in no additional branches.

Figure 10-1: A binary tree is a tree where each stem has no more than two branches.

Why Use a Binary Tree?

Programmers use a binary tree as a model to create a data structure to encode logic used to make complex decisions. Here s how this works. Let s say that a stem consists of a set of program instructions. At the end of the stem, the program evaluates a binary expression. You ll recall that a binary expression evaluates to either a Boolean true or false . Based on the evaluation, the program proceeds down one of two branches. Each branch has its own set of program instructions.

The basic concept of a binary tree isn t new to you because it uses Boolean logic that you learned to implement using an if statement in your program. An if statement evaluates an expression that results in a Boolean value. Depending on the Boolean value, the if statement executes one of two sets of instructions. However, a binary tree is much more than an if statement, as you ll learn in this chapter.