Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAPTER 10 Binary Trees

10.1Introduction

The binary tree is a fundamental structure in mathematics and computer science. Some of the terminology

of rooted trees, such as, edge, path, branch, leaf, depth, and level number, will also be used for binary trees.

However, we will use the term node, rather than vertex, with binary trees. We emphasize that a binary tree is not

a special case of a rooted tree; they are different mathematical objects.

10.2Binary Trees

Abinary treeTis defined as a finite set of elements, callednodes, such that:

(1)Tis empty (called thenull treeorempty tree), or

(2)T contains a distinguished nodeR, called therootofT, and the remaining nodes ofTform an

ordered pair of disjoint binary treesT 1 andT 2.

IfTdoes contain a rootR, then the two treesT 1 andT 2 are called, respectively, the left and right subtrees ofR.

IfT 1 is nonempty, then its root is called theleft successorofR; similarly, ifT 2 is nonempty, then its root is called

theright successorofR.

The above definition of a binary treeTis recursive sinceTis defined in terms of the binary subtreesT 1 andT 2.

This means, in particular, that every nodeNofTcontains a left and a right subtree, and either subtree or both

subtrees may be empty. Thus every nodeNinThas 0, 1, or 2 successors. A node with no successors is called a

terminalnode. Thus both subtrees of a terminal node are empty.

Picture of a Binary Tree

A binary treeT is frequently presented by a diagram in the plane called apictureofT. Specifically, the

diagram in Fig. 10-1(a) represents a binary tree as follows:

(i) Tconsists of 11 nodes, represented by the lettersAthroughL, excludingI.

(ii) The root ofTis the nodeAat the top of the diagram.

(iii) A left-downward slanted line at a nodeNindicates a left successor ofN; and a right-downward slanted

line atNindicates a right successor ofN.

235

Copyright © 2007, 1997, 1976 by The McGraw-Hill Companies, Inc. Click here for terms of use.