0

I'm new to C++ and I normally use Java, so I have a hard time to get into pointers and references. I have to do a variation of binary search tree with inner nodes and leaf nodes (only leafs contain the data).

class Node
    Node *parent;
    Node *left;
    Node *right;
    //other stuff
}

I need to implement operator<< which adds a new node with value to the tree.

//adding a node to tree
void operator<<(int value){
    if(size == 0){
        //stuff
    } else {
        Node* temp = root;
        getLeaf(temp,value);  
        //other magic        
        //temp will be used to append a new node into tree, 
        //so it has to point to the actual node in the tree
        delete temp;
    }        
}

The point of function getLeaf is to find a leaf (may or may not contain the desired value) and store it into temp, which needs to be accessible in the operator<< function.

int getLeaf( Node* temp, int value) const{
    int depth = 0;
    //goes trough all inner nodes until it finds specific leaf
    while(temp->isInner()){
        ++depth;
        if(value < temp->getValue()){ //searched value is smaller
            temp = temp->getLeft(); // to left subtree
            continue;
        } else {
            temp = temp->getRight(); //to rightsubtree
            continue;
        }
     return depth;
}

I am really confused how to do this and what is the right combination of pointers and values. If I set

    Node* temp = root;
    getLeaf(temp,value);

won't root get overridden while traversing the tree in getLeaf function?

Plus I need temp to point to actual node in the tree, so I can append a new node into it.

Could you please explain?

Ziezi
  • 6,375
  • 3
  • 39
  • 49
Filoména Petržlénová
  • 193
  • 1
  • 5
  • 19
  • This question is very specific to your problem, so it's hard to answer in a useful way for anyone else... But I think your `getLeaf` should take a reference to a pointer (`Node*&`, so that the actual value of `temp` can be updated in the original caller code. – Mats Petersson Jan 09 '16 at 23:37
  • (I didn't downvote, but I can see why someone would - your code is also not complete enough to test out to see if we can get it to work) – Mats Petersson Jan 09 '16 at 23:38
  • Thanks, I will try Node*&. My code is not finished yet, so I can't post it here yet :) But what about Node* temp = root; won't the new assigned value to temp in getLeaf have impact on the whole tree? – Filoména Petržlénová Jan 09 '16 at 23:46
  • You said that you know Java. You could see it that way that Java uses pointers for everything which are no basic types like `int` or `double`. If you have a method `void doSomething(MyClass object)` in Java, you can write `void doSomething(MyClass *object)` in C++ and use `->` instead of `.`. If you write `void doSomething(MyClass object)` in C++, you cannot modify the parameter inside the function, just as in Java with basic types. References are some type of syntactic sugar. Thay work like pointers, but you cannot change the target and you must not dereference it to access the value. – JojOatXGME Jan 09 '16 at 23:54
  • @JojOatXGME yes, but if I use void `doSomething(MyClass *object)` as far as I know, the local changes made to object will not be visible outside the method. Please correct me if I'm wrong. – Filoména Petržlénová Jan 10 '16 at 00:04
  • @FiloménaPetržlénová You are wrong. If you write `object->x = 1`, the change will be visible outsite of the function. Just like `void doSomething(MyClass object) { object.x = 1 }` in Java. But if you write `object = null(ptr)` in Java or C++, this change is not visible outsite of the function. The reason is that this changes the pointer and not the value behind it. If you want to change the pointer, you have to write `void doSomething(MyClass &*object)` or `void doSomething(MyClass **object)`. If you use the second one, you have to change some other lines, too. – JojOatXGME Jan 10 '16 at 00:55
  • @FiloménaPetržlénová I did a mistake: `MyClass &*object` seems to be wrong. You have to write `MyClass *&object`, just as written by Mats Peterssoh. – JojOatXGME Jan 10 '16 at 01:16
  • The thing I don't get however: *only leafs contain the data*. – Anirban Sarkar Jan 10 '16 at 07:35
  • @JojOatXGME Thank you, it's much clearer to me now! – Filoména Petržlénová Jan 10 '16 at 09:03
  • @AnirbanSarkar it is a binary search tree where leaves carry the values that were inserted and values in inner nodes guide while traversing the tree. Something similar to [this](http://stackoverflow.com/questions/15163623/balanced-binary-search-tree-store-data-only-in-leaves) – Filoména Petržlénová Jan 10 '16 at 09:03

1 Answers1

2

Migrating from Java to C++ is a bit tough. Migrating from C++ to Java is equally tough. To make things easy you just need to experiment.

In C++, pointers are variables that point to the location of another variable in memory and references are pointers that syntactically behave like the variable whose address is pointed to.

When arguments are passed to a function, the function does NOT receive the original arguments but a copy of them. The work you did is implement the traversal based on the above concepts. So how does it all "magically" work?

Your function: getLeaf(Node *&temp, int value) searches the correct leaf node and assigns it to temp at which insertion is to be performed. temp here is a copy of a reference to the pointer temp(in operator <<). So when the reference temp is assigned to in getLeaf, the pointer temp in operator << it points to is modified.

If I set

Node *temp = root;
getLeaf(temp,value);
won't root get overriden while traversing the tree in getLeaf function?

Note here that temp and root are two different pointers that point to the same variable. The content of the pointers is the same, they aren't and hence root is NOT overridden, when temp is updated.

But there is a problem later on in the code. If you delete temp;, root will also be deleted at the end of insertion as delete deletes the content pointed to by the pointer. Do NOT delete a pointer that is not allocated by a new.

Provide a separate function to free the dynamically allocated memory used by the tree, and call it at the end when you are done experimenting.

Ziezi
  • 6,375
  • 3
  • 39
  • 49
Anirban Sarkar
  • 796
  • 6
  • 14