在现代 C++ 中,通常建议在处理二叉树时使用 unique_ptr
来明确子树的所有权。例如,Elements of Programming Interviews推荐:
template <typename T>
struct Node {
T data;
unique_ptr<Node<T>> left, right;
};
我刚刚学习C++11特性,我想知道初始化对应于某种结构的二叉树最方便的方法是什么。我的用例是为特定树编写单元测试。例如,我想生成这棵树:
5
/ \
3 4
/ \
1 2
下面的方法确实有效,但确实很麻烦:
// first attempt: temporary variables & high syntactic noise
unique_ptr<Node<int>> tmp_n1(new Node<int>{1, nullptr, nullptr});
unique_ptr<Node<int>> tmp_n2(new Node<int>{2, nullptr, nullptr});
unique_ptr<Node<int>> tmp_n3(new Node<int>{3, move(tmp_n1), move(tmp_n2)});
unique_ptr<Node<int>> tmp_n4(new Node<int>{4, nullptr, nullptr});
unique_ptr<Node<int>> root(new Node<int>{5, move(tmp_n3), move(tmp_n4)});
我希望实现的是摆脱临时变量,并在一个嵌套语句中初始化树。如果代码结构类似于树结构那就太好了。但是,以下尝试失败并出现“无法转换”错误:
// second attempt: nested, but still a lot of syntax noise
unique_ptr<Node<int>> root(new Node<int>{5,
new unique_ptr<Node<int>>(new Node<int>{3,
new unique_ptr<Node<int>>(new Node<int>{1, nullptr, nullptr}),
new unique_ptr<Node<int>>(new Node<int>{2, nullptr, nullptr})
}),
new unique_ptr<Node<int>>(new Node<int>{4, nullptr, nullptr})
});
有什么想法如何以语法干净、简洁、灵活的方式编写这样的树初始化吗?
最佳答案
这是一个使用 C++14 make_unique
的解决方案默认参数设置为 nullptr
对于左右子树,为了避免原始 new
:
#include <iostream>
#include <memory>
template<class T>
struct Node;
template<class T>
using node_ptr = std::unique_ptr<Node<T>>;
template<class T>
struct Node
{
T data;
node_ptr<T> left, right;
Node(T const& value, node_ptr<T> lhs, node_ptr<T> rhs)
:
data(value), left(std::move(lhs)), right(std::move(rhs))
{}
};
template<class T>
auto make_node(T const& value, node_ptr<T> lhs = nullptr, node_ptr<T> rhs = nullptr)
{
return std::make_unique<Node<T>>(value, std::move(lhs), std::move(rhs));
}
template<class T>
void print_tree(Node<T> const& node)
{
std::cout << "{ ";
std::cout << node.data;
if (node.left) {
std::cout << ", ";
print_tree(*(node.left));
}
if (node.right) {
std::cout << ", ";
print_tree(*(node.right));
}
std::cout << " }";
}
int main()
{
auto const root = make_node(
5,
make_node(
3,
make_node(1),
make_node(2)
),
make_node(4)
);
print_tree(*root);
}
Live Example这也打印了树。
更新:感谢@Jarod42的评论,我更改了 print_tree
的签名采取Node<T> const&
这样它现在是 const 正确的,您不必输入 .get()
任何地方。我还制作了一个模板别名 node_ptr<T>
为 unique_ptr<Node<T>>
提供更简洁的符号在实现中。
关于c++ - 如何初始化嵌套结构的 unique_ptr (例如二叉树),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32601661/