Memory allocation In Tree

Question

Hello everyone i wish you are having a great day, i have a problem with allocation memory for my tree with some code i think it's easier to explain and understand.

 #define H 7

 class Node{

    public:
         int node_number;
         int depth;
         int value;
         Node* nodes[L];
    public:
         Node new_node(int node_number,int depth,int value);
         void  add_node(Node root_node,Node new_node);
         void  print_node(Node print_node);
};

To create a node my function is here

Node Node::new_node(int node_number,int depth,int value){
    Node x;
    x.node_number=node_number;
    x.depth=depth;
    x.value=value;
    x.nodes[L]=(Node*) std::malloc(L*sizeof(Node));
    return x; 
 }

and now when i want to add nodes in the node him self like declared in the class i got Segmentation fault (core dumped)

void Node::add_node(Node root_node,Node new_node){
    root_node.nodes[0]=&(new_node);
}

My main function

Node root_node;
root_node=root_node.new_node(10,2,23);

Node x;
x=x.new_node(17,19,7);
root_node.add_node(root_node,x);
root_node.print_node(root_node);

Thank you so much

Note, that with `&(new_node)` you get the address of a temporary object. — vahancho, Apr 08 '19 at 12:39
`Node* nodes[L];` Was this supposed to be `L` or `H` either way you should pick a better name. — drescherjm, Apr 08 '19 at 12:40
Don't store a pointer you acquire with `&` for later use. And don't use `malloc` in C++. And don't assign outside the bounds of an array. Take a deep dive into a good [C++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). — molbdnilo, Apr 08 '19 at 12:43
As an aside, why the `new_node` functionality effectively *not* wrapped in a constructor? Just because you don't want to allocate memory on heap? — sjsam, Apr 08 '19 at 12:45
@GhouibiGhassen it does, and indeed I should actually have asked: is there a specific reason that you use malloc as in more than 99% (arbitrarily chosen number) of the cases malloc should not be your starting point when using C++. As a starting point, you can outsource memory allocation to standard containers such as `std::vector`. — Michiel uit het Broek, Apr 08 '19 at 14:49

PeteBlackerThe3rd · Answer 1 · 2019-04-08T13:32:21.873

There are few problems here. Firstly you're not actually allocating any new memory. The line in the new_node method

Node x;

is a local variable so it will be destroyed when the method completes, the method then returns a copy of this object on the stack.

Then in the add_node method there is another problem:

root_node.nodes[0]=&(new_node);

This line doesn't call the node_node method, it actually takes the address of the function. Even if it did call the method it would be returning a copy of the object on the stack not a pointer to an object on the heap which is what you need.

Your code doesn't show the definition of L, I'm going to assume that it is a macro definition. Your new_node method should look like this, node the new reserved word, this is where the new object is created on the heap:

Node* Node::new_node(int node_number,int depth,int value){
    Node *x = new Node;
    x->node_number=node_number;
    x->depth=depth;
    x->value=value;
    // x->nodes[L]=(Node*) std::malloc(L*sizeof(Node));
    // not needed if L is a macro and needs correcting if L is a variable
    return x; 
 }

Now this method returns a pointer to a new object on the heap.

Your add_node method will then look like this:

void Node::add_node(Node root_node,Node new_node){
    root_node.nodes[0]=new_node(/* Need to add params here! */);
}

However there is a much better way of doing what you want here. You should write a constructor for the Node class like below:

Node::Node(int node_number,int depth,int value)
{
    this->node_number = node_number;
    this->depth = depth;
    this->value = value;
}

This removes the need for the new_node method and means your add_node method will look like this:

void Node::add_node(Node root_node,Node new_node){
    root_node.nodes[0]=new Node(/* Need to add params here! */);
}

Hope this helps.

Now that `x` is a pointer, those member accesses should be `x->node_number ...` etc. — Useless, Apr 08 '19 at 12:56
Doesn't the `new_node` variable shadow the `new_node()` function? — drescherjm, Apr 08 '19 at 13:16
Yes it does, I didn't spot that one. There are lot of things going wrong in this code. — PeteBlackerThe3rd, Apr 08 '19 at 13:31
Thank you so much my friend this help me so much my greetings bro @PeteBlackerThe3rd — Ghouibi Ghassen, Apr 08 '19 at 13:32

score 0 · Answer 2 · answered Apr 08 '19 at 15:42

Although there is already a complete answer provided by PeteBlackerThe3rd, I deem it worthy to also provide an answer that does not use any manual memory allocation as this is often the preferred way in C++.

I took the liberty to make some minor adjustments, e.g., when adding a node it is not necessary to provide the depth in the tree as this can be derived from its parent's node.

The struct uses a std::vector which has (at least) two benefits compared to the code provided in the question. First, there is no need to know the maximum number of children nodes during compile time. If you want to fix this during compile time one can easily replace the std::vector by std::array. Second, there is no need to manually free memory at destruction as this is all taken care of by std::vector.

#include <iomanip>
#include <vector> 

struct Node
{
  // I expect these data members to be constants
  int const d_nodeNumber;
  int const d_depth;
  int const d_value;

  std::vector<Node> d_childNodes;

  Node() = delete;

  Node(int number, int depth, int value)
  :
    d_nodeNumber (number),
    d_depth      (depth),
    d_value      (value),
    d_childNodes ()
  { }

  /*
   * Note that this function does not ask for a 'depth' argument
   * As the depth of a child is always the depth of its parent + 1
   */

  void addChildNode (int number, int value)
  {
    d_childNodes.emplace_back(number, d_depth + 1, value);
  }

  /*
   * Just an arbitrarily function to generate some output
   */

  void showTreeFromHere() const
  {
    int const n = 1 + 2 * d_depth;

    std::cout << std::setw(n) << ' '
              << std::setw(5) << d_nodeNumber 
              << std::setw(5) << d_depth 
              << std::setw(5) << d_value << std::endl;

    for (Node const &n: d_childNodes)
      n.showTreeFromHere();
  }
};

The struct can be used as follows:

int main() 
{
  Node root_node(0,0,0);

  // Add two child nodes
  root_node.addChildNode(1,1);
  root_node.addChildNode(2,1);

  // Add six grandchildren
  root_node.d_childNodes[0].addChildNode(3,8);
  root_node.d_childNodes[0].addChildNode(4,8);
  root_node.d_childNodes[0].addChildNode(5,8);
  root_node.d_childNodes[1].addChildNode(6,8);
  root_node.d_childNodes[1].addChildNode(7,8);
  root_node.d_childNodes[1].addChildNode(8,8);

  root_node.showTreeFromHere();
}

Memory allocation In Tree

2 Answers2