Category : C Source Code
Archive   : LLIST102.ZIP
Filename : TREE.C

 
Output of file : TREE.C contained in archive : LLIST102.ZIP
/**

tree.c -- file with tree functions

**/

#include
#include

extern struct NODE *inst_node( struct T_DATA *data,
struct NODE *parent );
extern struct NODE *inst_tree( struct T_DATA *data );
extern int add_child( struct NODE *parent, struct T_DATA *data );
extern int add_l_child( struct NODE *parent, struct T_DATA *data );
extern int adopt( struct NODE *child, struct NODE *parent );
extern struct NODE *find_root( struct NODE *t_node );
extern int is_leaf( struct NODE *t_node );
extern int is_root( struct NODE *t_node );
extern void preorder( struct NODE *t_node,
void ( cdecl *process )( struct NODE * ));
extern void inorder( struct NODE *t_node,
void ( cdecl *process )( struct NODE * ));
extern void postorder( struct NODE *t_node,
void ( cdecl *process )( struct NODE * ));

#define BOOLEAN int
#define TRUE 1
#define FALSE 0

/*
* Define NULL if it's not already defined

#ifndef NULL
#if SPTR
#define NULL 0
#else
#define NULL 0L
#endif
#endif

#ifndef NARGS
extern char *malloc(unsigned);
extern char *calloc(unsigned,unsigned);
#else
extern char *malloc();
extern char *calloc();
#endif
*/

#define MALLOC(x) ((x *) malloc(sizeof(x)))
#define CALLOC(n,x) ((x *) calloc(n,sizeof(x)))

struct NODE
{ struct T_DATA *N_DATA;
struct NODE *L_CHILD;
struct NODE *R_CHILD;
struct NODE *PARENT;
};

typedef struct NODE NODE_T;


/********************
* instantiate node *
********************/

NODE_T *inst_node(data,parent)
struct T_DATA *data;
NODE_T *parent;

{ NODE_T *new;

if (new = MALLOC(NODE_T)) /* allocate space */
{ new->N_DATA = data; /* and fill in the variables */
new->PARENT = parent;
new->L_CHILD = new->R_CHILD = NULL;
}

return(new); /* pointer points to new node */
}


/********************
* instantiate tree *
********************/

NODE_T *inst_tree(data)
struct T_DATA *data;

{ NODE_T *inst_node(struct T_DATA *, NODE_T *);

return(inst_node(data,NULL)); /* the parent of the root is NULL */
}


/****************************
* add child to parent node *
****************************/

BOOLEAN add_child(parent,data)
NODE_T *parent;
struct T_DATA *data;

{ NODE_T *inst_node(struct T_DATA *, NODE_T *);

if (parent->L_CHILD == NULL) /* if open space, */
parent->L_CHILD = inst_node(data,parent); /* add the child */
else
if (parent->R_CHILD == NULL) /* if open space, */
parent->R_CHILD = inst_node(data,parent); /* add the child */
else
return(FALSE); /* no open space on this node */

return(TRUE); /* say we were successful */
}


/*********************************
* add left child to parent node *
*********************************/

BOOLEAN add_l_child(parent,data)
NODE_T *parent;
struct T_DATA *data;

{ NODE_T *inst_node(struct T_DATA *, NODE_T *);

if (parent->L_CHILD == NULL) /* if open space, */
parent->L_CHILD = inst_node(data,parent); /* add the child */
else
if (parent->R_CHILD == NULL) /* if open space, */
parent->R_CHILD = inst_node(data,parent); /* add the child */
else
add_l_child(parent->L_CHILD, data); /* call again one node down */

return(TRUE); /* say we were successful */
}


/*******************************
* connect a parent to a child *
*******************************/

BOOLEAN adopt(child,parent)
NODE_T *child, *parent;

{ if (child->PARENT == NULL) /* if child is an orphan */
if (parent->L_CHILD == NULL) /* test if open left child */
parent->L_CHILD = child; /* and link in the node */
else
if (parent->R_CHILD == NULL) /* test if open right child */
parent->R_CHILD = child; /* and link in the node */
else
return(FALSE); /* no openings ... */

child->PARENT = parent; /* finally, connect the umbilicus */

return(TRUE);
}


/*********************
* find root of tree *
*********************/

NODE_T *find_root(t_node)
NODE_T *t_node;

{ /* look for NULL parent */
while (t_node->PARENT)
t_node = t_node->PARENT;

/* now return it! */
return(t_node);
}


/*******************************
* determine if node is a leaf *
*******************************/

BOOLEAN is_leaf(t_node)
NODE_T *t_node;

{ if ((t_node->L_CHILD == NULL) && (t_node->R_CHILD == NULL))
return(TRUE);
else
return(FALSE);
}


/*******************************
* determine if node is a root *
*******************************/

BOOLEAN is_root(t_node)
NODE_T *t_node;

{ if (t_node->PARENT) /* if it has a parent, it can't */
return(FALSE); /* be a root node */
else
return(TRUE);
}


/******************************
* perform preorder traversal *
******************************/

void preorder(t_node, process)
NODE_T *t_node;
void (*process)(NODE_T *);

{ if (t_node == NULL)
return;

/* process the root first... */
(*process)(t_node);

/* and now the rest */
preorder(t_node->L_CHILD, process); /* preorder the left lines */
preorder(t_node->R_CHILD, process); /* preorder the right lines */

return;
}


/*****************************
* perform inorder traversal *
*****************************/

void inorder(t_node, process)
NODE_T *t_node;
void (*process)(NODE_T *);

{ if (t_node == NULL)
return;

inorder(t_node->L_CHILD, process); /* inorder the left children */
(*process)(t_node); /* then the node itself */
inorder(t_node->R_CHILD, process); /* then the right children */

return;
}


/*******************************
* perform postorder traversal *
*******************************/

void postorder(t_node, process)
NODE_T *t_node;
void (*process)(NODE_T *);

{ if (t_node == NULL)
return;

postorder(t_node->L_CHILD, process); /* left children first */
postorder(t_node->R_CHILD, process); /* then right children */
(*process)(t_node); /* then the node itself */

return;
}


  3 Responses to “Category : C Source Code
Archive   : LLIST102.ZIP
Filename : TREE.C

  1. Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!

  2. This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.

  3. But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/