8 Replies - 339 Views - Last Post: 28 October 2013 - 08:46 PM Rate Topic: -----

#1 jc310xc  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 15
  • Joined: 14-January 11

Binary Search Tree in C++ -- Pointer issues?

Posted 27 October 2013 - 10:49 AM

Hi,

I'm attempting to create a binary search tree with c++. However, I'm fairly new at the language, and I'm pretty sure I'm tripping over pointer issues.

Currently, the code defines an object of type "Tree". I take the first input and make it the root node, and then from there I take the values and assign them their place in the tree, noting their index and counting the number of nodes in each subtree as I place new nodes.

Here's my code:
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

class Tree{
private:
    Tree *leftChild, *rightChild;
    int val, count, key;
public:
    Tree(int,int);
    Tree(int,int,int,Tree*,Tree*);
    Tree* getLeftChild(){return leftChild;}
    Tree* getRightChild(){return rightChild;}
    int getVal(){return val;}
    int getCount(){return count;}
    int getKey(){return key;}
    bool hasRightChild();
    bool hasLeftChild();
    Tree & operator=(const Tree &rhs);
    
    void setCount(int);
    void setLeftChild(Tree*);
    void setRightChild(Tree*);
};

Tree::Tree(int a,int B)/>{
    val = a;
    key = b;
    count = 1;
    leftChild = 0;
    rightChild = 0;
}

Tree::Tree(int tree_val, int tree_key, int tree_count, Tree* tree_leftChild, Tree* tree_rightChild){
    val = tree_val;
    key = tree_key;
    count = tree_count;
    leftChild = tree_leftChild;
    rightChild = tree_rightChild;
}

bool Tree::hasLeftChild(){
    if(leftChild = 0){
        return false;
    }else{
        return true;
    }
}

bool Tree::hasRightChild(){
    if(rightChild = 0){
        return false;
    }else{
        return true;
    }
}

void Tree::setCount(int a){
    count = a;
}

void Tree::setLeftChild(Tree *t){
    leftChild = t;
}

void Tree::setRightChild(Tree *t){
    rightChild = t;
}

Tree& Tree::operator=(const Tree& node){
    Tree result(node.val,node.key,node.count,node.leftChild,node.rightChild);
    
    return result;
}

void walk_tree(Tree *node){
    //if node is a leaf, print its info
    if(!node->hasLeftChild() && !node->hasRightChild()){
        //print its info
        cout << "Node Value: " << node->getVal() << endl;
        cout << "Node Key: " << node->getKey() << endl;
        cout << "Count: " << node->getCount() << endl;
        cout << endl;
    }else if(node->hasLeftChild()){
        walk_tree(node->getLeftChild());
    }else if(node->hasRightChild()){
        walk_tree(node->getRightChild());
    }
}



int main() {
    int firstInt;
    
    cin >> firstInt;
    
    Tree root(firstInt,0);
    
    
    
    for(int i = 1; i < 9; i++){
        int input;
        cin >> input;
        Tree curNode = root;
        bool placed = false;
        
        while(!placed){
            curNode.setCount(curNode.getCount()+1);
            //check left child
            if(input <= curNode.getVal()){
                if(curNode.hasLeftChild()){
                    curNode = curNode.getLeftChild(); // returns ptr to leftChild
                }else{
                    Tree nextNode(input,i);
                    curNode.setLeftChild(nextNode);
                    placed = true;
                }
            }else if(input > curNode.getVal()){
                if(curNode.hasRightChild()){
                    curNode = curNode.getRightChild();
                }else{
                    Tree nextNode(input, i);
                    curNode.setRightChild(nextNode);
                    placed = true;
                }
            }
        }
        
        walk_tree(*root);
        
    }
    
    
    return 0;
}



Currently, I'm being given these errors:

/run-19G4RYu5i2wjKHTWPb5d/solution.cc: In member function 'Tree& Tree::operator=(const Tree&)':
/run-19G4RYu5i2wjKHTWPb5d/solution.cc:74:10: warning: reference to local variable 'result' returned [enabled by default]
/run-19G4RYu5i2wjKHTWPb5d/solution.cc: In function 'int main()':
/run-19G4RYu5i2wjKHTWPb5d/solution.cc:116:53: error: lvalue required as unary '&' operand
/run-19G4RYu5i2wjKHTWPb5d/solution.cc:119:50: error: no matching function for call to 'Tree::setLeftChild(Tree&)'
/run-19G4RYu5i2wjKHTWPb5d/solution.cc:119:50: note: candidate is:
/run-19G4RYu5i2wjKHTWPb5d/solution.cc:65:6: note: void Tree::setLeftChild(Tree*)
/run-19G4RYu5i2wjKHTWPb5d/solution.cc:65:6: note: no known conversion for argument 1 from 'Tree' to 'Tree*'
/run-19G4RYu5i2wjKHTWPb5d/solution.cc:124:54: error: lvalue required as unary '&' operand
/run-19G4RYu5i2wjKHTWPb5d/solution.cc:127:51: error: no matching function for call to 'Tree::setRightChild(Tree&)'
/run-19G4RYu5i2wjKHTWPb5d/solution.cc:127:51: note: candidate is:
/run-19G4RYu5i2wjKHTWPb5d/solution.cc:69:6: note: void Tree::setRightChild(Tree*)
/run-19G4RYu5i2wjKHTWPb5d/solution.cc:69:6: note: no known conversion for argument 1 from 'Tree' to 'Tree*'
/run-19G4RYu5i2wjKHTWPb5d/solution.cc:133:20: error: no match for 'operator*' in '*root'

I've looked all around at pointer information, I'm not quite sure where to go from where I'm at now, however.

Is This A Good Question/Topic? 0
  • +

Replies To: Binary Search Tree in C++ -- Pointer issues?

#2 eker676  Icon User is offline

  • Software Engineer
  • member icon

Reputation: 378
  • View blog
  • Posts: 1,833
  • Joined: 18-April 09

Re: Binary Search Tree in C++ -- Pointer issues?

Posted 27 October 2013 - 06:47 PM

There are a few problems here.

Line 74-76, you are returning a reference to a temporary variable. The variable will be destroyed when the function returns, thus invalidating the reference. If you had a swap function, then you could swap the temporary variable for the current instance. (This is called the copy-swap idiom.)

On line 116, you are trying to assign a pointer to a value type variable. (See the declaration on line 108. Did you want line 108 to be a pointer?)

On line 119, you are trying to pass a value type variable to a function that accepts a pointer, probably not what you want. Line 118 is probably incorrect as well.

Line 124 has the same problem as 116.

Line 133, root is not a pointer. Change line 101 so that the Tree is dynamically allocated.
Was This Post Helpful? 1
  • +
  • -

#3 jc310xc  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 15
  • Joined: 14-January 11

Re: Binary Search Tree in C++ -- Pointer issues?

Posted 27 October 2013 - 08:15 PM

Thanks! I'm having trouble wrapping my mind around pointers, I find myself constantly trying to use * to dereference variables instead of pointers, and then I end up feeling like i'm chasing my tail. That cleared up most of the problems.

When I'm overloading the "=" operator on lines 74-76, would it be sufficient to just do this?

Tree* Tree::operator=(const Tree* node){
    return node;
}



I'm not sure what to do otherwise; I know you'd mentioned a swapping function, but I'm not sure how I'd go about achieving it.

My best guess would be something like:
Tree* set_equal(Tree* node1, Tree* node2){
Tree temp_node = new Tree(node2.getVal(),node2.getKey(),node2.getCount(),node2.getLeftChild(),node2.getRightChild());
node1 = &temp_node;
}



But I'm pretty sure that would cause the same issue I was having with the "=" operator in my earlier code, because temp_node is local to the function. Am I right in thinking that?
Was This Post Helpful? 0
  • +
  • -

#4 eker676  Icon User is offline

  • Software Engineer
  • member icon

Reputation: 378
  • View blog
  • Posts: 1,833
  • Joined: 18-April 09

Re: Binary Search Tree in C++ -- Pointer issues?

Posted 27 October 2013 - 09:16 PM

That wouldn't be assignment.

Without copy-swap, a common implementation of the assignment operator would be like this:
// This is done with reference values, not pointers. 
Tree& Tree::operator=(const Tree& node){

    // Check for self assignment to avoid Trees that point
    // to the same thing.
    if(this == node) {
        return *this;
    }

    val = node.val;
    key = node.key;
    count = node.count;
    leftChild = node.leftChild;
    rightChild = node.rightChild;

    return *this;
}

This post has been edited by eker676: 27 October 2013 - 09:22 PM

Was This Post Helpful? 0
  • +
  • -

#5 jc310xc  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 15
  • Joined: 14-January 11

Re: Binary Search Tree in C++ -- Pointer issues?

Posted 28 October 2013 - 06:27 AM

When I'm checking for self assignment, the compiler sends me another error saying that the == operator doesn't take the arguments i've given it, even though i'm using "this" and "node". Same thing happens if I try to use one of their int members, like this.key and node.key.

If I avoid self assignment and run it, it doesn't populate the tree. It goes through three elements, one larger, one bigger, and then when it gets to the third element and curNode gets assigned to something other than root, I get a runtime error, a segmentation fault. I checked the val of the last node it sees and it looks like it tried to use a null pointer as a pointer to a Tree node. I imagine the problem lies with the self-assignment issue.

Here's my code thus far, with all the changes.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

class Tree{
private:
    Tree *leftChild, *rightChild;
    int val, count, key;
public:
    Tree(int,int);
    Tree(int,int,int,Tree*,Tree*);
    Tree getLeftChild(){return *leftChild;}
    Tree getRightChild(){return *rightChild;}
    int getVal(){return val;}
    int getCount(){return count;}
    int getKey(){return key;}
    bool hasRightChild();
    bool hasLeftChild();
    Tree& operator=(const Tree&);
    bool operator==(const Tree&);
    
    void setCount(int);
    void setLeftChild(Tree*);
    void setRightChild(Tree*);
};

Tree::Tree(int a,int B)/>{
    val = a;
    key = b;
    count = 1;
    leftChild = 0;
    rightChild = 0;
}

Tree::Tree(int tree_val, int tree_key, int tree_count, Tree* tree_leftChild, Tree* tree_rightChild){
    val = tree_val;
    key = tree_key;
    count = tree_count;
    leftChild = tree_leftChild;
    rightChild = tree_rightChild;
}

bool Tree::hasLeftChild(){
    if(leftChild == 0){
        return false;
    }else{
        return true;
    }
}

bool Tree::hasRightChild(){
    if(rightChild == 0){
        return false;
    }else{
        return true;
    }
}

void Tree::setCount(int a){
    count = a;
}

void Tree::setLeftChild(Tree *t){
    leftChild = t;
}

void Tree::setRightChild(Tree *t){
    rightChild = t;
}

bool Tree::operator==(const Tree& node){
    if(this == node){
        return true;
    }else{
        return false;
    }
}


Tree& Tree::operator=(const Tree& node){
    
    if(this.key == node.key){
        return *this;
    }
    
    val = node.val;
    key = node.key;
    count = node.count;
    leftChild = node.leftChild;
    rightChild = node.rightChild;
    
    return *this;
}



void walk_tree(Tree node){
    //if node is a leaf, print its info
    if(!node.hasLeftChild() && !node.hasRightChild()){
        //print its info
        cout << "Node Value: " << node.getVal() << endl;
        cout << "Node Key: " << node.getKey() << endl;
        cout << "Count: " << node.getCount() << endl;
        cout << endl;
    }else if(node.hasLeftChild()){
        walk_tree(node.getLeftChild());
    }else if(node.hasRightChild()){
        walk_tree(node.getRightChild());
    }
}



int main() {
    int firstInt;
    
    cin >> firstInt;
    
    Tree root(firstInt,0);
    
    for(int i = 1; i < 9; i++){
        int input;
        cin >> input;
        Tree* curNode = &root;
        bool placed = false;
        while(!placed){
            curNode->setCount(curNode->getCount()+1);
            if(input <= curNode->getVal()){
                if(curNode->hasLeftChild()){
                    *curNode = curNode->getLeftChild();
                }else{
                    Tree nextNode(input,i);
                    Tree* nextNode_ptr = &nextNode;
                    curNode->setLeftChild(nextNode_ptr);
                    placed = true;
                }
            }else if(input > curNode->getVal()){
                if(curNode->hasRightChild()){
                    *curNode = curNode->getRightChild();
                }else{
                    Tree nextNode(input, i);
                    Tree* nextNode_ptr = &nextNode;
                    curNode->setRightChild(nextNode_ptr);
                    placed = true;
                }
            }
        }
    }
    
    return 0;
}



Thanks again for all the help, It's really appreciated.
Was This Post Helpful? 0
  • +
  • -

#6 eker676  Icon User is offline

  • Software Engineer
  • member icon

Reputation: 378
  • View blog
  • Posts: 1,833
  • Joined: 18-April 09

Re: Binary Search Tree in C++ -- Pointer issues?

Posted 28 October 2013 - 03:22 PM

Oops, for the assignment I did that wrong. You want to compare the pointers.
if(this == &node) {
  return *this;
}

// rest of the assignment stuff here



Just a general C++ tip. You have a lot of code that looks like this:
if(leftChild == 0){
    return false;
}else{
    return true;
}



Take advantage of the fact that pointers can be implicitly converted into boolean values and write it like this:
// If leftChild == 0, will return false. Returns true otherwise.
return leftChild;

Was This Post Helpful? 0
  • +
  • -

#7 jc310xc  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 15
  • Joined: 14-January 11

Re: Binary Search Tree in C++ -- Pointer issues?

Posted 28 October 2013 - 06:08 PM

Alright. So Everything related with the class is working.

However, I'm still having issues with actually placing the values in the tree.

My loop for placing nodes in the tree is now as follows:

for(int i = 1; i < 9; i++){
        int input;
        cin >> input;
        Tree* curNode = &root;
        bool placed = false;
        while(!placed){
            curNode->setCount(curNode->getCount()+1);
            cout << "Key: " << curNode->getKey() << endl;
            cout << "Val: " << curNode->getVal() << endl;
            Tree* leftChild = curNode->getLeftChild();
            Tree* rightChild = curNode->getRightChild();
            cout << "address of leftChild: " << &leftChild << endl;
            cout << "address of rightChild: " << &rightChild << endl;
            if(input <= curNode->getVal()){
                if(curNode->hasLeftChild()){
                    curNode = curNode->getLeftChild();
                }else{
                    Tree nextNode(input,i);
                    cout << "address of new Node: " << &nextNode << endl;
                    curNode->setLeftChild(nextNode);
                    placed = true;
                }
            }else if(input > curNode->getVal()){
                if(curNode->hasRightChild()){
                    curNode = curNode->getRightChild();
                }else{
                    Tree nextNode(input, i);
                    curNode->setRightChild(nextNode);
                    placed = true;
                }
            }
        }
    }



curiously, if I remove the statement "cout << "address of new node: " << &nextNode << endl;", the program trips up and I get null pointer issues. Otherwise it seems to run fine, but seems to be looping infinitely at the end.

My input is as follows:

"10 7 2 15 4 13 5 6 0"

10 is previously taken in the program as the root node.
Was This Post Helpful? 0
  • +
  • -

#8 eker676  Icon User is offline

  • Software Engineer
  • member icon

Reputation: 378
  • View blog
  • Posts: 1,833
  • Joined: 18-April 09

Re: Binary Search Tree in C++ -- Pointer issues?

Posted 28 October 2013 - 06:14 PM

Line 18-20, you are using the value of the Node incorrectly and will end up with a dangling pointer.
Tree nextNode(input,i);
cout << "address of new Node: " << &nextNode << endl;
curNode->setLeftChild(nextNode);


setLeftChild should take a pointer, not a normal value. As soon as that block leaves scope the nextNode will be destroyed and you will be left with a dangling pointer (if you had setLeftChild accept a pointer.)

Allocate new nodes on the heap and add a pointer to the tree. Then clean up all the heap allocations in the destructor.
Tree* newNode = new Tree(input, i);
curNode->setLeftChild(newNode);

Was This Post Helpful? 1
  • +
  • -

#9 jc310xc  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 15
  • Joined: 14-January 11

Re: Binary Search Tree in C++ -- Pointer issues?

Posted 28 October 2013 - 08:46 PM

it works perfectly! thank you so much!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1