Mattia Paterna - 1 year ago 98
C++ Question

# segfault when setting bool possible?

I have a binary tree, whose nodes are defined as

``````struct Fibonacci_node{
ul number;
int n;
bool isLeaf;
Fibonacci_node * left;
Fibonacci_node * right;
};
``````

I'd like to set
`isLeaf`
each insertion, so that I could easily get the total number of leafs eventually. The insertion method is made up of a public method, insert, that calls the private recursive method insertR.

``````#include <iostream>
using namespace std;
typedef unsigned long ul;

class Fibonacci_tree{
private:
struct Fibonacci_node{
ul number;                              // store the n-th fibonacci number
int n;                                  // fibonacci number to compute
bool isLeaf;                            // true if the node is leaf
Fibonacci_node * left;
Fibonacci_node * right;
};

/* definition of the root of the binary tree */
Fibonacci_node * root;

/* class private methods (recursively defined) */
ul fibonacci(int n){
/* BASE CASE */
if (n == 0) { return 1; }
if (n == 1) { return 1; }

/* call the function recursively */
return fibonacci(n - 1) + fibonacci(n - 2);
};

Fibonacci_node * insertR(int n, Fibonacci_node * node){
if (!node) {
/* if pointer is null create a new node */

Fibonacci_node * tmp = new Fibonacci_node;
tmp->n = n;
tmp->number = fibonacci(tmp->n);
tmp->left = tmp->right = 0;
tmp->isLeaf = 0;

/* update the pointer and return it */
node = tmp;

/* BASE CASE */
if (n == 0) {
node->isLeaf = 1;
return node;
}
if (n == 1) {
node->isLeaf = 1;
return node;
}
}

/* call the function recursively */
node->left = insertR(n - 1, node->left);
node->right = insertR(n - 2, node->right);

return node;
};

public:
Fibonacci_tree(){
root = 0;
}
~Fibonacci_tree(){}

/* class public methods (they include private methods recursively defined)*/
void insert(int n){

/* first, create initial node and compute fibonacci for the root */
Fibonacci_node * tmp = new Fibonacci_node;
tmp->n = n;
tmp->number = fibonacci(n);
tmp->isLeaf = false;
//getNo(tmp);

/* make root point to the first element of the tree */
root = tmp;

/* then call the recursive function */
root = insertR(n, root);
};
};
/* END OF CLASS DECLARATION */

/* main program to check the class */
int main(void) {
int n = 3;

/* instantiate a Fibonacci tree */
Fibonacci_tree fib_series;
/* fill the tree */
fib_series.insert(n);

return 0;
}
``````

When I run my executable, I get

``````Segmentation fault: 11
``````

Could it be possible such scenario?
I think that because so far I haven't had any problem but this, and it started when I introduced this variable in the class definition.

The actual problem is here:

`````` /* call the function recursively */
node->left = insertR(n - 1, node->left);
``````

at that point `node->left` is not yet initialized, you pass that non inizialized value recursively to `insertR`, where you check if it's `NULL`, as it is non inizialized it is most likely non null, and then you dereference it again here: `node->left = insertR(n - 1, node->left);`. Dereferencing a non initialized pointer is undefined behaviour.

Actually you simply forgot to initialize `left`and `right` to 0 here:

``````/* first, create initial node and compute fibonacci for the root */
Fibonacci_node * tmp = new Fibonacci_node;
tmp->n = n;
tmp->number = fibonacci(n);
tmp->isLeaf = false;
tmp->left = tmp->right = 0;    // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< you forgot this.
//getNo(tmp);
``````

As you are writing in C++ why don't you write a constructor for `Fibonacci_node` where all the initialisation could be done in one place ?

`tmp->isLeaf = false;` causing a segfault on your computer is just a consequence of undefined behaviour.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download