cursor.c

/* Simple Binary Tree operations using Cursors!*/

typedef int PtrToNode
typedef PtrToNode List;
typedef PtrToNode Position;


void InitializeCursorBinTree ( void );
int IsBinTreeEmpty( void );
void insertIntoTree(int element);
int deleteFromTree(int element);

struct Node{
 int Elem;
 int LeftTree;
 int RightTree;
};

struct Node CursorBinTree [ SpaceSize ];


voice initializeCursorBinTreeHelper(int, int);

void InitializeCursorBinTree ( void ){
    int i = 1;
    /* first Element acts as head of tree , if Elem == 0 then tree is empty*/
    /* otherwise CursorBinTree[0].Elem points to first element's i*/
    CursorBinTree[0].Elem = 0;
    while (i < (SpaceSize-1)){
      CursorBinTree[i].LeftTree = i+1;
      CursorBinTree[i].RightTree = i+2;
      i = i+2; 
    }
}


struct Node CursorTree[ SpaceSize ];

int isBinTreeEmpty(){
  if (CursorBinTree[0].Elem == 0){
    return 1;
  }
  else{
    return 0;
  }
 }
 
 /*returns 1 if insert successful*/
 /*returns -1 if not enough memory */

 int insertIntoTree(int element){
     int i=0;
     while(i < SpaceSize){
         if (CursorBinTree[i] ==0){
             CursorBinTree[i].Elem = element;
             return 1;
         }
         else{
             if (CursorBinTree[i].Elem > element){
                 if (CursorBinTree.LeftChild != 0){
                     i = CursorBinTree.LeftChild;
                  }
                  else{
                     return -1;
                  }
              }
              else{
                  if (CursorBinTree.RightChild != 0){
                      i = CursorBinTree.RightChild;
                   }
                   else{
                      return -1;
                   }
              }
         }
     }
 }  
 
 /*take a starting index into the tree and find the smallest value*/
 
 int FindMin(int index){
    
  
 }
 
 /*the problem with this way of using the stucture is that get dead rows, that need to be freed somehow*/
 /*returns -1 if element is not in tree. 1 if successful */
 
 
 
 int deleteFromTree(int element, int index){
     if (CursorBinTree[index].Elem ==0){
         return -1
      }
      else{
          if (CursorBinTree[index].Elem == element){
              /*if it has two children*/
              if (CursorBinTree[index].LeftChild !=0 && CursorBinTree[index].RightChild != 0){
                  int tmp = FindMin(CursorBinTree[index].RightChild);
                  deleteFromTree(tmp, index);
                  CursorBinTree[index].Elem = tmp;
                  return 1;
              }    
              else{
                 if(CursorBinTree[index].LeftChild !=0){
                     int LeftIndex = CursorBinTree[index].LeftChild;
                     CursorBinTree[index].Elem = CursorBinTree[LeftIndex ].Elem;
                     CursorBinTree[index].LeftChild = CursorBinTree[LeftIndex ].LeftChild;
                     CursorBinTree[index].RightChild = CursorBinTree[LeftIndex].RightChild;
                     return 1;
                 }
                 if (CursorBinTree[index].RightChild!= 0){
                     int RightIndex = CursorBinTree[index].RightChild;
                     CursorBinTree[index].Elem = CursorBinTree[RightIndex].Elem;
                     CursorBinTree[index].LeftChild = CursorBinTree[RightIndex].LeftChild;
                     CursorBinTree[index].RightChild = CursorBinTree[RightIndex].RightChild;
                     return 1;
                  }
                  CursorBinTree[index].Elem=0;
                  return 1;
         }
         else{
             if(CursorBinTree[index].Elem > element){
                 int next_index = CursorBinTree[index].LeftChild;
                 if (next_index != 0){
                     deleteFromTree(element,next_index );
                 }
                 else{
                     return -1;
                 }
              }     
              else{
                  int next_index = CursorBinTree[index].RightChild;
                  if (next_index != 0){
                      deleteFromTree(element,next_index );   
                   }
                   else{
                  return -1;
              }
         }
     }
 }