Binary Trees

Trees are a very beautiful data structure. I like them because they are easily implemented by using recursivity. The very basic implementation of trees have some pros and cons, like the way you insert nodes (leafs) in the trees may affect drastically the search timing (like in the case of all nodes to the right or all to the left). The deeper a tree is the more time consuming the search will be. By now you may have infered that in binary trees all branches have only two sub-branches, one to the right and one to the left. Trees are mostly used for optimizing searches. Some trees like Red-Black trees optimize themselves during node insertion, but to uderstand those advanced topics first you need to understand the basic Binary Trees.

This is my approach to Binary Tree data structure construction:

struct tree_leaf {
    int key;
    struct tree_leaf *left;
    struct tree_leaf *right;
};

typedef struct tree_leaf leaf;

One of the small things about trees and recursivity is that the order of calling the recursive functions change a lot the way the algorithm behaves, see this example:

void print_tree(leaf *root)
{
  if(root)
  {     
      print_tree(root->left);
      printf("%d\n",root->key);
      print_tree(root->right);     
  } 
}

The way I put these three instructions will have as a result first printing everything to the left of the root, then the root, then everything to the right. By changing the printf instruction to the beginning will print the root first, then everything to the left and then right, and so on. You need to have in mind what kind of search you want to do in your tree before defining the position of these lines, and also very important is how you did the insertion in the tree.

Here is the rest of the implementation:

static leaf *create_leaf(int key)
{
    leaf *temp=NULL;
    temp = (leaf*)malloc(sizeof(leaf));
    temp->key=0;
    temp->right=NULL;
    temp->left=NULL;
    return temp;   
}

void insert(leaf **root, int key)
{
    if(!(*root))
    {
        printf("posición vacia. Crea nodo e inserta %d\n",key);   
        *root = create_leaf(key);
        (*root)->key = key;
    }
    else if(key <= (*root)->key)
    {
        printf("ve a la izquierda\n");   
        insert(&(*root)->left,key);
    }
    else if(key > (*root)->key)
    {
        printf("ve a la derecha\n");   
        insert(&(*root)->right,key);
    }
    else
        //if you replace the "<=" by "<" in the second condition you can avoid inserting duplicates
        //if a duplicate (colision) happens then log that we've found one.
        printf("colisión\n");
    printf("termina inserción\n");   
}

static leaf *search_leaf(leaf *root, int key)
{
  if(root)
  {
      if(key==root->key)
      {
          return root;
      }
      else if(key<root->key)
      {
          return search_leaf(root->left,key);
      }
      else
      {
          return search_leaf(root->right,key);
      }
  }
  else return 0;
}

void print_tree(leaf *root)
{
  if(root)
  {     
      print_tree(root->left);
      printf("%d\n",root->key);
      print_tree(root->right);     
  } 
}

int search(leaf *root, int key)
{
    leaf *temp=search_leaf(root,key);
    if(temp)
        return temp->key;
    return 0;
}

void delete_tree(leaf **root)
{
  if((*root))
  {
      delete_tree(&(*root)->left);
      delete_tree(&(*root)->right);
      free( *root );
  }
}