Блог

Я хочу обобщить этот процесс создания двоичного дерева, чтобы позволить различным типам узлов быть включенными в само дерево. Например, я хочу, чтобы пользователь мог выбрать, хочет ли он построить дерево со структурой города (как я сделал ниже) или со структурой людей или любой структурой, которую он хочет определить в исходном коде.

Есть ли простой способ реализовать эти изменения?

Это и есть код:

 #include lt;iostreamgt;  template lt;typename Tgt; struct node {  T infoStruct;  // Pointers  node* left = NULL;  node* right = NULL; }; struct city {  std::string cityName;  int population; };  struct people {  std::string name;  std::string surname;  int age;  int weight; };  nodelt;citygt;* root;  void visualizeInOrder(nodelt;citygt;*); void insertNewNode(nodelt;citygt;*, nodelt;citygt;*);  int main() {  root = NULL;  char choice;   do  {  nodelt;citygt;* tmp = new nodelt;citygt;;  std::cout lt;lt; "Insert city name: ";  getline(std::cin, tmp-gt;infoStruct.cityName);  std::cout lt;lt; "Insert population: ";  std::cin gt;gt; tmp-gt;infoStruct.population;   if (root)  insertNewNode(root, tmp);  else  root = tmp;   choice = 'N';  std::cout lt;lt; "Insert another city? [y|N]gt; ";  std::cin gt;gt; choice;  std::cin.ignore();  } while (choice != 'N');   visualizeInOrder(root); }     void visualizeInOrder(nodelt;citygt;* root) {  if (root-gt;left) visualizeInOrder(root-gt;left);  std::cout lt;lt; root-gt;infoStruct.cityName lt;lt; " has " lt;lt; root-gt;infoStruct.population lt;lt; " populationn";  if (root-gt;right) visualizeInOrder(root-gt;right); }    void insertNewNode(nodelt;citygt;* root, nodelt;citygt;* leaf) {  if (root)  {  if (leaf-gt;infoStruct.population lt; root-gt;infoStruct.population)  if (root-gt;left)  insertNewNode(root-gt;left, leaf);  else  root-gt;left = leaf;  else  if (root-gt;right)  insertNewNode(root-gt;right, leaf);  else  root-gt;right = leaf;  } }  

Большинство фрагментов уже там. Первый шаг, который вы можете сделать, — это просто изменить подпись insertNewNode и visualizeInOrder принять nodelt;Tgt; вместо nodelt;citygt; .

Так insertNewNode бы стало:

 templatelt;typename Tgt; void insertNewNode(nodelt;Tgt;* root, nodelt;Tgt;* leaf) {  if (root)  {  if (leaf-gt;infoStruct.population lt; root-gt;infoStruct.population)  if (root-gt;left)  insertNewNode(root-gt;left, leaf);  else  root-gt;left = leaf;  else  if (root-gt;right)  insertNewNode(root-gt;right, leaf);  else  root-gt;right = leaf;  } }  

Однако проблема здесь в том, что универсальный тип T не будет иметь члена population . Поэтому вместо использования:

 leaf-gt;infoStruct.population lt; root-gt;infoStruct.population  

Вы можете добавить шаблонную функцию сравнения Comp comp в подпись, затем использовать ее для сравнения и передать ее также вызову рекурсии:

 templatelt;typename T, typename Compgt; void insertNewNode(nodelt;Tgt;* root, nodelt;Tgt;* leaf, Comp comp) {  if (root)  {  if (comp(leaf.infoStruct, root.infoStruct)  if (root-gt;left)  insertNewNode(root-gt;left, leaf, comp);  else  root-gt;left = leaf;  else  if (root-gt;right)  insertNewNode(root-gt;right, leaf, comp);  else  root-gt;right = leaf;  } }  

Однако это не самый эффективный способ добавления функции сравнения, так как вам всегда придется добавлять какую-либо функцию, например лямбду, к первому вызову insertNewNode в вашей основной программе вручную. Таким образом, в настоящее время вы будете вызывать функцию в основном, как:

 insertNewNode(root, tmp, [](const cityamp; city_a, const cityamp; city_b){  return city_a.population lt; city_b.population; });  

Это довольно многословно и прямо не работало бы, если population бы было частным участником. Вместо этого вы можете использовать std::less по умолчанию, поэтому объявление будет:

 templatelt;typename T, typename Comp = std::lesslt;gt;gt; void insertNewNode(nodelt;Tgt;* root, nodelt;Tgt;* leaf, Comp comp = {});  

Теперь вы можете либо добавить функцию сравнения вручную, как это было у меня ранее, либо вы можете добавить a operatorlt; в свой city класс, и он будет автоматически использоваться в insertNewNode функции:

 struct city {  ⋮  bool operatorlt; (const cityamp; other) const  {  return population lt; other.population;  } };  

Аналогично, для visualizeInOrder , поскольку cityName и population являются уникальными для city , вы не можете использовать:

 std::cout lt;lt; root-gt;infoStruct.cityName lt;lt; " has " lt;lt; root-gt;infoStruct.population lt;lt; " populationn";  

Вместо этого вы можете перегрузить ostreamamp; operatorlt;lt; для своего city класса, чтобы распечатать всю подробную информацию. И внутри visualizeInOrder это просто стало бы:

 std::cout lt;lt; root-gt;infoStruct lt;lt; 'n';