Microsoft Visual C# 2008 Step By Step by Unknown

Author:Unknown
Language: eng
Format: epub
Tags: c#

Empty trees

FIGURE 18-1 A binary tree.

The real power of binary trees becomes evident when you use them for sorting data. If you start with an unordered sequence of objects of the same type, you can construct an ordered binary tree and then walk through the tree to visit each node in an ordered sequence. The algorithm for inserting an item I into an ordered binary tree T is shown here:

If the tree, 7~, is empty Then

Construct a new tree T with the new item I as the node, and empty left and right subtrees Else

Examine the value of the current node, N, of the tree, T If the value of N is greater than that of the new item, I Then

If the left subtree of T is empty Then

Construct a new left subtree of T with the item I as the node, and empty left and right subtrees Else

Insert I into the left subtree of T End If Else

If the right subtree of T is empty Then

Construct a new right subtree of T with the item I as the node, and empty left and right subtrees Else

Insert I into the right subtree of T End If End If End If

www.it-ebooks.info

Part III Creating Components

Notice that this algorithm is recursive, calling itself to insert the item into the left or right subtree depending on how the value of the item compares with the current node in the tree.

Note The definition of the expression greater than depends on the type of data in the item and node. For numeric data, greater than can be a simple arithmetic comparison, for text data it can be a string comparison, but other forms of data must be given their own means of comparing values. This is discussed in more detail when you implement a binary tree in the upcoming section titled "Building a Binary Tree Class by Using Generics."

If you start with an empty binary tree and an unordered sequence of objects, you can iterate through the unordered sequence, inserting each object into the binary tree by using this algorithm, resulting in an ordered tree. Figure 18-2 shows the steps in the process for constructing a tree from a set of five integers.

FIGURE 18-2 Constructing an ordered binary tree.

After you have built an ordered binary tree, you can display its contents in sequence by visiting each node in turn and printing the value found. The algorithm for achieving this task is also recursive:

If the left subtree is not empty Then

Display the contents of the left subtree End If

Display the value of the node

If the right subtree is not empty

www.it-ebooks.info

Chapter 18 Introducing Generics 341

Then

Display the contents of the right subtree End If

Figure 18-3 shows the steps in the process for outputting the tree constructed in Figure 18-2. Notice that the integers are now displayed in ascending order.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.