tree_removers.c

linked list linked list tree struc

/*
 * Wei Cui
 * 981503
 * wec924 */
 
#include <stdio.h>
#include <tree.h>

TREE *freeTreePtr;    /* next available tree */
NODE *freeNodePtr;    /* next available node */


/* the function is defined in tree_adders.c doing the necessary rotation job */
void _rotate_if_necessary(TREEPTR, NODE *);

/* tree removers : */


TITEM _sampleRemove(NODE *replace)
{
  if (!replace->right)
  {
    if (replace->parent)
    {
      if (replace->parent->left == replace)   replace->parent->left=replace->left;
      else   replace->parent->right=replace->left;
    }
    if (replace->left)   replace->left->parent=replace->parent;
  }
  else
  {
    if (replace->parent)
    {
      if (replace->parent->left == replace)   replace->parent->left=replace->right;
      else   replace->parent->right=replace->right;
    }
    replace->right->parent=replace->parent;
  }
  if (replace->next)   replace->next->prev=replace->prev;  
  if (replace->prev)   replace->prev->next=replace->next;
  replace->height = 0;
  replace->parent = NULL;
  replace->left = NULL;
  replace->right = NULL;
  replace->prev = NULL;
  replace->next = freeNodePtr;
  freeNodePtr = replace;
  return replace->item;
}


TITEM TreeRemove(TREEPTR mytree)
{
  NODE *delNode, *replace, *cpNode;
  TITEM delItem;
  if ((!mytree)||(!mytree->curr_node))
  {
    return NULL;
  }
  else
  {
    delNode = mytree->curr_node;
    delItem = delNode->item;
    cpNode = delNode->parent;
    if ((delNode->right) && (delNode->left)) /* the delNode has both subtrees */
    {
 /* choose the next node as the replacement of deletation */
      replace = delNode->next;
      cpNode = replace->parent;
      delNode->item = _sampleRemove(replace);
    }
    else                            /* the delNode doesn't have both subtrees */
    {
      if (delNode->next)   mytree->curr_node=delNode->next;
      else   mytree->curr_node=delNode->prev;
      if (mytree->root_node == delNode)   mytree->root_node = mytree->curr_node;
      delItem = _sampleRemove(delNode);
    }
    if (mytree->first_node == delNode)   mytree->first_node=mytree->curr_node;
    if (mytree->last_node == delNode)   mytree->last_node=mytree->curr_node;
    while (cpNode)
    {  
      _rotate_if_necessary(mytree, cpNode);
      cpNode = cpNode->parent;
    }
    mytree->size--;
    freeNodePtr->item = NULL;
    return delItem;
  }
}



void TreeFree(TREEPTR mytree, void itemFree(void *))
{
  NODE *tempNode;
  TITEM tempItem;
  if (mytree)
  {
    mytree->curr_node = mytree->first_node;
    while ( mytree->curr_node != NULL )
    {
      tempItem = mytree->curr_node->item;
      (*itemFree)(tempItem);
      /* call the pointer routine to deal with each item. */
      tempNode = mytree->curr_node->next;
      mytree->curr_node->next = freeNodePtr;
      freeNodePtr = mytree->curr_node;
      mytree->curr_node = tempNode;
    }
    mytree->first_node = NULL;
    mytree->last_node = (NODE *)freeTreePtr;
    mytree->root_node = NULL;
    mytree->size = 0;                       /* mytree left empty */
    freeTreePtr = mytree;                   /* but the space is available to be reused */
  }
  else printf("The tree doesn't exist!!\n");
}