Построение дерева с родительским указателем с использованием умных указателей C ++ - PullRequest
Новая
       9

Построение дерева с родительским указателем с использованием умных указателей C ++

0 голосов
/ 05 ноября 2019

Я пытаюсь построить двоичное дерево с умными указателями, где узлы также включают родительский указатель. Для этого я определил дочерние указатели как 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);
}

First ofвсе, это правильно?

Во-вторых, мне не очень нравится определять базовый класс NodeBase. Причина в том, что я могу передать shared_ptr в add_node_left и add_node_right, необходимые для создания родителя weak_ptr. Есть ли способ сделать это, чтобы избежать NodeBase, но поддерживать тот же (или аналогичный) интерфейс?

1 Ответ

1 голос
/ 05 ноября 2019

Вам не нужно 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
    }
};
...