使用唯一指针向树添加节点

Question

我对智能指针非常陌生，我正在尝试创建一个双树，其中子节点通过唯一指针从父节点指向，子节点通过原始指针指向父节点。因此，当父节点被销毁时，整个子树将在此过程中被销毁。

class Node {
private:
    Node *parent;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
public:
    Node(Node* _left, Node* _right, Node* _parent);
};

Node::Node(Node* _left, Node* _right, Node* _parent) {
    parent = &_parent;

    //this is where the problem starts
}

我不明白如何指向可能有我想要连接的树的新节点。如果我使用 make_unique 我相信会创建一个新节点而不是保留树。

我可能完全错了，因为我大约 4 天前才学习智能指针（实际上有足够的时间学习一些东西）。

Answer 1

我认为你不能使用：

Node(Node _left, Node _right, Node _parent);

这将不允许逐个节点地构建树。相反，使用：

Node(Node* _left, Node* _right, Node* _parent);

这样，您可以使用以下方法创建第一个节点：

Node firstNode(nullptr, nullptr, nullptr);

从那里，您可以构建其他节点。

构建一个简单的树，三个节点如下

            N1
           /  \
         N2    N3

您可以使用：

Node* N1 = new Node(nullptr, nullptr, nullptr);
Node* N2 = new Node(nullptr, nullptr, N1);
Node* N3 = new Node(nullptr, nullptr, N1);

N1->left = N2;  // Use the equivalent member function.
N1->right = N3;

Answer 2

我相信你想要parent，左右childpublic。至少，这就是我一直使用 struct 来实现我的节点的方式：

struct Node
{
    Node(std::unique_ptr<Node> _parent = nullptr, 
std::unique_ptr<Node> _left = nullptr, std::unique_ptr<Node> _right = nullptr) : parent(_parent), left(_left), right(_right) {}

    std::unique_ptr<Node> parent;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;

};

如有错误请指正

Answer 3

首先，空树是可能的，默认构造的节点会很合适。在附加节点时将知道父引用，因此，一旦将节点设置为当前树的左或右子节点，子节点的父节点将被更新。

接收 unique_ptr 可能是个好主意，因为您正在取得接收到的指针的所有权。这是一个示例实现：

class Node {
private:
  Node *parent = nullptr;
  std::unique_ptr<Node> m_left;
  std::unique_ptr<Node> m_right;

public:

  void left(std::unique_ptr<Node> child) {
    m_left = std::move(child);
    m_left->parent = this;
  }

  void right(std::unique_ptr<Node> child) {
    m_right = std::move(child);
    m_right->parent = this;
  }
};

您将像下面这样使用它：

int main()
{
  auto tree = std::make_unique<Node>();
  auto subtree = std::make_unique<Node>();

  subtree->right(std::make_unique<Node>());
  tree->right(std::make_unique<Node>());
  tree->left(std::move(subtree));
  return 0;
}

我自己对unique_ptr还很陌生，希望有人能进一步纠正我。顺便说一句，不要使用以 _ 开头的名称作为您的标识，它们是保留的。

使用唯一指针向树添加节点

adding nodes to tree with unique pointer

c++

smart-pointers