如何泛化C++二叉树创建流程以支持多种自定义类型节点？

你现有代码中的node结构本身已经是模板实现，仅需解耦和具体结构体绑定的三个逻辑即可完成改造，无需重构核心树结构： #

改造后完整可运行代码 #

#include <iostream>
#include <functional>

template <typename T>
struct node
{
    T infoStruct;
    node* left = nullptr;
    node* right = nullptr;
};

struct city
{
    std::string cityName;
    int population;
};

struct people
{
    std::string name;
    std::string surname;
    int age;
    int weight;
};

// 泛化插入函数，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;
    }
}

// 泛化中序遍历函数，Printer为自定义打印规则
template <typename T, typename Printer>
void visualizeInOrder(node<T>* root, Printer print)
{
    if (root->left) visualizeInOrder(root->left, print);
    print(root->infoStruct);
    if (root->right) visualizeInOrder(root->right, print);
}

int main()
{
    // 此处可切换为node<people>直接使用people结构体构建树
    node<city>* root = nullptr;
    char choice;

    // 定义city类型的比较规则：按人口升序
    auto cityComp = [](const city& a, const city& b) {
        return a.population < b.population;
    };
    // 定义city类型的打印规则
    auto cityPrinter = [](const city& c) {
        std::cout << c.cityName << " has " << c.population << " population\n";
    };

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

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

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

    visualizeInOrder(root, cityPrinter);

    // 内存释放逻辑可按需补充
    return 0;
}

扩展其他结构体的方法 #

如果要切换为people或者其他自定义结构体，仅需修改3处代码即可：

1. 替换根节点类型，比如将node<city>* root = nullptr;改为node<people>* root = nullptr;
2. 定义对应结构体的比较规则，例如people按年龄升序：

auto peopleComp = [](const people& a, const people& b) {
    return a.age < b.age;
};

3. 定义对应结构体的打印规则和输入采集逻辑，替换main中原有city的相关代码即可。

内容的提问来源于stack exchange，提问作者JohnBrownie_