使用C++智能指针使用父指针构建树

Question

我正在尝试用智能指针构建一个二叉树，其中节点还包括一个父指针。为此，我将子指针定义为shared_ptr，将父指针定义为weak_ptr。

我能想出的最好的办法是：

#include <iostream>
#include <memory>
using namespace std;
struct Node;
struct NodeBase {
int val;
NodeBase(int v) : val(v) {}
virtual void add_node_left(shared_ptr<Node> &ptr, int v) = 0;
virtual void add_node_right(shared_ptr<Node> &ptr, int v) = 0;
virtual ~NodeBase() {};
};
struct NodePtr {
shared_ptr<NodeBase> ptr;
template<typename... Args>
NodePtr(Args&&... args) : ptr(std::forward<Args>(args)...) {}
void add_left(int v) {
shared_ptr<Node> node_ptr = std::static_pointer_cast<Node>(ptr);
ptr->add_node_left(node_ptr, v);
}
void add_right(int v) {
shared_ptr<Node> node_ptr = std::static_pointer_cast<Node>(ptr);
ptr->add_node_right(node_ptr, v);
}
};
struct Node : public NodeBase {
NodePtr left, right;
weak_ptr<Node> parent;
Node(int v) : NodeBase(v), left(nullptr), right(nullptr), parent() {}
shared_ptr<Node> make_child(shared_ptr<Node> &selfptr, int v) {
auto child = make_shared<Node>(v);
child->parent = selfptr;
return child;
}
void virtual add_node_left(shared_ptr<Node> &selfptr, int v) {
left = make_child(selfptr, v);
}
void virtual add_node_right(shared_ptr<Node> &selfptr, int v) {
right = make_child(selfptr, v);
}

virtual ~Node() {};
};
struct Tree {
NodePtr root;
Tree() : root(nullptr) {};
Tree(int val) {
add_root(val);
}
void add_root(int val) {
root = make_shared<Node>(val);
}
};
int main() {
Tree tree;
tree.add_root(10);
tree.root.add_left(5);
tree.root.add_right(12);
}

首先，这是正确的吗？

其次，我不太喜欢定义NodeBase基类。原因是我可以将创建父weak_ptr所需的shared_ptr传递给add_node_left和add_node_right。有没有一种方法可以避免NodeBase，但保持相同(或类似(的接口？

Answer 1

您既不需要NodeBase也不需要NodePtr。

struct Node : std::enable_shared_from_this {
int val;
std::shared_ptr<Node> left, right;
std::weak_ptr<Node> parent;
Node(int v, std::weak_ptr<Node> p) : val(v), left(), right(), parent(p) {}
void add_node_left(int v) {
left = std::make_shared<Node>(v, weak_from_this()); // shared_from_this() pre C++17
}
void add_node_right(int v) {
right = std::make_shared<Node>(v, weak_from_this()); // shared_from_this() pre C++17
}
};