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

 
Output of file : TREE.DOC contained in archive : LLIST102.ZIP


Documentation for TREE.C

Written Sept. 1986, Bob DuBose

TREE.C is a C file designed to support tree-creating and traversing
procedures. At present, it only handles binary trees (that is, trees with at
most two children at each branch). Future versions will be designed to handle
trees whose sibling size may be any number, not just restricted to two nodes
per branch. However, for many applications, a simple binary tree is
sufficient. The individual node structure as defined in TREE.H consists of
four elements. Three are pointers to other node structures; two to the two
children of this node (these are set to NULL if the node is a leaf node), and
the third points to the parent of this node (while is set to NULL if the node
is the root of the tree). The last pointer is a pointer to a structure of type
T_DATA, which holds the actual data for that particular node. Since the node
structure is defined using pointers only, the structure "T_DATA" need not yet
be defined for the file to compile properly. The individual program that the
user creates will need to define the structure, however. The node structure
was deliberately designed using only pointers to be as flexible as possible for
different uses.


Functions in TREE.C: All source code designed to use the tree functions should
include the statement "#include " to declare the functions in the
TREE.OBJ file.

MALLOC(x), CALLOC(x)

these macros are the same as the malloc() and calloc() functions, except
that they will automatically provide the sizeof operator to the function
call.


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


usage: Given the pointers to a data element and a parent node, inst_tree()
calls MALLOC to allocate memory for a node. If there is memory
available, the function returns a pointer to the new node, otherwise
it returns NULL. If successful, the function links the new node to
the parent, but not vice-versa. The new node's left and right
children are set to NULL.



NODE_T *inst_tree(data)
struct T_DATA *data;

Usage: inst_tree() calls inst_node() with the parent pointer set to NULL,
and returns (if successful) the return value of inst_node(), a
pointer to the new node.




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

Usage: The function attempts to add a child to the parent. It calls
inst_node() to do so. If there is memory available, add_child()
checks if the left child of the parent is NULL. If so, the child
becomes the parent's new left child. If not, the right child node is
checked for NULL, and, if so, the child is linked there. If the
parent already has two children, FALSE (0) is returned. If there is
not any available memory, the parent will remain unchanged.



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

Usage: This is similar to the add_child() function, however if the parent is
"full", it traverses down the left children of the parent and adds a
new child to the leftmost leaf node. The function does not check for
memory availability, and always returns TRUE.



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

Usage: This function connects a parent to a child. Both nodes already must
exist. If there is no room for the child to be connected to the
parent, the function returns FALSE, otherwise it returns TRUE. Both
the child is connected to the parent, and the parent is connected to
the child.



NODE_T *find_root(t_node)
NODE_T *t_node;

Usage: The function traverses backwards up the linked list of nodes until it
reaches the root (parent == NULL). It returns the a pointer to that
node.



BOOLEAN is_leaf(t_node)
NODE_T *t_node;

Usage: This function returns TRUE if the node has no children, FALSE
otherwise.



BOOLEAN is_root(t_node)
NODE_T *t_node;

Usage: This function returns TRUE if the node has no parent, FALSE
otherwise.




NODE TRAVERSING FUNCTIONS:
preorder() The calling parameters are identical for the three
inorder() functions, so only for the preorder function is
postorder() a description given.


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

Usage: This function performs a preorder traversal of the tree, starting at
the given node (it treats the node argument as a root). The argument
"process" is a pointer to a function that the user must define. The
only restriction on this "process" is that it must be of type void
and can have as it's argument only a pointer to a node structure.
The process function typically acts on the data that the node stores
(in the T_DATA structure, accessed via the N_DATA pointer), although
it may be something as simple as a function that counts the nodes as
they are traversed. I decided to code the function in this manner
(using a pointer to a process function), because that seemed to be
the best way of allowing the user to manipulate the tree in any
nonpredefined manner. In this way, the preorder function can be
called with different pointers to different functions, and it will
not be limited to always calling some prenamed external function
(if it were not this way, there could be one and only one function
that the programmer could have his or her preorder function implement
throughout the whole program). Preorder returns nothing.


Any suggestions, comments, helpful criticisms, etc. (especially pats on
the back) would be appreciated. These programs are now public domain;
it's my hope that maybe someone else out there may find them useful!
A future update (and we may be talking WAY in the future...) will be able
to accomodate trees with any number of sibling nodes, not just two. Also,
if anyone has any good functions to use on trees that I forgot, add 'em
in. (It'd be nice if you send me a letter, too, so I could put them in
permanently into my sources.) Finally, the ideas for these routines came
from the book Advanced C: Programming Techniques, available in paperback
for about $19.95 or so. The MALLOC, CALLOC, and node names in particular
are from that. Oh, yes... I almost forgot... The TREE.OBJ file was
created with a LATTICE C compiler, version 3.10.

Bob DuBose, Fido 100/10 (McDonnell-Douglas Bullentin board).



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

  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/