树创建的概括

Question

我想概括这个二叉树的创建过程，以便让不同类型的节点包含在树本身中。例如，我想让用户选择是否要用结构 city（就像我在下面所做的那样）或用结构 people 或他想在源代码中定义的任何结构来构建树。

是否有一种简单的方法来实现这些更改？

这是代码：

#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;
    }
}

Answer 1

大部分作品已经存在。您可以做的第一步是简单地更改 insertNewNode 和 visualizeInOrder 的签名以接受 node<T> 而不是 node<city>.

所以 insertNewNode 会变成：

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;
    }
}

但是，这里的问题是泛型类型 T 不会有成员 population。所以不要使用：

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

您可以向签名添加一个模板化比较函数 Comp comp，然后使用它进行比较，并将它也传递给递归调用：

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;
    }
}

但是，这不是添加比较函数的最有效方法，因为您总是必须手动向 main 中第一次调用 insertNewNode 添加一些函数，例如 lambda。所以目前，您将在 main 中调用该函数，例如：

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

这非常冗长，如果 population 是私有成员，这将直接不起作用。相反，您可以使用 std::less 作为默认值，因此声明将是：

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

现在你可以像我之前那样手动添加一个比较函数，或者你可以在你的cityclass中添加一个operator<，它将自动用于insertNewNode 函数：

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

同样，对于 visualizeInOrder，由于 cityName 和 population 是 city 所独有的，您不能使用：

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

相反，您可以为 city class 重载 ostream& operator<< 以打印所有详细信息。在 visualizeInOrder 里面，它会变成：

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

树创建的概括

Generalization of tree creation

c++

tree

templates

struct