Tree example

[Drew]

In the example in the tutorial Binary Trees, Is int key_value; Is this the number being compared to in the functions pointed to by the left and right pointers? key_value is the variable holding the numbers being manipulated. Is this statement correct?

struct node
{
int key_value;
node *left;
node *right;
};

class btree
{
node *root;
btree();
~btree();
void destroy_tree(node *leaf);
void insert(int key, node *leaf);
node *search(int key, node *leaf);
public:
void insert(int key);
node *search(int key);
void destroy_tree();
};


void btree::insert(int key, node *leaf)
{
if(key< leaf->key_value)
{
if(leaf->left!=NULL)
insert(key, leaf->left);
else
{
leaf->left=new node;
leaf->left->key_value=key;
leaf->left->left=NULL; //Sets the left child of the child node to null
leaf->left->right=NULL; //Sets the right child of the child node to null
}
}
else if(key>=leaf->key_value)
{
if(leaf->right!=NULL)
insert(key, leaf->right);
else
{
leaf->right=new node;
leaf->right->key_value=key;
leaf->right->left=NULL; //Sets the left child of the child node to null
leaf->right->right=NULL; //Sets the right child of the child node to null
}
}
}

I do not understand what the int key value is doing? Why do you need it? What value does it have?

[zen]

'int key' is the value being inserted into the tree. If it is less than the key_value of the node it's being compared to then it will be inserted to the left, or if it's greater than to the right. If there is already a node in the position it is to be inserted then the insert function is called recursively so that the value can be inserted to the left or right of the appropriate child (and so on until there is a NULL child for it to be inserted into).

As the nodes are private in you class you cannot access they key_value directly so you have to pass an integer (int key) into an access function (insert) so that this value (int key) can be assigned to a node's key_value.