Subject | Computer |

Due By (Pacific Time) | 12/02/2016 07:00 pm |

**1) Binary Search Tree **Please implement the binary search tree and finish the following operations

*(1) *Search

*(2) *Insert

*(3) *Delete

*(4) *inorderTraversal (print the tree)

Please use the following operation as your tester.

insert(50);

insert (40);

insert (80);

insert (20);

insert (45);

insert (60);

insert (90);

insert (55);

insert (65);

inorderTraversal();

search(20); // return Boolean to indicate whether it is found

delete(20);

inorderTraversal();

search(80);

delete(80);

inorderTraversal();

For the next problem I will need detail explanation of everything you do, I will have to present this particular problem in front of the class and professor.

2)

Imagine an array of n items from which you can choose. You will place the items you choose into a knapsack of size *k*. Each item has a size and a value. Of course, you cannot take more items than you have space for in the knapsack. Your goal is to maximize the total value of the items you take.

a. Design a recursive algorithm *maxKnapsack* to solve this knapsack problem. The parameters to the algorithm are the knapsack, the array of items, and the position within the array of the next item to consider. The algorithm chooses the items for the knapsack and returns a knapsack containing the chosen items. A knapsack can report its size, its contents, the value of its contents, and the size of its contents.

** Hint**: if any items in the array have not yet been considered retrieve the next item in the array. You can either ignore the item or, if it fits, put it in the knapsack. To decide, make a recursive call for each of these two cases. Compare the knapsacks returned by these calls to see which one has the most valuable contents. Then return that knapsack.

b. Write the classes **Knapsack** and **KnapsackItem**. Then write a program that defines the method maxKnapsack. The program should read the size of the knapsack and then the size, value and name of each available item. Here is some sample input data for a knapsack of size 10:

**Size Value Name**

1 50000 rare coin

2 7000 small gold coin

4 10000 packet of stamps

4 11000 pearl necklace

5 12000 silver bar

10 60000 painting

After displaying the items, call maxKnapsack. Then display the chosen items, their values and their total value.

For Both questions please answer the following

Test code:

Running results:

Comments:……

___This program can run successfully, with no errors and passed all test cases.

___ This program can compile and run, but it cannot pass all test cases.

___ This program cannot compile, and it has some syntax errors.

___ This program is incomplete

Other comments: _____________________________________________________

Tutor | Rating |
---|---|

pallavi |
out of 1971 reviews |

amosmm |
out of 766 reviews |

PhyzKyd |
out of 1164 reviews |

rajdeep77 |
out of 721 reviews |

sctys |
out of 1600 reviews |

sharadgreen |
out of 770 reviews |

topnotcher |
out of 766 reviews |

XXXIAO |
out of 680 reviews |