0

我是 C++ 新手，所以还在学习。我正在尝试编写一个算法来递归地构建树，我通常会根据下面的方法 1 编写它，但是，当函数返回时，它会生成 RandomTreeNode 的（我希望是深度）副本，我担心调用它递归，因此更喜欢方法2。我的想法正确吗？

方法一

RandomTreeNode build_tree(std::vector<T>& data, const std::vector<funcion_ptr>& functions){
        if(data.size() == 0 || data_has_same_values(data)){
            RandomeTreeNode node = RandomTreeNode();
            node.setData(node);
            return node;
        }

        RandomTreeNode parent = RandomTreeNode();
        vector<T> left_data = split_data_left(data);
        vector<T> right_data = split_data_right(data);
        parent.set_left_child(build_tree(left_data));
        parent.set_right_child(build_tree(right_data));
        return parent;
    }

方法二

void build_tree(RandomTreeNode& current_node, vector<T> data){
    if(data.size() == 0 || data_has_same_values(data)){
        current_node.setData(node);
    }

    vector<T> left_data = split_data_left(data);
    vector<T> right_data = split_data_right(data);

    RandomTreeNode left_child = RandomTreeNode();
    RandomTreeNode right_child = RandomTreeNode();
    current_node.set_left_child(left_child);
    current_node.set_right_child(right_child);

    build_tree(left_child, left_data);
    build_tree(right_child, right_data);

}
4

1 回答 1

1

有几处改进。

  • 首先，您正在复制一个向量。据我了解您的函数名称，您将向量分成两个块（[left|right]而不是[l|r|lll|r|...]）。因此，您不必每次都传递一个向量，而只需传递索引来指定范围。

  • 方法 2，如果实施得当，在内存中的效率会更高。所以，你应该改进它背后的想法。

  • 最后，您可以使用更适合该问题的辅助功能（方法 1 和方法 2 的混合）。

这是一些示例代码：

// first is inclusive
// last is not inclusive
void build_tree_aux(RandomTreeNode& current_node, std::vector<T>& data, int first, int last)
{
    if(last == first || data_has_same_values(data,first,last))
    {
        current_node.setData(data,first,last);
        // ...
    }

    // Find new ranges
    int leftFirst = first;
    int leftLast = split_data(data,first,last);
    int rightFirst = leftLast;
    int rightLast = last;

    // Instead of copying an empty node, we create the children
    // of current_node, and then process these nodes
    current_node.build_left_child();
    current_node.build_right_child();

    // Recursion, left_child() and right_child() returns reference
    build_tree_aux(current_node.left_child(),data,leftFirst,leftLast);
    build_tree_aux(current_node.right_child(),data,rightFirst,rightLast);
    /*
        // left_child() and right_child() are not really breaking encapsulation,
        // because you can consider that the child nodes are not really a part of
        // a node.
        // But if you want, you can do the following:
        current_node.build_tree(data,leftFirst,leftLast);
        // Where RandomTreeNode::build_tree simply call build_tree_aux on the 2 childrens
    */
}

RandomTreeNode build_tree(std::vector<T>& data)
{
    RandomTreeNode root;

    build_tree_aux(root,data,0,data.size());

    return root;
}
于 2012-10-16T21:01:33.257 回答