tree.h

linked list linked list tree struc

/*
** -----------------------------------------------------------
** CMPT 332/422 University of Saskatchewan
** 2004/2005
** Assignment 1
** File: BBS_Tree.h
** Authors: some unnamed students. Simplified by D. Makaroff
** Modified from former Tree.h 
** January 11, 2005
** -----------------------------------------------------------
**
*/

#define TREELEN 100
#define NODELEN 10000

/*
** Data types
*/
typedef struct _TREEHEAD TREE, *TREEPTR;
typedef struct _NODE NODE;
typedef void * TITEM;
typedef int COMPARATOR(TITEM, TITEM);
typedef void ITEMFREE(TITEM);
typedef int ORDERTYPE(TITEM, TITEM);


/*
** Tree node
*/
struct _NODE {
  TITEM item;
  NODE *prev;
  NODE *next;
  NODE *parent;
  NODE *left;
  NODE *right;
  int height;
};

/*
** Tree header
*/
struct _TREEHEAD {
  NODE *first_node;
  NODE *curr_node;
  NODE *last_node;
  NODE *root_node;
  int size;
};


/* Create a new tree    */
TREE* TreeCreate(void);

/* Return the number of elements in a tree */
int TreeSize(TREEPTR);

/* Set current node to first node */
TITEM TreeFirst(TREEPTR);

/* Set current node to last node */
TITEM TreeLast(TREEPTR);

/* Set current node to next node */
TITEM TreeNext(TREEPTR);

/* Set current node to previous node */
TITEM TreePrev(TREEPTR);

/* Return data stored in current node */
TITEM TreeCurr(TREEPTR);

/* Insert a new node after current node */
int TreeAdd(TREEPTR, TITEM, ORDERTYPE);


/* Remove current node */
TITEM TreeRemove(TREEPTR);

/* Destroy a list */
void TreeFree(TREEPTR, ITEMFREE);

/* Find an element in the list */
TITEM TreeSearch(TREEPTR, COMPARATOR, void *comparison_arg);

/* Find an element in the list by its key*/
TITEM TreeKeySearch(TREEPTR, COMPARATOR, void *comparison_arg);


/*
** ------------- [extras] ------------
*/

/* Set current node to root node of the tree*/
TITEM TreeRoot(TREEPTR);

/* Set current node to the parent node of it*/
TITEM TreeParent(TREEPTR);

/* Set current node to the left node of it*/
TITEM TreeLeft(TREEPTR);

/* Set current node to the right node of it*/
TITEM TreeRight(TREEPTR);

/*
** --------------- Optional Error codes -------------
*/
#define TE_SUCCESS        0     /* No errors */
#define TE_OUTOFHEADS     1     /* Out of memory for headers */
#define TE_OUTOFNODES     2     /* Out of memory for nodes */
#define TE_BADARGS        3     /* Invalid arguments */
#define TE_TREE_EMPTY     4     /* Tree is empty */
#define TE_NOTFOUND       5     /* TreeSearch found no elements */