1

我正在用 C++ 练习一些二叉树算法，并尝试编写尽可能通用的代码。特别是，我希望我的函数（算法）能够对任何（当然，在某种程度上）树状数据结构进行操作。

树节点结构可能以不同的方式定义，例如：

struct binary_tree_node
{
    int data;
    struct binary_tree_node *left;
    struct binary_tree_node *right;
};

或者像这样：

struct binary_tree_node2
{
    long key;
    struct binary_tree_node2 *first_child;
    struct binary_tree_node2 *second_child;
};

或者无论如何，但与该模式非常相似。所以我希望我的函数/算法能够使用任何这些或类似的数据结构。

例如，这是我定义一个简单函数的方式：

template <typename TreeNode, typename DataType = typename TreeNode::data_type>
TreeNode*
binary_tree_new_node(DataType value = DataType(),
                     DataType  TreeNode::* data  = &TreeNode::data,
                     TreeNode* TreeNode::* left  = &TreeNode::left,
                     TreeNode* TreeNode::* right = &TreeNode::right)
{
    TreeNode *newnode = new TreeNode();
    newnode->*data  = value;
    newnode->*left  = nullptr;
    newnode->*right = nullptr;
    return newnode;
}

因此，可以将该函数与您选择的任何合适的树节点类型一起使用。如果数据成员有不同的名称（不是data，left和right），那么可以调用该函数并将指针传递给相应的数据成员。这样，该函数不依赖于（或至少可以自行调整）输入类型的数据成员的命名方式。

到目前为止它工作得很好，但是随着我实现越来越多的函数，我厌倦了这些指向数据成员的指针参数，我必须将它们列为函数的可选参数。那么有没有更好的方法来处理这个问题？也许是某种特质？或者以其他方式？

我想尽可能少地保持对输入类型的要求。例如，不应强制客户端程序只定义树节点类型。它也不应该被迫使用/派生于任何提供的类型或模板。当然，客户端程序可能会重复使用一些提供的模板，如下面的模板，我也定义了它，但不应该真的被迫这样做。

template<typename T>
struct binary_tree_node
{
    using data_type = T;
    data_type data;
    struct binary_tree_node *left;
    struct binary_tree_node *right;
};

这里有哪些可用选项？这有任何意义吗？:)

提前致谢

4

2 回答 2

0

STL 集合库的工作方式是树库的作者将提供节点类，因此模板的所有用户需要做的就是提供数据。您似乎想要的另一个选择是侵入性数据结构（这对于谷歌来说是一个很好的术语）。对于那些你有几个选择，第一个是要求数据成员是左、右和数据。其次需要具有特定名称的访问函数，以便模板可以找到它们。第三，要求函子作为模板参数传入，以便您可以使用它们来查找所需的数据。就我个人而言，我发现 STL 方法最不混乱，其次是仿函数方法。

于 2013-06-18T19:09:59.957 回答
0

为了使您的算法尽可能通用，我建议使用仿函数。你的 binary_tree_new_node 看起来像

template<typename G, typename L, typename R, typename AT, typename AD, typename D>
auto binary_tree_new_node(
    G generator,
    L left,
    R right,
    AT assign_tree,
    AD assign_data,
    D data) ->decltype( generator() )
{
    auto  tree = generator();
    auto& l    = left(tree);
    auto& r    = right(tree);
    assign_data(tree, data);
    assign_tree(l, nullptr);
    assign_tree(r, nullptr);
    return tree;
}

对于您的 binary_tree_node，仿函数如下所示：

// WARNING!!! Very dangerous code!!!

binary_tree_node* generator()
{
    return new binary_tree_node;
}

binary_tree_node*& left(binary_tree_node* tree)
{
    return tree->left;
}

binary_tree_node*& right(binary_tree_node* tree)
{
    return tree->right;
}

void assign_data(binary_tree_node* node, int data)
{
    node->data = data;
}

void assign_tree(binary_tree_node*& node, binary_tree_node* data)
{
    node = data;
}
于 2013-06-18T22:53:46.717 回答