Binary tree C++ basics

Question

void BinarySearchTree::insert(int d)
{
    tree_node* t = new tree_node;
    tree_node* parent;
    t->data = d;
    t->left = NULL;
    t->right = NULL;
    parent = NULL;

    // is this a new tree?
    if(isEmpty()) root = t;
    else
    {
        //Note: ALL insertions are as leaf nodes
        tree_node* curr;
        curr = root;
        // Find the Node's parent
        while(curr)
        {
            parent = curr;
            if(t->data > curr->data) curr = curr->right;
            else curr = curr->left;
        }

        if(t->data < parent->data)
           parent->left = t;
        else
           parent->right = t;
    }
}

Questions:

Why do I need to allocate memory for tree_node* t; using new but not for tree_node* parent;?
What exactly is tree_node* what does it look like in memory and what does it do?
Can someone explain to me the -> operator and how it works?

tree_node* t is being used as a new node, the one that will be inserted, while parent is just a temporary storage variable used to store parents nodes during processing. The -> operator is an accessor so that you can get data stored within the object. As for what tree_node actually is? That's probably a custom data type made specifically for this tree implementation. You'd have to look through your source for it. — TheZ
– TheZ, Commented Jul 26, 2012 at 23:05
The -> means the same thing as . in other languages; it references members of an object. So parent->right means the right member in the parent object. — Robert Harvey
– Robert Harvey, Commented Jul 26, 2012 at 23:08
@RobertHarvey well... parent is not an object, but a pointer. — Luchian Grigore
– Luchian Grigore, Commented Jul 26, 2012 at 23:11
It points to an object, right? Otherwise, being merely a pointer, it wouldn't have any members. :) — Robert Harvey
– Robert Harvey, Commented Jul 26, 2012 at 23:13
@Undermine2k: Sounds a lot like you need to learn the basics of c/c++. That would pretty much answer most of your questions. cplusplus.com has decent enough tutorials — Keldon Alleyne
– Keldon Alleyne, Commented Jul 26, 2012 at 23:16

Luchian Grigore · Accepted Answer · 2012-07-26 23:11:01Z

Why do I need to allocate memory for tree_node* t; using new but not for tree_node* parent;?

You don't need to, but it's part of the logic. t represents the new node you're inserting, so you need to create it first (which is done by the new). You don't allocate memory for parent because it will refer to an already existing node:

 while(curr)
 {
    parent = curr;
    //...

What exactly is tree_node* what does it look like in memory and what does it do?

No way to tell (it should be defined somewhere), but it's probably a structure like so:

struct tree_node
{
    tree_node* left;
    tree_node* right;
    int data;
}

Can someone explain to me the -> operator and how it works?

It's for accessing object members through a pointer. If you have Class* x, then x->a is equivalent to (*x).a.

Collectives™ on Stack Overflow

Binary tree C++ basics

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related