Write a C++ function to compute the balance factor of a tree and more.......

CIS22C – LAB 3 Revision. Due date changed to 8/7 1:00 pm. Additional instructions also

added. Sorry for the late notification. Note: If you have already completed Lab3 you will

still benefit from the rubric change listed below.

Revised Scoring Rubric: You may select which parts of the lab you wish to do in any order. The first 3

parts you choose will be worth 6 points each. After doing 3 parts, additional parts are worth 2 points each.

This means you can earn from 6 points to 24 points depending on which parts you choose to answer.

PART A:

Write a C++ function to compute the balance factor of a tree. If it is called initially with a root pointer, it should

determine the balance factor of the entire tree. If it is called with a pointer to a subtree it should determine if

the tree is balanced or not. In balanced trees, the height difference of the left verses the right subtrees must

not differ by more than 1

Upload your function to Catalyst to a file named determineBalance.cpp

Test with unbalanced preorder tree

23 A / \ / \ 18 25 B C / \ / \ 17 20 D E / / 12 F Test with balanced preorder tree 23,18,30,17,20: 23 A / \ / \ 18 30 B C / \ / \ 17 20 D E PART B:

Write a C++ program that will add a node with value 29 to the balanced tree in PART A. Implement your code

using the algorithm below. Your result should indicate that a new pointer is created from node C pointing to a

location that contains the value 29.

Test your function using the balanced tree in PART A. inserting a new node with value of 29 into the tree. Upload your

function to addBstNode.cpp . Upload a screen snapshot of your program execution using one of the following formats:

execution.jpg, execution.docx or execution.rtf

PART C:

Write a C++ program that reads a list of names and telephone numbers from a text file and inserts them into a

BST. Once the tree has been built, present the user with a menu that allows them to search the list for a

specified name, insert a new name, delete and existing name or print the entire phone list. At the end of the

job, write the data in the list back to the file. Test your program with the comma delimited file phoneList.txt

(download from Catalyst).

Upload your program and screen captures to Catalyst to a files named phoneList.cpp and

phoneListScreenout.txt

Part D:

Write an algorithm to combine two heaps and produce a third one. Heap A should be on the bottom and Heap

B on top.

Upload your algorithm to Catalyst to a file named heapCombineAlgorithm.txt

Part E:

The following instruction is replaced:

Old Instruction: Write a function that will create an adjacency matrix for the graph below

New Instruction: Manually fill out the adjacency matrix for the graph below. Us a “1” to indicate if there is an

edge from vertex to vertex and “0” if there is not.

Output your results in an adjacency matrix:

Upload your function to Catalyst as a file named adjacencyMatrix.txt

Part F:

A graph can be used to show relationships. For example, from the following list of people belonging to the same club (vertices) and their friendships (edges), write and test a program that will find: A. All friends of Jerry B. All friends of Quan C. All friends of Julie D. All friends of James People = (George, James, Julie, Frank, Fred, Jerry, Quan) Friendship = {(George, Julie), (Frank, Fred), (George, Jerry), (James, Fred) (James, Frank), (James, Quan), (Quan, Frank)} Upload your program and output screen capture to Catalyst using the filenames myFriends.cpp and myFriendsOutput.jpg (or word document)

A B C D E F G H

A 0 B

0

C

0 D

0

E

0 F

0

G

0 H

0