Programming Assignment 6 Binary Search Tree Solution

Modify the BST program that is discussed in the class by addingthefollowing functions:




Write a function that builds a binary search tree by inserting the following nodes intothetree. ( 70 50 100 30 60 80 11020
68 90 1202562 ). The function must display the binarysearchtree.




Write a function that traverse and displays the tree inpre-orderform.



Write a function that traverse and displays the tree in post- orderform.



Write a function that displaysallthe right sub roots ofthat tree.



Write a function that displaysallthe left sub roots ofthat tree.



Write a function that counts and displays the number of leafsin thetree.



Write a function that displaysonlythe leafs of thetree.






Note :




You havetouse only arrayswhen implementing thisprogram
(items 1-7whereapplicable ).Cannotusevectorarrays, orlinkedlists.




Cannotuse library functions suchas swap, sort , vector … etc. for thisprogrammingassignment.



In thesampleoutput ,ReplaceMyname(HusainGholoom) with your firstandlastname.
Style Guidelines:




At the beginning of your program ( andbeforethe #include statement ), include the following:




Header comments(file documentation block) should be at the top of each file and shouldcontain: Author / s, Due Date, Assignment Number, Course number and section, Instructor, and a brief description of the purpose of the code in the file. For example:

// Roster Number /s: xxxxxxxxx

//

// Author / s : (Your namehere!!)

// Due Date:

// Programming Assignment Number6

//

// Spring 2018 - CS3358 - Your SectionNumber

//

// Instructor: HusainGholoom.

//

// <Brief description of the purpose of theprogram







Variable names :



Must bemeaningful.
The initial letter should be lowercase, following words should be capitalized,noother caps or punctuation( i.e. weightInPounds ).
Each variable must be declared on a separate line with a descriptivecomment.



Named constants :




Use for most numericliterals.
All capitals with underscores( i.e. TX_STATE_SALES_TAX )
Should occur at top of function, or global (only ifnecessary)
Line lengthof source code should be no longer than 80 characters (no wrapping of lines).




Indentation :




Use 2-4 spaces (but be consistent throughout yourprogram).
Indent blocks, within blocks,etc.
Use blank lines to separatesections.



Comments for variables :

All variable definitions should be commented as follows: intgender; // integer value for the gender,

// 1 = Male , 2 = Female ,

Note : In order to get a full mark:







Your programmust compileand run. We will test your program using latest version of codeblocks that is availed in Texas State University’s Labs. Your program should run for any number ofnode.
Yourprogrammustbedocumentedaccordingthestyleabove.Seethewebsiteforthesample programming styleprogram.
Must properly format the output as shownbelow.
Mustusefunctions ( prototypes and definitions).
You must name your program as:



oLastName_FirstName_PG6_BSTs.cpp




Where LastName is your Last Name and FirstName is your First Name. For example , the file name should look somethinglike: Gholoom_Husain_PG6_BSTs.cpp (not .cbp)



Everyone must upload the electronic version of the program no later than the starting of class time on the due date.DO NOTsend your assignment solution via email.No late assignments will be accepted and a grade of zero will be assigned .Group members must upload identical copy of theassignment.



USE TRACS To upload your program .



You mustalsoturn in hard copy of your source code no later than the starting of class time on the due date . Should the hard copy consist of more than one page , then , the hard copy must bestapled. If you are unable to turn in a printout during class, you can take the program to the computer science department and hand it to the front desk personal (Comal 211 ) before the deadline. Make sure that the front office stamps the program. Make sure that include the date and time. Finally ,make sure that they place the program in my mailbox.Only one copy per group.



No late submission hard copy of the assignment will be accepted and a grade of zero will be assigned .



DO NOTslide your program under my office door – It willNOTbe acceptedand a grade of zero will be assigned .




The following points will bedeductedif:




Compilation errors , Incorrect file format such asuploading.cbp instead of .cpp , missing electronic copy , missing the hardcopy , different copies of the assignment per group , using vector array or linked lists , using function libraries such as swap / sort , more than one file such as using .h , .cppfile
( - 10 points )




Each logical error :( - 1.5 points)






Other :( 1.75points ) ifanyof the following takes a place:



Unable to read the source code due to unclear printing or printing in a landscapeformat.
Incorrect Outputformat.
Incorrect program filename.
Hard copy is notstapled.
Incorrect Stylesuch as but not limited toMissing Header , footer , comments or program documentations , missing roster number , missing section number …etc






Usethefollowing sample .cpp file to test yourprogram




BinarySearchTree tree;




cout << "Binary Search Tree By Husain Gholoom\n\n";cout << "Inserting nodes.\n\n"; tree.insertNode(70);

tree.insertNode(50); tree.insertNode(100); tree.insertNode(30); tree.insertNode(60); tree.insertNode(80); tree.insertNode(110); tree.insertNode(20); tree.insertNode(68); tree.insertNode(90); tree.insertNode(120); tree.insertNode(25); tree.insertNode(62);




cout<<"Building BST iscompleted.\n\n";




cout << "Values of the Binary Search tree.\n\n";










// Pre-Order Traversal .

cout << "Pre-Order Traversal of the BST :\n\n"; tree.preOrder();







// Post-Order Traversal .

cout << "Post-Order Traversal of the BST :\n\n"; tree.postOrder();







// All right sub root values.

cout << "Here are all right sub root values for the BST :\n\n"; tree.displayRSR();




// All left sub root values.

cout << "\n\nHere are all left sub root values for the BST :\n\n"; tree.displayLSR();













// Counting Number of Leafs .

cout << "\n\nNumberofLeafs = " << tree.treeLeafsCount();




// Display the leaf values.

cout << "\n\nHere are the leaf values in the BST:\n\n"; tree.displayLeafValues();




cout << "\n\n\nApril 25 , 2018\n\nWritten by Husain Gholoom \n\n";







Sample Output Run









Binary Search Tree By Husain Gholoom Inserting nodes.
Building BST iscompleted.







Values of the BinarySearchTree :




1: 70

2: 50

3: 100

4: 30

5: 60

6: 80

7: 110

8: 20

9: empty

10: empty

11: 68

12: empty

13: 90

14: empty

15: 120

16: empty

17: 25

18: empty

19: empty

20: empty

21: empty

22: 62

23: empty

24: empty

25: empty

26: empty

27: empty

28: empty

29: empty

30: empty

31: empty




Pre-Order Traversal :



70

50

30

20

25

60

68

62

100

80

90

110

120




Post-Order Traversal :



25

20

30

62

68

60

50

90

80

120

110

100

70




Here are all right sub root values fortheBST :



100

110

120

Here are all left sub root values fortheBST :



50

30

20

NumberofLeafs : 4






Here are the leaf values in the BST :




25

62

90

120







April 25 ,2018



Written by Husain Gholoom