Generalization of tree creation-CodePudding

I want to generalize this binary tree creation process in order to let different types of nodes to be included in the tree itself. For example, I want to let the user choose if he wants to build a tree with the structure city (as I did below) or with the structure people or any structure he wants to define in the source code.

Is there a simple way to implement those changes?

This is the code:

#include <iostream>

template <typename T>
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;
};

node<city>* root;

void visualizeInOrder(node<city>*);
void insertNewNode(node<city>*, node<city>*);

int main()
{
    root = NULL;
    char choice;

    do
    {
        node<city>* tmp = new node<city>;
        std::cout << "Insert city name: ";
        getline(std::cin, tmp->infoStruct.cityName);
        std::cout << "Insert population: ";
        std::cin >> tmp->infoStruct.population;

        if (root)
            insertNewNode(root, tmp);
        else
            root = tmp;

        choice = 'N';
        std::cout << "Insert another city? [y|N]> ";
        std::cin >> choice;
        std::cin.ignore();
    } while (choice != 'N');

    visualizeInOrder(root);
}




void visualizeInOrder(node<city>* root)
{
    if (root->left) visualizeInOrder(root->left);
    std::cout << root->infoStruct.cityName << " has " << root->infoStruct.population << " population\n";
    if (root->right) visualizeInOrder(root->right);
}



void insertNewNode(node<city>* root, node<city>* leaf)
{
    if (root)
    {
        if (leaf->infoStruct.population < root->infoStruct.population)
            if (root->left)
                insertNewNode(root->left, leaf);
            else
                root->left = leaf;
        else
            if (root->right)
                insertNewNode(root->right, leaf);
            else
                root->right = leaf;
    }
}

CodePudding user response：

Most of the pieces are already there. The first step you can do is to simply change the signature of insertNewNode and visualizeInOrder to accept node<T> instead of node<city>.

So insertNewNode would become:

template<typename T>
void insertNewNode(node<T>* root, node<T>* leaf)
{
    if (root)
    {
        if (leaf->infoStruct.population < root->infoStruct.population)
            if (root->left)
                insertNewNode(root->left, leaf);
            else
                root->left = leaf;
        else
            if (root->right)
                insertNewNode(root->right, leaf);
            else
                root->right = leaf;
    }
}

However, the problem here is that a generic type T would not have a member population. So instead of using:

leaf->infoStruct.population < root->infoStruct.population

You could add a templated comparison function Comp comp to the signature, then use that to do the comparison, and pass it to the recursion call as well:

template<typename T, typename Comp>
void insertNewNode(node<T>* root, node<T>* leaf, Comp comp)
{
    if (root)
    {
        if (comp(leaf.infoStruct, root.infoStruct)
            if (root->left)
                insertNewNode(root->left, leaf, comp);
            else
                root->left = leaf;
        else
            if (root->right)
                insertNewNode(root->right, leaf, comp);
            else
                root->right = leaf;
    }
}

However, this is not the most effective way of adding a comparison function, since you would always have to add some function, such as a lambda, to the first call of insertNewNode in your main manually. So currently, you would be calling the function in the main like:

insertNewNode(root, tmp, [](const city& city_a, const city& city_b){
    return city_a.population < city_b.population;
});

This is quite verbose, and would straight up not working if population was a private member. Instead, you could use std::less as default, so the declaration would be:

template<typename T, typename Comp = std::less<>>
void insertNewNode(node<T>* root, node<T>* leaf, Comp comp = {});

Now you can either add a comparison function manually like what I had earlier, or you can add a operator< to your city class, and it would be automatically used in the insertNewNode function:

struct city
{
     ⋮
    bool operator< (const city& other) const
    {
        return population < other.population;
    }
};

Similarly, for visualizeInOrder, since cityName and population are unique to city, you can't use:

std::cout << root->infoStruct.cityName << " has " << root->infoStruct.population << " population\n";

Instead, you can overload the ostream& operator<< for your city class to print all the detail information. And inside visualizeInOrder, it would just become:

std::cout << root->infoStruct << '\n';