CIS Logo SVC Logo

   Computing & Information Systems
   Department

 

Schoology Facebook        Search CIS Site      Tutorials

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++

Author: Br. David Carlson with contributions by Br. Isidore Minerd
Last updated: August 27, 2009
Disclaimer