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. For example, 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_inline62773; or
  2. The set consists of a root, r, and exactly two distinct binary trees tex2html_wrap_inline62929 and tex2html_wrap_inline62931, tex2html_wrap_inline62933.
The tree tex2html_wrap_inline62929 is called the left subtree  of T, and the tree tex2html_wrap_inline62931 is called the right subtree  of T.

Binary trees are almost always considered to be ordered trees  . Therefore, the two subtrees tex2html_wrap_inline62929 and tex2html_wrap_inline62931 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.

   figure14915
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. For example, Theorem gif tells us that an binary tree with tex2html_wrap_inline58277 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_inline62845 has at most tex2html_wrap_inline62957 internal nodes. Conversely, the height of a binary tree with n internal nodes is at least tex2html_wrap_inline62961. That is, the height of a binary tree with n nodes is tex2html_wrap_inline59909.

Finally, according to Theorem gif, a binary tree of height tex2html_wrap_inline62845 has at most tex2html_wrap_inline62969 leaves. Conversely, the height of a binary tree with l leaves is at least tex2html_wrap_inline62973. Thus, the height of a binary tree with l leaves is tex2html_wrap_inline62977


next up previous contents index

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