Link to home
Start Free TrialLog in
Avatar of blaze_wk
blaze_wk

asked on

Binary Search

#include <stdio.h>
#include <stdlib.h>

/* Small program to explore using binary trees.
   The program takes an array filled with random numbers
   and inserts the numbers into a binary tree.
   The program then prints the contents of the tree in
   key order. It should print -
   0 1 2 3 4 5 6 7 8 9
   The program then free's up the tree.

   I can't seem to find the error of this program..
*/

struct treeRecord
{
   int key;
   struct treeRecord *left, *right;
};

typedef struct treeRecord treeNode;

void insertArrayInTree(treeNode **root, int array[], int size);
void insertElementInTree(treeNode **root, int number);
void printTree(treeNode *start);
void freeTree(treeNode **start);
treeNode* newNode(int number);

int main()
{
   int array[] = { 6, 3, 8, 1, 5, 2, 9, 7, 4, 0 };
   treeNode *root = NULL;

   insertArrayInTree(&root, array,10);
   printTree(root);
   printf("\n");
   freeTree(&root);

   return 0;
}


void insertArrayInTree(treeNode **root, int array[], int size)
{
   /* insert elements of array into correct position in binary tree */

   int i;

   for (i=0; i<size; i++)
   {
      insertElementInTree(root, array[i]);
   }
}

void insertElementInTree(treeNode **root, int number)
{
   treeNode *temp = *root;

if (*temp != NULL)
{
      if (number < (*root)->key)
         insertElementInTree(&(temp->left), number);
      else
         insertElementInTree(&(temp->right), number);
}
else
{
   *root = newNode(number);
}
}

void printTree(treeNode *root)
{
   /* print the contents of the tree in order */

   while (root != NULL)
   {
      printf(" %d", root->key);
      root = root->right;
   }
}

void freeTree(treeNode **root)
{
   /* free up memory allocated to binary tree */
   treeNode *temp = *root;

   if (temp != NULL)
   {
      if (temp->left != NULL) freeTree(&temp->left);
      if (temp->right != NULL) freeTree(&temp->right);
      free(temp);
      *root = NULL;
   }
}
treeNode* newNode(int number)
{
   /* dynamicaly allocate memory for a treeNode
      make sure it is initialised correctly
   */

   treeNode *temp;

   temp = (treeNode *) malloc(sizeof(treeNode));
   if (temp == NULL)
   {
      printf("WARNING - Memory allocation error\n");
      exit(EXIT_FAILURE);
   }
   temp->key = number;
   temp->left = NULL;

   return temp;
}
ASKER CERTIFIED SOLUTION
Avatar of van_dy
van_dy

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of van_dy
van_dy

in case i was not clear, in my last post, in  function void insertElementInTree(treeNode **root, int number)

>> if (temp != NULL)            //not *root
should be
     if(temp != NULL)            //not *temp
Hi,

Is that (*root)->key or root->key? Does that make any difference?
>>Is that (*root)->key or root->key? Does that make any difference?
It should be (*root)->key in insertElementInTree(treeNode **root, int number). (*root) will be a pointer to treenode,
so u access its key memeber by (*root)->key