Mattia Paterna Mattia Paterna - 21 days ago 4
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.

Answer

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 leftand 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.