treei

treeimp.c

#include <stdlib.h>
#include "tree.h"
/*
  *The type of trees.
 */
//typedef struct treeiter treeiter_t;

/*
struct treeiter
{
  tree_t *tree;
};*/
//Creates a new root for a new store_inorder
tree_t *tree_create(cmpfunc_t cmpfunc) {
  tree_t *node = malloc(sizeof(tree_t));

    node -> data   = NULL;
    node -> height = 1;
    node -> left   = NULL;
    node -> right  = NULL;
    node -> numitems = 2;
    node ->cmpfunc = cmpfunc;
  	return node;
}

//Int compare function
int max(int a, int b)
{
    return a > b ? a : b;
}
//gets height of tree
int height(tree_t *node)
{
    return node ? node -> height : 0;
}
//updates height
void recalc(tree_t *node)
{
    node -> height = 1 + max(height(node -> left), height(node -> right));
}
//rotates subtree right
tree_t *rotate_right(tree_t *node)
{
    tree_t *q = node -> left;

    node -> left = q -> right;
    q -> right = node;

    recalc(node);
    recalc(q);

    return q;
}
//rotates subtree left
tree_t *rotate_left(tree_t *node)
{
    tree_t *q = node -> right;
    node -> right = q -> left;
    q -> left = node;

    recalc(node);
    recalc(q);

    return q;
}
//balances the tree so that the max balance factor is no more than 1
tree_t *balance(tree_t *node)
{
    recalc(node);

    if ( height(node -> left) - height(node -> right) == 2 )
    {
        if ( height(node -> left -> right) > height(node -> left -> left) )
            node -> left = rotate_left(node -> left);
        return rotate_right(node);
    }
    else if ( height(node -> right) - height(node -> left) == 2 )
    {
        if ( height(node -> right -> left) > height(node -> right -> right) )
            node -> right = rotate_right(node -> right);
        return rotate_left(node);
    }

    return node;
}
//stores the traversal order of the tree in an array
void store_inorder(tree_t *tree, int inorder[], int *index_ptr)
{
    if (tree == NULL)
        return;
    int *p;

    /*first recur on left child */
    store_inorder(tree->left, inorder, index_ptr);
    p = tree->data;
    inorder[*index_ptr] = *p;
    (*index_ptr)++;  // increase index for next entry

    /*now recur on right child */
    store_inorder(tree->right, inorder, index_ptr);
}
/*
  *Destroys the given tree.  Subsequently accessing the tree
  *will lead to undefined behavior.
 */
void tree_destroy(tree_t *node)
{
  if ( !node )
    return;
//destroying the tree recursively
tree_destroy(node -> left);
tree_destroy(node -> right);
free(node);
}

/*
  *Returns the size (cardinality) of the given tree.
 */
int tree_size(tree_t *tree){
  return tree->numitems;
}

/*
  *Adds the given element to the given tree.
 */
tree_t *node_add(tree_t *node, void *data) {
  if ( !node )
      return tree_create(data);
	//conditionals to determine where to put the data
  if ( data < node -> data )
      node -> left = node_add(node -> left, data);
  else if ( data > node -> data )
      node -> right = node_add(node -> right, data);
  else
      node -> data = data;
	node->numitems++;

  return balance(node);
}

/*
  *Returns 1 if the given element is contained in
  *the given tree, 0 otherwise.
 */
int tree_contains(tree_t *node, void *data){
	if( node == NULL )
			return 0;
	if( data < node->data )
			return tree_contains(node->left, data );
	else if( data > node->data )
			return tree_contains(node->right, data );
	else
			return 1;
}

//coverts a sorted array to a balanced binary tree
tree_t *sortedArrayToBST(int arr[], int start, int end)
{
    if (start > end)
      return NULL;
    cmpfunc_t cmpfunc;

    //get the middle element and make it root
    arr[0] = (start + end)/2;
    tree_t *root = tree_create(cmpfunc);
    root->data = arr;

    //recursively construct the left subtree and make it
       //left child of root
    root->left =  sortedArrayToBST(arr, start, arr[0]-1);

    //recursively construct the right subtree and make it
       //right child of root
    root->right = sortedArrayToBST(arr, arr[0]+1, end);

    return root;
}
//function to remove duplicate elements in an array
int remove_dup(int arr[], int m)
{
  int i, j, k;

  for (i = 0; i < m; i++) {
      for (j = i + 1; j < m;) {
         if (arr[j] == arr[i]) {
            for (k = j; k < m; k++) {
               arr[k] = arr[k + 1];
            }
            m--;
         } else
            j++;
      }
   }
}
//counts the number of intersections in two arrays
int *intersc_count(int arr1[], int arr2[], int m, int n)
{
  int i = 0, j = 0, k = 0, s = 0;
  int *node;
  node = &s;
  // Traverse through both arrays
  while (i < m && j < n)
  {
      // nodeick the smaler element and nodeut it in mergedArr
      if (arr1[i] < arr2[j])
      {
          i++;
      }
      else if (arr2[j] < arr1[i])
      {
          j++;
      }
      else if (arr1[i] == arr2[j])
      {
       printf("arr1[%d]\n", arr1[i]);
       s++;
       i++;
       j++;
     }
  }
  return node;
}

//find similiar elements in two arrays and puts them in a third array
int *intersc_init(int arr1[], int arr2[], int m, int n)
{
  int i = 0, j = 0, k = 0, s = 0;
  int *size;
  size = intersc_count(arr1, arr2, m, n);
  printf("\nS: %d\n", *size);

  int *arr3 = malloc(sizeof(*size));
  if(arr3 == NULL)
    return NULL;

  while (i < m && j < n)
  {
      if (arr1[i] < arr2[j])
      {
          i++;
      }
      else if (arr2[j] < arr1[i])
      {
          j++;
      }
      else if (arr1[i] == arr2[j])
      {
       arr3[s] = arr1[i];
       s++;
       i++;
       j++;
     }
  }

  return arr3;
}

//counts the number of differences in two arrays
int *difference_count(int arr1[], int arr2[], int m, int n)
{
  int i = 0, j = 0, s = 0;
  int *p;
  p = &s;
  // Traverse through both arrays
	for(int i = 0; i < m; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(arr1[i]!=arr2[j])
			{
				++j;
				++i;
				++*p;
			}
		}
	}
	printf("\ndiff_size: %d\n", *p);
	return p;
}

//all elements of tree a that is not in tree b, are put in an array
int *difference_init(int arr1[], int arr2[], int m, int n)
{
  int i = 0, j = 0, k = 0, s = 0;
  int *size;
  size = difference_count(arr1, arr2, m, n);
	printf("\ndiff_size: %d\n", *size);
	int *arr3 = malloc(sizeof(*size));
	if(arr3 == NULL)
		return 0;

	for(int i = 0; i < m; i++)
	{
			for(int j = 0; j < n; j++)
			{
				if(arr1[i]!=arr2[j])
				{
					arr3[s] = arr1[i];
					++i;
					++j;
					++s;
				}
			}
	}
	return arr3;
}
//merges two arrays, combined with the duplicate delete
//the union of two arrays can be found
int *merge(int arr1[], int arr2[], int m, int n)
{
    //mergedArr[] is going to contain result
    int *mergedArr = malloc(sizeof(int[m + n]));
    if(mergedArr == NULL)
      return NULL;
    int i = 0, j = 0, k = 0;

    //traverse through both arrays
    while (i < m && j < n)
    {
        //pick the smaler element and put it in mergedArr
        if (arr1[i] < arr2[j])
        {
            mergedArr[k] = arr1[i];
            i++;
        }
        else
        {
            mergedArr[k] = arr2[j];
            j++;
        }
        k++;
    }
    //if there are more elements in first array
while (i < m)
{
    mergedArr[k] = arr1[i];
    i++; k++;
}

//if there are more elements in second array
while (j < n)
{
    mergedArr[k] = arr2[j];
    j++; k++;
}
remove_dup(mergedArr, m+n);

return mergedArr;
}

/*
 *Returns the union of the two given trees; the returned
 *tree contains all elements that are contained in either
 *a or b.
 */
//converts trees to arrays, merges the arrays, then converts
//the merged array back into a tree
tree_t *tree_union(tree_t *a, tree_t *b, int m, int n)
{
	//store inorder traversal of first tree in arr1[]
  int arr1[m];
  int i = 0;
  store_inorder(a, arr1, &i);

  //store inorder traversal of second tree in arr2[]
  int arr2[n];
  int j = 0;
  store_inorder(b, arr2, &j);

  // Merge the two sorted array into one
  int *mergedArr = merge(arr1, arr2, m, n);

  //construct a tree from the merged array and return root of the tree
  return sortedArrayToBST (mergedArr, 0, m+n-1);

}

/*
  *Returns the intersection of the two given trees; the
  *returned tree contains all elements that are contained
  *in both a and b.
 */
tree_t *tree_intersection(tree_t *a, tree_t *b, int m, int n)
{
	//store inorder traversal of first tree in arr1[]
  int arr1[m];
  int i = 0;
  store_inorder(a, arr1, &i);

  //store inorder traversal of second tree in arr2[]
  int arr2[n];
  int j = 0;
  store_inorder(b, arr2, &j);

	//calls the intersection function
  int *arr3 = intersc_init(arr1, arr2, m, n);

	//gets the size of the intersection count, so memory isn't wasted
  int *size;
  size = intersc_count(arr1, arr2, m, n);

  return sortedArrayToBST (arr3, 0, *size-1);
}

/*
 *Returns the tree difference of the two given trees; the
 *returned tree contains all elements that are contained
 *in a and not in b.
 */
tree_t *tree_difference(tree_t *a, tree_t *b, int m, int n)
{
	//store inorder traversal of first tree in arr1[]
  int arr1[m];
  int i = 0;
  store_inorder(a, arr1, &i);

  //store inorder traversal of second tree in arr2[]
  int arr2[n];
  int j = 0;
  store_inorder(b, arr2, &j);

  int *arr3 = difference_init(arr1, arr2, m, n);

  int *size;
  size = difference_count(arr1, arr2, m, n);

  return sortedArrayToBST (arr3, 0, *size-1);
}
/*
 *Returns a copy of the given tree.
 */
 //copies the contents of one tree to another tree
tree_t *tree_copy(tree_t *tree, int m, int n)
{
  int arr1[m], arr2[m];
  int b = 0, i;
  store_inorder(tree, arr1, &b);
  for (i = 0; i < m; i++)
   arr2[i] = arr1[i];

  return sortedArrayToBST (arr2, 0, m-1);
}

void go_left(tree_t *root)
{
  if(!root)
    return;
  go_left(root->left);
}

void go_right(tree_t *root)
{
  if(!root)
    return;
  go_left(root->right);
}

void preorder(tree_t *root){
  if(!root)
    return;
  printf("%d\t",root->data);
  preorder(root->left);
  preorder(root->right);
}
//function for printing the in-order of tree
void inorder_print(tree_t *root){
  if(!root)
    return;
  inorder_print(root->left);
  printf("%d\t",root->data);
  inorder_print(root->right);
}
void inorder(tree_t *root){
  if(!root)
    return;
  inorder(root->left);
  inorder(root->right);
}

void postorder(tree_t *root)
{
    if(root == NULL)
        return;
    else {
        postorder(root ->left);
        postorder(root ->right);
        printf("%d\t",root ->data);
    }
}