CODEWITHSUNDEEP
c++recursionbinary-tree
Alex2134
Alex2134

Reputation: 567

Trying to create a pointer to parent node whilst building binary Tree

I'm an enthusiast, very new to c++, and I'm working my way through the best way to implement this tree.

I have a number of issues, but primarily I'm trying to figure out the best way of storing a pointer to the parent node, during building of the tree; but I'm getting a Bus Error when I try to access the root->parent->data value, in preOrder member function. I can happily access the address root->parent, this outputs without error.

Could anyone suggest what I'm doing fundamentally wrong here? I'm thinking it might be a scope issue, but there may be a better way of building the tree? 

class FibTree {

    class Node {
    public:
        int data;
        Node const* left;
        Node const* right;
        Node const* parent;
        Node (void);
    };
    Node const* root; // 'root' pointer to constant Node

public:
    FibTree (int);
    Node const* getRoot(void);
    void preOrder(Node const* root);

};

// Tree constructor
FibTree::FibTree(int n) {
    this->root = buildTree( n );
};

FibTree::Node const* FibTree::getRoot(void) {
    return this->root;
}

private:
    static Node* buildTree( int n, Node* parent = NULL );
};

void FibTree::preOrder(Node const* root) {
    if (root == NULL)
        return;
    // *** This prints the address of the parent node correctly
    cout << root->data << "[" << root->parent << "]" << ",";
    // *** This produces a 'Bus Error'
    cout << root->data << "[" << root->parent->data << "]" << ",";
    preOrder(root->left);
    preOrder(root->right);
}

FibTree::Node* FibTree::buildTree( int n, Node* parent ) {
    // *** Is there a scope issue with 'thisNode' here?
    Node* thisNode = new Node();
    thisNode->parent = parent;
    if (n < 2) {
        thisNode->left = NULL;
        thisNode->right = NULL;
        thisNode->data = n;
        return thisNode;
    } else {
        thisNode->left = buildTree( n - 1 , thisNode );
        thisNode->right = buildTree( n - 2, thisNode );
        thisNode->data = thisNode->left->data + thisNode->right->data;
        return thisNode;
    }
}

// Node constructor
FibTree::Node::Node(void) {
    this->data;
    this->left;
    this->right;
    this->parent;
};

int main () {
    FibTree f(n);
    f.preOrder(f.getRoot());
    return 0;
}

Also, would there be a standard approach for avoiding having to pass the root Node to a traversal function, and have the member function, traverse the created root node. As I don't feel f.preOrder(f.getRoot()) is very elegant.

Many thanks, Alex

Upvotes: 1

Views: 2532

Answers (2)

maditya
maditya

Reputation: 8886

The problem as far as I can tell is a combination of:

this line in your buildTree function,

thisNode->parent = parent;

this function,

// Tree constructor
FibTree::FibTree(int n) {
    this->root = buildTree( n );
};

and your preOrder function.

The parent pointer is not being passed in to buildTree in the tree constructor, so the default is a NULL pointer. So root->parent will be NULL (makes sense, since it's the root).

You then call the preOrder function starting with the root. Root has a parent that is NULL, but you never check for this (you do check if the root itself is NULL).

You should do something like the following instead:

void FibTree::preOrder(Node const* root) {
    if (root == NULL)
        return;

    if(root->parent == NULL) {
      cout << root->data << " [I am the root] " << endl;
    }
    else {
      cout << root->data << "[" << root->parent->data << "]" << ",";
    }
    preOrder(root->left);
    preOrder(root->right);
}

Upvotes: 2

Daniel Frey
Daniel Frey

Reputation: 56863

I can't reproduce the problem, but the part that looks most suspicious is this:

// Node constructor
FibTree::Node::Node(void) {
    this->data;
    this->left;
    this->right;
    this->parent;
};

the statements (this->data) do absolutely nothing. Maybe you wanted (and should try):

FibTree::Node::Node()
  : data( 0 ),
    left( NULL ),
    right( NULL ),
    parent( NULL )
{
}

To explain: Your code didn't initialize the data and the pointers, so they were uninitialized. If you print the pointer, that usually works but dereferencing it could cause the error you saw.

When you do this, you might see that parent becomes NULL and that you need to check for that:

if( root->parent != NULL ) {
    cout << root->data << "[" << root->parent->data << "]" << ",";
}

Upvotes: 1

Related Questions