Software Design Using C++
Sixth Advanced Windows Forms Example
The Goal
The goal is to produce a Windows forms app that allows the user to display a binary search
tree and to insert new items into it, one by one. This is somewhat like our previous
Fifth Advanced Windows Forms Example, which displayed a hash table
and allowed the user to manipulate the hash table. However, in that example we used an object of
our own hash table class and then added the ability to display the table in a ListView .
In our binary search tree example we will use a TreeView to both store and display the
data. No separate data structure will be used to hold the tree data, though this could be done
if desired.
Our app will start with an empty TreeView object and allow the user to add new strings to
the tree in such a fashion as to maintain it as a
binary search tree.
Recall that a binary tree allows each node of the tree to have a left child node and/or a right child node
under it. Thus a binary tree is ordered, with the left child distinguished from the right.
A binary search tree adds the property that with every node N of the tree, data anywhere in the left
subtree of N is less than the data in node N and data anywhere in the right subtree of N is greater
than the data in node N. This makes it pretty easy to look up data later. Note that we assume that
we will never try to put duplicate data into our binary search tree. (Duplicate data can be handled
but let's avoid that complication.)
One complication that we cannot avoid is that a TreeView object is designed to handle
a general, unordered tree. Such an object can allow a huge number of nodes under a given node, unlike
the limit of 2 imposed by binary trees. Although there is some order used when displaying the
TreeView data, it is top to bottom, not left to right as we are used to using with binary
trees. However, with a good imagination you can look at the display of the object sideways, with
the left side of the display holding the root (top) of the tree. With a little practice you can
easily see the binary tree structure. If you look at any child nodes immediately to the right
of a given node N, the child node on the top will be considered to be the right child of N
and the child node on the bottom will be considered to be the left child of N.
Remember: with a binary tree we have a maximum of two child nodes.
Since a node N might have only a left child (or only a right child), how will we be able to display
this situation in a TreeView ? If we only listed one child node immediately to the right
of node N, we could not tell if we meant it to be the left or right child of N.
Because of this, anytime a node N has just one child node (left or right), we will actually create
the other child node with an empty string for the displayed text. Thus, anytime we see a line from
a node to nothing (an empty node), it is just this case where we need to be able to tell if the
sibling node is the left or right child of the parent node.
Look at this picture of a binary tree in the completed app.
You can see that the user has just finished inserting the string "gerald" into the binary search tree.
The root node contains the data matthew. (All of the data used by this app will be string data. Here
we used people's first names.) The left child node of the root contains the name anthony, while the right
child contains the name rebecca. Notice that the binary search tree property holds: the string anthony
is alphabetically less than matthew, while rebecca is greater than matthew. Furthermore, all of the
names in the left subtree (such as karen and allison) are less than matthew, while all of the names
in the right subtree are greater than matthew. Of course, this property has to hold at all nodes
of the binary tree for it to be a binary search tree. Let's check the node containing timothy: there
are no names in the left subtree (notice that line to an empty node), so nothing needs to be checked
there, while the names in the right subtree (walter and valerie) are greater than timothy.
All in all, this sounds complicated, but there is an easy way to insert the data one item at a time
so as to get a binary search tree: Put the first item into the root node. With each new item,
compare to the root data, if the new item is bigger, go right; if smaller, go left.
When you come to an existing node of the tree, do the same thing: compare the new data to the item in
the current node. If the new item is bigger, go right; otherwise, go left. If you reach an empty node,
insert the new item there. This is essentially the algorithm our app will use to insert data so as
to get a binary search tree.
Getting Started
Create a new Windows forms app, named perhaps BinaryTree.
Change FormBorderStyle to Fixed3D, MaximizeBox to False, and Text to "Binary Search Tree Demo".
Resize the form as needed so that it is about the same size as that shown in
our picture of the running app.
Designing the Form
Go ahead and place the controls on the form. As you can see, there is a label with "New Item:"
as the text and next to it a TextBox. Make the name of the TextBox to be ItemTextBox and clear out
its Text property. To the right of these is a button.
Name it InsertButton and change its Text property to "Insert".
Also drag a TreeView control to the form and resize it to fill most of the rest
of the form. Change its name to BinaryTreeView.
You can adjust the TabIndex and TabStop properties of the controls if you wish.
It would make sense for the text box to have TabIndex 1, the button TabIndex 2, and the
TreeView TabIndex 3.
Save all of your files. Also right click on the new project in Solution Explorer
and set this project to be the startup project.
The Coding
Double click on the button so as to create the outline of a click handler function for it.
Then, in Form1.h change it to a function prototype in our usual way. That is,
change it to match the following, which shows the very end of the Form1.h file,
with the }; marking the end of the Form1 class and the final
} indicating the end of the BinaryTree namespace.
private: System::Void InsertButton_Click(System::Object * sender, System::EventArgs * e);
};
}
|
The only thing that we need to add to the Form1.cpp file is the code for the
click handler, but it is somewhat complex. Put the following at the end of the Form1.cpp file.
/* This is the click handler for the insert button.
It looks up the data item in ItemTextBox and inserts it at the proper place in
the TreeView object on our form, so as to maintain it as a binary search tree.
Our convention is that the first child under a node is the right child (index 0
in the nodes collection) and the second child is the left child (index 1 in the
nodes collection).
*/
System::Void Form1::InsertButton_Click(System::Object * sender, System::EventArgs * e)
{
TreeNodeCollection * Root, * Current, * Parent;
String * Item, * ParentString;
int ParentIndex;
bool Inserted;
Item = ItemTextBox->Text;
Root = BinaryTreeView->Nodes;
if (Root->Count == 0)
Root->Add(Item);
else
{
Current = Root;
ParentIndex = 0;
Inserted = false;
while (! Inserted)
{
Parent = Current;
Current = Current->Item[ParentIndex]->Nodes;
ParentString = Parent->Item[ParentIndex]->Text;
if (Current->Count == 0)
{
if (String::Compare(Item, ParentString) < 0) // Insert Item as left child.
{
Current->Add(S""); // Use empty string for an empty node.
Current->Add(Item);
}
else // Insert Item as right child.
{
Current->Add(Item);
Current->Add(S"");
}
Inserted = true;
}
else // Count must be 2.
{
if (String::Compare(Item, ParentString) < 0) // Insert in left subtree.
{
if (Current->Item[1]->Text->get_Length() == 0) // Empty node, insert here
{
Current->Item[1]->set_Text(Item); // 1 for left
Inserted = true;
}
else
ParentIndex = 1; // Indicate that we go left before looping around.
}
else // Insert in right subtree.
{
if (Current->Item[0]->Text->get_Length() == 0) // Empty node, insert here
{
Current->Item[0]->set_Text(Item); // 0 for right
Inserted = true;
}
else
ParentIndex = 0; // Indicate that we go right before looping around.
}
} // bottom of count == 2 case
} // bottom of while loop
}
}
|
Although the comments in the above function help some, let's take a more careful look at this code.
Much of the code uses the pointers Root , Current , and Parent .
Judging by their type, these are allowed to point to an object of type TreeNodeCollection .
Each node of a tree has a Nodes property which can contain a TreeNodeCollection ,
namely the collection of all child nodes for the given node.
We begin by getting the user's string from ItemTextBox . This is the item that we want
to insert into the binary search tree for this particular call of the function.
Then we use Root = BinaryTreeView->Nodes to set Root to point at the
top-level node collection. Although a TreeView will let you put lots of nodes at this
level, we put just one here, namely the root node for our whole tree. You can see that we check the
Count property on this collection, and if it is zero we insert our new item here (as the
root node) by using Root->Add(Item) .
If we were not able to insert the new item at the root of the tree, we then loop through
successive node collections, going right or left as required by a binary search tree, until we
find the correct location to insert this new item. We prepare for this loop by
having Current point at the node collection containing the root node.
We then set ParentIndex to 0 to indicate that the parent node (root node in this case)
is the one at index 0 (the topmost, which we interpret as the rightmost) and not at index 1
(which is for the bottom node, which we interpret as the leftmost). For the root node collection there
is only one node, so only index 0 is used. We control our loop with the Inserted boolean
flag. It is initially false and is only changed to true once we have been able to insert our new item.
Each time around the loop we set Current to point to the node collection we are currently
examining and Parent to point to the node collection that contains the parent node.
We also set ParentIndex to 0 or 1 to indicate whether the parent node is the one at
index 0 or index 1 in that parent node collection. Only 0 and 1 are used as we can have at most
a right child (at index 0) and a left child (at index 1).
Notice how we use what amounts to Current = Parent->Item[ParentIndex]->Nodes
to pick out the collection of child nodes for the node at index ParentIndex .
(Did you notice that for a moment Parent and Current pointed to the same
node collection? That's why we can use either Parent and Current after the
= in that last assignment with no change in meaning.)
In a similar way we use Parent->Item[ParentIndex]->Text to get at the string
that is held in the parent node. We need to compare our new item to this string in order to
know whether to go left or right (in our current nodes collection) to find the place to insert this string.
We check to see if the Count is 0 for the current nodes collection. If so, it is an
empty collection and should be used for the string we are inserting. If
String::Compare(Item, ParentString) < 0 then we know that Item is less than
ParentString and we should go left. Otherwise we go right. In adding the
Item string on the left, we first add an empty string as the right child (just as a
placeholder). Then we add Item as the left child. The order of addition is, of course,
reversed when we insert Item as the right child.
If the Count for the current nodes collection was not 0, it must be 2. For all nodes
(except the root, which can have a count of 0 or 1), the counts must be 0 or 2, as we always add
the child nodes in pairs. In the case where the count is 2, we again use the same kind of string
comparison to tell whether to go left or right. In either case, we already have a node present, though
it might contain the empty string. If it is indeed the empty string, we just replace the empty string
with the string we are inserting. Notice how we use the get_Length function on a string
to tell if it is the empty string. Also note the use of 0 or 1 to pick out the correct child node
(right or left, respectively).
If we did not reach a node with an empty string, we cannot do the insertion this time around the loop.
Instead, we put 0 or 1 into ParentIndex to indicate whether this node was a right child
or left child and go around in the loop to try again, one level deeper into the tree, to do the insertion.
We are guaranteed to eventually reach the correct spot to insert our new string, since the tree
is not infinite.
Building and Testing the App
At this point save all of your files. Then build and run your application to
see that it works reasonably. The running app should look like the one shown in
our picture of the running app.
Note that the TreeView uses + and - signs in front of nodes. If there is a + sign
you can click on it to expand your view, thus allowing you to see what is under that node.
If there is a minus sign, you can click on it to collapse your view so that you do not see
what is under that particular node. Look at this picture
of the collapsed tree to see the view when everything is collapsed and only the root is visible.
Then see this picture of the two-level view where
the root and its two child nodes are visible, but all is collapsed at these two child nodes.
Finally, check out this picture of the three-level view, showing
everything collapsed at the "grandchildren" nodes of the root node. Note that the nodes labeled
allison and patrick have neither a + or - in front of them. That is because these are leaf nodes;
there are no child nodes under them.
Back to the main page for Software Design Using C++
|