CODEWITHSUNDEEP
c++smart-pointers
Dogunbound hounds
Dogunbound hounds

Reputation: 613

adding nodes to tree with unique pointer

I am very new to smart pointers and I am trying to create a doubly tree where the child nodes are pointed from the parents by a unique pointer, and the children are pointing to the parents via raw pointer. So when A parent node gets destroyed the whole sub-tree will get destroyed in the process.

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
}

I don't understand how to point to a new node that might have a tree I want to connect. If I use make_unique I believe that will create a new node Instead of preserving the tree.

I might be totally wrong about this since I just learned smart pointers about 4 days ago (Realistically enough time to learn something).

Upvotes: 3

Views: 1705

Answers (3)

Giuseppe Puoti
Giuseppe Puoti

Reputation: 140

First of all, an empty tree is possible and a default constructed node will fit well. Parent reference will be known at the time a node is attached so, child's node parent shall be updated once a node is set as left or right child of the current tree.

It might be a good idea to receive unique_ptr as you are taking ownership of the pointer you receive. Here is an example implementation:

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;
  }
};

You will use it like the following:

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;
}

I'm pretty new to unique_ptr myself, hope someone will further correct me. BTW don't use names hat that starts with _ for your identifies, they are reserved.

Upvotes: 8

Sailanarmo
Sailanarmo

Reputation: 1191

I believe that you want to make the parent, left and right child public. At least, this is how I have always implemented my nodes using a struct instead:

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;

};

Someone please correct me if I am wrong.

Upvotes: 0

R Sahu
R Sahu

Reputation: 206667

I don't think you can use:

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

This won't allow to build the tree node by node. Instead, use:

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

That way, you can create the first node using:

Node firstNode(nullptr, nullptr, nullptr);

From there, you can build other nodes.

To build a simple tree, with three nodes as below

            N1
           /  \
         N2    N3

you can use:

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;

Upvotes: 2

Related Questions