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

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

首先,可以使用空树,并且默认构造的节点将很好地适合.在附加节点时将知道父引用,因此,一旦将节点设置为当前树的左子节点,就应更新子节点父节点.

接收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自己很陌生,希望有人能进一步纠正我.顺便说一句,不要使用以_标识开头的名字帽,它们是保留的.