Data Structures and the Java Collections Framework, Third Edition

CHAPTER 9

Binary Trees

In this chapter we "branch" out from the linear structures of earlier chapters to introduce what is essentially a non-linear construct: the binary tree. This brief chapter focuses on the definition and properties of binary trees, and that will provide the necessary background for the next four chapters. Chapters 10 through 13 will consider various specializations of binary trees: binary search trees, AVL trees, decision trees, red-black trees, heaps, and Huffman trees. There is no question that the binary tree is one of the most important concepts in computer science. Finally, to round out the picture, Chapter 15 presents the topic of trees in general.

CHAPTER OBJECTIVES

1. Understand binary-tree concepts and important properties, such as the Binary Tree Theorem and the External Path Length Theorem.
2. Be able to perform various traversals of a binary tree.

9.1 Definition of Binary Tree

The following definition sets the tone for the whole chapter:

A binary tree t is either empty or consists of an element, called the root element, and two distinct binary trees, called the left subtree and right subtree of t.

We denote those subtrees as leftTree(t) and rightTree(t), respectively. Functional notation, such as leftTree(t), is utilized instead of object notation, such as t.leftTree(), because there is no binary-tree data structure. Why not? Different types of binary trees have widely differing methods—even different parameters lists—for such operations as inserting ...