Unexpected segfault when creating a binary tree

Question

I've got the following representation for a BinaryTree class:

#include "treecode.hh"
Treecode::Treecode(){}

Treecode::Treecode(string s, int f) {
    this->s = s;
    this->freq = f;
    this->left = NULL;
    this->right = NULL;
}

Treecode::Treecode(Taula_freq taula_f) {
    priority_queue<Treecode, vector<Treecode>, Compare_trees> q;
    for (auto a: taula_f.get_taula()) {
        Treecode myTree = Treecode(a.first, a.second);
        q.push(myTree);
    }
    Treecode res;
    while (q.size() > 1) {
        Treecode a = q.top();
        q.pop();
        Treecode b = q.top();
        q.pop();
        res = Treecode(a,b);
        q.push(res);
    }
    res = q.top();
    this->freq = res.freq;
    this->s = res.s;
    this->left = (res.left);
    this->right = (res.right);
}


Treecode::Treecode(Treecode& a, Treecode& b) {
    this->left = &b;
    this->right = &a;
    this->freq = a.freq + b.freq;
    this->s = a.s + b.s;
}

int Treecode::get_freq() {
    return this->freq;
}

string Treecode::get_s() {
    return this->s;
}

void Treecode::print_tree(const Treecode& a) {
    cout << a.s << " " << a.freq << endl;
    if (a.left != NULL)
        print_tree(*a.left);
    if (a.right != NULL)
        print_tree(*a.right);
}

And this is the hh

#ifndef TREECODE_HH
#define TREECODE_HH
#include "taula_freq.hh"
#include <queue>
using namespace std;


class Treecode{
private:
    int freq;
    string s;
    Treecode* left;
    Treecode* right;

public:
    Treecode();
    Treecode(string s, int f);
    Treecode(Taula_freq taula);
    Treecode(Treecode& a, Treecode& b);
    int get_freq();
    string get_s();
    void print_tree(const Treecode &a);
};


class Compare_trees {
public:
         bool operator() (Treecode a, Treecode b) {
            if (a.get_freq() < b.get_freq()) return true;
            else if (b.get_freq() < a.get_freq()) return false;
            else if (a.get_s() < b.get_s()) return true;
            else return false;
         } 
 };



#endif

So the problem here is that the root node is being generated correctly according to the specification, but when I call the function print_tree for checking the links between the roots and the left and right children I get an unexpected segfault. The constructor for creating a new tree giving two different trees seems to be the problem, but I don't know why because I'm passing the two parameters by reference and accessing correctly to the memory location (I think) using the & operator. Also, everytime I create a new Tree using the Treecode(string s, int f) constructor, I make sure that the left and right nodes are NULL, so I'm also unsure why the base case of print_tree(...) is failing.

Edit: here is the main and taula_freq class

taula_freq.hh

#ifndef TAULA_FREQ_HH
#define TAULA_FREQ_HH

#include <map>
#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;

class Taula_freq {

private:
    map<string, int> taula;

public:
    Taula_freq();
    Taula_freq(string c, int n);
    //Per fer-lo una mica mes net
    //Taula_freq(vector<pair<string,int> >);

    void add_freq(string c, int n);

    void print_taula();
    int get_freq(string s);
    map<string, int> get_taula();

};

#endif

taula_freq.cc

#include "taula_freq.hh"

Taula_freq::Taula_freq(){}

Taula_freq::Taula_freq(string c, int n) {
    this->taula[c] = n;
}

void Taula_freq::add_freq(string c, int n) {
    this->taula[c] = n;
}

void Taula_freq::print_taula() {
    for (auto a : this->taula) {
        cout << "(" << a.first << ", " << a.second << ")" << endl;
    }
}

int Taula_freq::get_freq(string s) {
    if (this->taula.find(s) == this->taula.end())
        return -1;
    else return this->taula[s];
}

map<string, int> Taula_freq::get_taula() {
    return this->taula;
}

main.cc

#include "taula_freq.hh"
#include "treecode.hh"
using namespace std;

int main() {
    Taula_freq t = Taula_freq("a", 30);
    t.add_freq("b", 12);
    t.add_freq("c", 18);
    t.add_freq("d", 15);
    t.add_freq("e", 25);
    Treecode tree = Treecode(t);
    tree.print_tree(tree);
}

Edit 2:

I already tried to add an assignment operator as follows, but I get also the segfault:

Treecode& Treecode::operator= (const Treecode& other){
    if (this != &other) { 
        this->s = other.s;
        this->freq = other.freq;
        this->left = other.left;
        this->right = other.right;
        }
        return *this;
    }

Edit 3

Ok, I will mark this as solved. Thanks for pointing out the deep and shallow copy in the comments. My c++ is really rusty...

Treecode& Treecode::operator=(const Treecode& other){
    if (this != &other) { 
        this->s = other.s;
        this->freq = other.freq;
        this->left = new Treecode();
        this->right = new Treecode();
        if (other.right != NULL) {
            this->right->freq = other.right->freq;
            this->right->s = other.right->s;
            if (other.right->left != NULL)
                this->right->left = other.right->left;
            if (other.right->right != NULL)
                this->right->right = other.right->right;
        }
        if (other.left != NULL) {
            this->left->freq = other.left->freq;
            this->left->s = other.left->s;
            if (other.left->left != NULL)
                this->left->left = other.left->left;
            if (other.left->right != NULL)
                this->left->right = other.left->right;
        }

        }
        return *this;
    }

Please read [What is The Rule of Three?](https://stackoverflow.com/questions/4172722/what-is-the-rule-of-three). — πάντα ῥεῖ, May 05 '19 at 11:15
Please post [mcve] including the `main` function creating the trees. Why is `print_tree` a member function? Why are you creating `res` in the combined constructor instead of directly assigning the `s` and `freq`. — Quimby, May 05 '19 at 11:17
@πάνταῥεῖ I edited the question with an assignment operator, but the segfault is still there. Thanks for the recommendation tho. — Norhther, May 05 '19 at 11:42
You added an assignment that does the same as the default assignment. Adding one is not enough; it needs to Do The Right Thing, too. — molbdnilo, May 05 '19 at 11:51
@πάνταῥεῖ I think I know the difference, but I suppose that not that well if I'm having this kind of trouble pointed out by you. Could you be a little more specific in reference to the code? Thanks — Norhther, May 05 '19 at 11:51
@molbdnilo I'm also trying to make the assignment with **new Treecode** for left and right child, but It don't work neither. — Norhther, May 05 '19 at 11:54
You seem to not understand pointers and lifetime of local variables.`res = Treecode(a,b);` will stop working after the next while loop iteration because the variables `a,b` are destroyed. Perhaps you need a good [C++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) — Quimby, May 05 '19 at 12:07

score 0 · Accepted Answer · answered May 05 '19 at 12:25

Thanks to the comments, I came up with this

Treecode& Treecode::operator=(const Treecode& other){
    if (this != &other) { 
        this->s = other.s;
        this->freq = other.freq;
        this->left = new Treecode();
        this->right = new Treecode();
        if (other.right != NULL) {
            this->right->freq = other.right->freq;
            this->right->s = other.right->s;
            if (other.right->left != NULL)
                this->right->left = other.right->left;
            if (other.right->right != NULL)
                this->right->right = other.right->right;
        }
        if (other.left != NULL) {
            this->left->freq = other.left->freq;
            this->left->s = other.left->s;
            if (other.left->left != NULL)
                this->left->left = other.left->left;
            if (other.left->right != NULL)
                this->left->right = other.left->right;
        }

        }
        return *this;
    }

Unexpected segfault when creating a binary tree

1 Answers1