Replace the tables and linked lists with binary search trees. How do you convert

ID: 3843949 • Letter: R

Question

Replace the tables and linked lists with binary search trees.

How do you convert linked lists into binary search trees?

Could you also post the output result.

Player.h

#pragma once

#include <string>
using namespace std;

class Player
{
public:
   //constructors
   Player();
   Player(const string& new_name);

   //accessors
   string name() const;
   int wins() const;
   int sum() const;

//mutators
void name(const string& new_name);

//custom methods
   void recordWin();
   void addFace(int face);
private:
   string _name;
   int _wins;
   int _sum;
};

Player.cpp

#include <cassert>
#include "Player.h"

//constructors
Player::Player()
{
_name = "Nemo";
_wins = 0;
_sum = 0;
}

Player::Player(const string& new_name)
{
   _name = "Nemo";
   name(new_name);
   _wins = 0;
   _sum = 0;
}

//accessors
string Player::name() const
{
   return _name;
}
int Player::wins() const
{
   return _wins;
}
int Player::sum() const
{
   return _sum;
}

//mutators
void Player::name(const string& new_name)
{
   //trim leading and trailing spaces
   unsigned left = 0;
   while (left < new_name.length() && isspace(new_name[left]))
       left++;
   unsigned right = new_name.length();
   while (right > 0 && isspace(new_name[right - 1]))
       right--;
   //change _name only if new_name is a good name
   if (left <= right)
       _name = new_name.substr(left, right - left + 1);
}

// custom methods
void Player::recordWin()
{
   _wins++;
}
void Player::addFace(int face)
{
   assert(1 <= face && face <= 6);
   _sum += face;
}

Source.cpp

#include <cassert>
#include <ctime>
#include <iostream>
#include <iterator>
#include <list>
#include <random>
#include <string>
#include <vector>
#include "Player.h"

using namespace std;

struct GameToken
{
string name;
unsigned value;
};

list<Player>::iterator find(list<Player>& players, const string& player_name)
{
   list<Player>::iterator pit = players.begin();
   while (pit != players.end() && (*pit).name() != player_name)
       ++pit;
   return pit;
}
int compSimpleWinner(const list<GameToken>& values, list<GameToken>& winners)
{
   list<GameToken>::const_iterator wit = values.begin();
   winners.clear();
   winners.push_back(*wit);
   for(list<GameToken>::const_iterator vit = ++wit; vit != values.end(); ++vit)
       if ((*vit).value > winners.front().value)
       {
           winners.clear();
           winners.push_back(*vit);
       }
       else if ((*vit).value == winners.front().value)
           winners.push_back(*vit);
   if (winners.size() == values.size())
   {
       winners.clear();
       return 0;
   }
   else
       return winners.size();
}
unsigned compTossWinner(const list<GameToken>& faces, list<GameToken>& winners)
{
   return compSimpleWinner(faces, winners);
}
int compGameWinner(const list<GameToken>& winCounts, const list<GameToken>& sums, list<GameToken>& winners)
{
   int nwinners = compSimpleWinner(winCounts, winners);
   if (nwinners == 0) nwinners = compSimpleWinner(sums, winners);
   return nwinners;
}
int main()
{
   cout << "Please enter the number of players: ";
   unsigned nPlayers;
   cin >> nPlayers;
   assert(cin.good() && nPlayers > 1);

   /*list<Player> players(nPlayers);
   unsigned playerId = 0;
   for (list<Player>::iterator pit = players.begin(); pit != players.end(); ++pit)
   {
       (*pit).name("p" + to_string(playerId));
       playerId++;
   }*/

   list<Player> players;
   for (unsigned playerId = 1; playerId <= nPlayers; playerId++)
       players.push_back(Player("p" + to_string(playerId)));

default_random_engine e(static_cast<unsigned>(time(nullptr)));
uniform_int_distribution<int> u(1, 6);

   cout << "Please enter the number of tosses: ";
   unsigned ntosses;
   cin >> ntosses;
   assert(cin.good() && ntosses > 0);

   for(unsigned toss = 1; toss <= ntosses; toss++)
   {
       list<GameToken> faces;
       list<GameToken> toss_winners;
       for (list<Player>::iterator pit = players.begin(); pit != players.end(); ++pit)
       {
           GameToken game_token;
           game_token.name = (*pit).name();
           game_token.value = u(e);
           faces.push_back(game_token);
           cout << game_token.name << " tosses " << game_token.value << endl;
           (*pit).addFace(game_token.value);
       }
       //who wins the this toss?
       if (compTossWinner(faces, toss_winners) > 0)
       {
           for (list<GameToken>::iterator wit = toss_winners.begin(); wit != toss_winners.end(); ++wit)
           {
               list<Player>::iterator where = find(players, (*wit).name);
               assert(where != players.end());
               (*where).recordWin();
               cout << (*where).name() << " wins toss " << toss << endl;
           }
       }
       else
           cout << "Toss " << toss << " is tied" << endl;
       cout << endl;
   }

   list<GameToken> wins;
   list<GameToken> sums;
   for (list<Player>::iterator pit = players.begin(); pit != players.end(); ++pit)
   {
       GameToken game_token;
       game_token.name = (*pit).name();
       game_token.value = (*pit).wins();
       wins.push_back(game_token);
       game_token.value = (*pit).sum();
       sums.push_back(game_token);
   }
   //who wins the game?
   list<GameToken> game_winners;
   if (compGameWinner(wins, sums, game_winners) > 0)
   {
       for (list<GameToken>::iterator wit = game_winners.begin(); wit != game_winners.end(); ++wit)
           cout << (*wit).name << " wins the game" << endl;
   }
   else
       cout << "The game is tied" << endl;

   wins.clear();
   sums.clear();
   game_winners.clear();

system("pause");
return 0;
}

Explanation / Answer