使用 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 基础 class。这样做的原因是我可以将 shared_ptr 传递给 add_node_left 和 add_node_right，需要创建父 weak_ptr。有没有一种方法可以避免 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
    }
};

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

Building tree with a parent pointer using C++ smart pointers

c++

smart-pointers