In this lab, we see how to carry out the common binary search tree operations of finding a node with a given key, inserting a new node, traversing the tree, and deleting a node.
At the end of this lab, you need to submit a word document including some text answers and screenshots of your lab result. The way to get the screen shots is to press Key "Print Screen" from your keyboard to get the image of the whole screen, then use Start->All Programs->Accessories->Paint, click Edit->Paint to get the image, use text to add your own name (to replace Qi Zhu), then cut and paste the part of image you want into your homework file such as .doc).
1. Download the Workshop Applets
Go to the Blackboard or Textbook's website http://www.samspublishing.com/title/0672324539# to download the file WorkshopApplets.zip into directory C:\COSC3333\. Then extract the zip file.
2. Operations on Tree.html
To execute an applet, perform the following steps.
(1.) Click Start > Windows System -> Command Prompt
(2.) Use command "cd" to move into the directory where you run the applet, such as cd C:\COSC3333\Chap08\Tree.
(3.) Use the command "appletviewer Tree.html" to run the application, you will have Figure 1.
Fig. 1 Initial State for Binary Tree: see image.
(4.) Fill 5 in the blank of Enter number, and click Fill to randomly initialize a 5 elements binary search tree, we have Figure 2 (your tree may be different since the numbers are randomly selected, maximally it could have 32 nodes in 5 levels). Q1: How many levels your binary search tree has (including level 0)? Q2: Is the binary search tree you created height balanced?
Fig. 2 A Random 5-element Binary Tree see image.
(5.) Fill 31 in the blank of Enter number, and click Ins to insert this element, we have Figure 3 after it is inserted. Q3: What is the insertion process of the binary search tree?
Fig. 3 Insert an Element "31" see image.
(6.) Insert some more elements, 45, 79, 61, and insert an element that is already in the tree, such as 52 in my case, finally you have Figure 4. Q4: The new identical element is inserted as left or right child of the existing same value?
Fig. 4 Insert some more Elements see image.
(7.) Fill 31 in the blank of Enter number, and click Find to search this element, we have Figure 5 after it is found. Try again using some element is not in the tree, such as 35 in my case. Q5: What is the find process of the binary tree? If we have the multiple appearance of an element, such as 52, can both be found?
Fig. 5 Find Element "31" see image.
(8.) Click Trav to observe the traverse process. Q6: What is traverse process and what is the visiting result? What order it is, prefix (Middle->Left->Right), postfix (Left->Right->Middle), or infix (Left->Middle->Right)?
(9.) Click Del to delete 31. Q7: What is delete process? What happened with the node under this deleted node?
Fig. 6 Delete Element "31" see image.
(10.) Click Del to delete the root element, in my case, it is 58. Q8: Which element has been selected as the new root? How to find it?
Fig. 7 Delete the Root Element "58" see image.