Question
Please need help with this; In call of duty, the only goal to accomplish is to maximize your enemies taken out and thus have the
Please need help with this; In call of duty, the only goal to accomplish is to maximize your enemies taken out and thus have the highest K/D in the lobby. So now you are playing Call of Duty: World at War (The best call of duty game ever) and you have reached a place with a large staircase in front of you. And there is an enemy at each landing of the staircase (on the left side and the right side of each step of the staircase). The staircase is analogous to a binary tree with each of its nodes as a landing of the staircase and each of its edges as stairs from one landing to another. Given the following binary search tree
You start with person 8 and you take that person out, and then you move left or right. You want to take out the maximum possible number of enemies. You can take out every person you can see from your position with your suppressed sniper gun. But you can see only the persons at the leftmost standing at each level and cannot see the rest.
Before starting shooting them, you want to know how many persons you can take out. You are busy keeping an eye on the enemies. So you want this program to find out the maximum number of people you can take out from that location by providing with the analogous a binary search tree.
[ Note: Players do not change their position after one player has been taken out, i.e. the leftmost node remains the same even after player on that node has been taken out. Or we can say that the nodes are not removed after the player on that node has been taken out. ]
In other words, you need to find the maximum number of left children on a path of the binary search tree. The input for your program will be an integer (> 0) that denotes the amount of test cases then the numbers to be inserted into a binary search three. The output will be a number that denotes the maximum number of enemies that can be taken out. You will also need to implement a binary search tree type.
template
class bst
{
struct binTreeNode
{
binTreeNode * left ;
binTreeNode * right ;
Type item ;
};
public :
class binTreeIterator
{
public : friend class bst;
binTreeIterator ();
binTreeIterator ( binTreeNode *);
bool operator ==( binTreeNode *);
bool operator ==( binTreeIterator );
binTreeIterator rightSide ();
binTreeIterator leftSide ();
private :
binTreeNode * current ;
};
bst ();
bst ( const bst < Type >&);
const bst& operator =( const bst < Type >&);
~bst ();
void insert ( const Type &);
binTreeIterator begin ();
binTreeIterator end ();
private :
binTreeNode * insert ( binTreeNode * , const Type &);
void destroyTree ( binTreeNode *);
void cloneTree ( binTreeNode * , binTreeNode *);
binTreeNode * root ;
};
Each member contains and performs the following
struct binTreeNode - is the binary tree node, each node contains some item and a pointer to the left and right child
class binTreeIterator - is basically going to be a pointer to traverse the binary search tree, but we will use this iterator to hide pointer info in main and still allow us to navigate the binary search tree, each member of binTreeIterator will be as follows
binTreeNode * current - stores the pointer of a node that the iterator points to
binTreeIterator() - is the default constructor that sets current to NULL
binTreeIterator(binTreeNode*) - is a constructor that sets current with the pointer passed into the constructor
bool operator==(binTreeNode*) - returns true if current equals the pointer on the right hand side of the operator and false otherwise
bool operator==(binTreeIterator) - returns true if current equals the right hand side iterator objects current and false otherwise
binTreeIterator rightSide() - returns an iterator object that is on the right side of the iterator that calls the function
binTreeIterator leftSide() - returns an iterator object that is on the left side of the iterator that calls the function
binTreeNode * root - is a pointer that points to the root of the binary search tree
bst() - is the default constructor that sets root to NULL
bst(const bst&) - is the copy constructor, it will call cloneTree by passing in root and copy.root (copy is the object passed into the constructor)
const bst& operator=(const bst&) - is the default assignment operator, it will check for self assignment and call destroyTree and cloneTree if the objects arent the same and then returns *this
~bst() - is the destructor that deallocates the binary search tree, it will just call destroyTree
void insert(const Type&) insert an item into the binary search tree, this function will call the private insert function if we do not have an empty binary search tree (and that function will recursively insert the element), the public insert is simply a wrapper
binTreeIterator begin() - returns an iterator that contains the root pointer, return binTreeIterator(root)
binTreeIterator end() - returns an iterator that contains a NULL pointer, return binTreeIterator(NULL)
binTreeNode* insert(binTreeNode*, const Type&) - this private function will insert an element into the binary search tree, this function is recursive
void destroyTree(binTreeNode*) - deallocates the binary search tree, this will be a postorder method of deallocating the tree
void cloneTree(binTreeNode*, binTreeNode*) - this creates a deep copy of the tree, this will copy the children of the second parameter into the the children of the first parameter and recursively continue this step for the left and right have of the binary search tree (this is more complicated version of preorder)
Contents of main
In main, you will
1. Read the number of test cases
2. Read nodes and insert each into the binary search tree one by one until you read -1
3. Output the max number of enemies that can be taken out
4. Repeat step 2 if more test cases exist
In order to output the max enemies, you will need a recursive function in main that will traverse the bst object using binTreeIterator, the function prototype is
int findMaxEnemyTakeOuts (bst binTreeIterator )
The way this function is written is that it returns all the max number of enemies not including the root, so in main, we have cout << findMaxEnemyTakeOuts(binSearchTree->begin()) + 1 << endl; and binSearchTree is a pointer that points to a bst object.
This function sort of follows postorder traversal of a binary tree. Thus you compute the max enemies on the left side, the compute the max enemies on the right side, and the max number of the two gets returned up the binary tree. Remember an enemy on the left side counts as 1 enemy take out and an enemy on the right does not count as an enemy take out (all though there could be a sub tree for the right side, but the immediate right node is not a take out).
Sample Input:
home / study / engineering / computer science / computer science questions and answers / please need help with this; in call of duty, the only goal to accomplish is to maximize your ...
Question: Please need help with this; In call of duty, the only goal to accomplish is to maximize your enem...
Please need help with this; In call of duty, the only goal to accomplish is to maximize your enemies taken out and thus have the highest K/D in the lobby. So now you are playing Call of Duty: World at War (The best call of duty game ever) and you have reached a place with a large staircase in front of you. And there is an enemy at each landing of the staircase (on the left side and the right side of each step of the staircase). The staircase is analogous to a binary tree with each of its nodes as a landing of the staircase and each of its edges as stairs from one landing to another. Given the following binary search tree
You start with person 8 and you take that person out, and then you move left or right. You want to take out the maximum possible number of enemies. You can take out every person you can see from your position with your suppressed sniper gun. But you can see only the persons at the leftmost standing at each level and cannot see the rest.
Before starting shooting them, you want to know how many persons you can take out. You are busy keeping an eye on the enemies. So you want this program to find out the maximum number of people you can take out from that location by providing with the analogous a binary search tree.
[ Note: Players do not change their position after one player has been taken out, i.e. the leftmost node remains the same even after player on that node has been taken out. Or we can say that the nodes are not removed after the player on that node has been taken out. ]
In other words, you need to find the maximum number of left children on a path of the binary search tree. The input for your program will be an integer (> 0) that denotes the amount of test cases then the numbers to be inserted into a binary search three. The output will be a number that denotes the maximum number of enemies that can be taken out. You will also need to implement a binary search tree type.
template
class bst
{
struct binTreeNode
{
binTreeNode * left ;
binTreeNode * right ;
Type item ;
};
public :
class binTreeIterator
{
public : friend class bst;
binTreeIterator ();
binTreeIterator ( binTreeNode *);
bool operator ==( binTreeNode *);
bool operator ==( binTreeIterator );
binTreeIterator rightSide ();
binTreeIterator leftSide ();
private :
binTreeNode * current ;
};
bst ();
bst ( const bst < Type >&);
const bst& operator =( const bst < Type >&);
~bst ();
void insert ( const Type &);
binTreeIterator begin ();
binTreeIterator end ();
private :
binTreeNode * insert ( binTreeNode * , const Type &);
void destroyTree ( binTreeNode *);
void cloneTree ( binTreeNode * , binTreeNode *);
binTreeNode * root ;
};
Each member contains and performs the following
struct binTreeNode - is the binary tree node, each node contains some item and a pointer to the left and right child
class binTreeIterator - is basically going to be a pointer to traverse the binary search tree, but we will use this iterator to hide pointer info in main and still allow us to navigate the binary search tree, each member of binTreeIterator will be as follows
binTreeNode * current - stores the pointer of a node that the iterator points to
binTreeIterator() - is the default constructor that sets current to NULL
binTreeIterator(binTreeNode*) - is a constructor that sets current with the pointer passed into the constructor
bool operator==(binTreeNode*) - returns true if current equals the pointer on the right hand side of the operator and false otherwise
bool operator==(binTreeIterator) - returns true if current equals the right hand side iterator objects current and false otherwise
binTreeIterator rightSide() - returns an iterator object that is on the right side of the iterator that calls the function
binTreeIterator leftSide() - returns an iterator object that is on the left side of the iterator that calls the function
binTreeNode * root - is a pointer that points to the root of the binary search tree
bst() - is the default constructor that sets root to NULL
bst(const bst&) - is the copy constructor, it will call cloneTree by passing in root and copy.root (copy is the object passed into the constructor)
const bst& operator=(const bst&) - is the default assignment operator, it will check for self assignment and call destroyTree and cloneTree if the objects arent the same and then returns *this
~bst() - is the destructor that deallocates the binary search tree, it will just call destroyTree
void insert(const Type&) insert an item into the binary search tree, this function will call the private insert function if we do not have an empty binary search tree (and that function will recursively insert the element), the public insert is simply a wrapper
binTreeIterator begin() - returns an iterator that contains the root pointer, return binTreeIterator(root)
binTreeIterator end() - returns an iterator that contains a NULL pointer, return binTreeIterator(NULL)
binTreeNode* insert(binTreeNode*, const Type&) - this private function will insert an element into the binary search tree, this function is recursive
void destroyTree(binTreeNode*) - deallocates the binary search tree, this will be a postorder method of deallocating the tree
void cloneTree(binTreeNode*, binTreeNode*) - this creates a deep copy of the tree, this will copy the children of the second parameter into the the children of the first parameter and recursively continue this step for the left and right have of the binary search tree (this is more complicated version of preorder)
Contents of main
In main, you will
1. Read the number of test cases
2. Read nodes and insert each into the binary search tree one by one until you read -1
3. Output the max number of enemies that can be taken out
4. Repeat step 2 if more test cases exist
In order to output the max enemies, you will need a recursive function in main that will traverse the bst object using binTreeIterator, the function prototype is
int findMaxEnemyTakeOuts (bst binTreeIterator )
The way this function is written is that it returns all the max number of enemies not including the root, so in main, we have cout << findMaxEnemyTakeOuts(binSearchTree->begin()) + 1 << endl; and binSearchTree is a pointer that points to a bst object.
This function sort of follows postorder traversal of a binary tree. Thus you compute the max enemies on the left side, the compute the max enemies on the right side, and the max number of the two gets returned up the binary tree. Remember an enemy on the left side counts as 1 enemy take out and an enemy on the right does not count as an enemy take out (all though there could be a sub tree for the right side, but the immediate right node is not a take out).
Sample Input:
5
8 10 3 14 13 6 4 7 1 -1
10 -1
3 4 -1
3 2 5 -1
10 11 2 7 6 5 4 3 12 -1
Sample Output
Case 1 : 3
Case 2 : 1
Case 3 : 1
Case 4 : 2
Case 5 : 6
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started