Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Binary Trees

 

In this section we consider an extremely important and useful category of tree structure--binary trees . A binary tree is an N-ary tree for which N is two. Since a binary tree is an N-ary tree, all of the results derived in the preceding section apply to binary trees. However, binary trees have some interesting characteristics that arise from the restriction that N is two. E.g., there is an interesting relationship between binary trees and the binary number system. Binary trees are also very useful for the representation of mathematical expressions involving the binary operations such as addition and multiplication.

Binary trees are defined as follows:

Definition (Binary Tree)  A binary tree   T is a finite set of nodes  with the following properties:
  1. Either the set is empty, tex2html_wrap_inline63628; or
  2. The set consists of a root, r, and exactly two distinct binary trees tex2html_wrap_inline63784 and tex2html_wrap_inline63786, tex2html_wrap_inline63788.
The tree tex2html_wrap_inline63784 is called the left subtree  of T, and the tree tex2html_wrap_inline63786 is called the right subtree  of T.

Binary trees are almost always considered to be ordered trees  . Therefore, the two subtrees tex2html_wrap_inline63784 and tex2html_wrap_inline63786 are called the left and right subtrees, respectively. Consider the two binary trees shown in Figure gif. Both trees have a root with a single non-empty subtree. However, in one case it is the left subtree which is non-empty; in the other case it is the right subtree that is non-empty. Since the order of the subtrees matters, the two binary trees shown in Figure gif are different.

   figure15569
Figure: Two Distinct Binary Trees

We can determine some of the characteristics of binary trees from the theorems given in the preceding section by letting N=2. E.g., Theorem gif tells us that an binary tree with tex2html_wrap_inline59063 internal nodes contains n+1 external nodes. This result is true regardless of the shape of the tree. Consequently, we expect that the storage overhead of associated with the empty trees will be O(n).

From Theorem gif we learn that a binary tree of height tex2html_wrap_inline63700 has at most tex2html_wrap_inline63812 internal nodes. Conversely, the height of a binary tree with n internal nodes is at least tex2html_wrap_inline63816. I.e., the height of a binary tree with n nodes is tex2html_wrap_inline60675.

Finally, according to Theorem gif, a binary tree of height tex2html_wrap_inline63700 has at most tex2html_wrap_inline63824 leaves. Conversely, the height of a binary tree with l leaves is at least tex2html_wrap_inline63828. Thus, the height of a binary tree with l leaves is tex2html_wrap_inline63832


next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.