<![CDATA[/*
* Tree node structure
*/
struct tnode
{
struct tnode *left, *right;
TDATUM d;
};
/*
* Queue data structure used by tbreadhfirst
*/
#define QDATUM struct tnode *
#include "queue.c"
/*
* Function to be called by the tree traversal functions.
*
* Parameters:
*
* n Pointer to a node (obviously).
*
* param: Value provided by the traversal function's caller.
*
* depth: Recursion depth indicator. Allows the function to
* determine how many levels the node being processed is
* below the root node. Can be used, for example, for
* selecting the proper indentation width when tdepthfirst
* or tbreadthfirst are used to print a tree dump
* to the screen.
*/
typedef void TWORKER(struct tnode *n, int param, int depth);
/*
* tinsert: insert a new item into the tree.
*
* Parameters:
*
* n Address of a pointer to a node.
*
* d Item to be inserted.
*
* Return values:
*
* non-NULL The item has been inserted.
*
* NULL The datum provided could not be inserted, either due
* to TKEY collision (the tree already contains another
* item with which the same TKEY is associated), or due
* to insufficient memory.
*/
struct tnode *
tinsert(struct tnode **n, TDATUM d)
{
if (!(*n)) {
if (!((*n) = malloc(sizeof(struct tnode)))) {
return NULL;
}
(*n)->left = (*n)->right = NULL;
(*n)->d = d;
return *n;
}
if (TKEY(d) < TKEY((*n)->d)) {
return tinsert(&(*n)->left, d);
}
if (TKEY(d) > TKEY((*n)->d)) {
return tinsert(&(*n)->right, d);
}
return NULL;
}
/*
* tfindhighest: remove and return the tree's highest-ranking item.
*
* Parameters:
*
* n Address of a pointer to a node.
*
* Return values:
*
* non-NULL The tree did contain at least one item; the return
* value points to what previously was the tree's
* highest-ranking element.
*
* NULL No item could be removed as the tree is empty.
*/
struct tnode *
tfindhighest(struct tnode **n)
{
struct tnode *tmp = *n;
if (!(*n)) {
return NULL;
}
if ((*n)->right) {
return tfindhighest(&(*n)->right);
}
*n = (*n)->left;
return tmp;
}
/*
* tfindlowest: remove and return the tree's lowest-ranking item.
*
* See tfindhighest for the details.
*/
struct tnode *
tfindlowest(struct tnode **n)
{
struct tnode *tmp = *n;
if (!(*n)) {
return NULL;
}
if ((*n)->left) {
return tfindlowest(&(*n)->left);
}
*n = (*n)->right;
return tmp;
}
/*
* tremove: remove an item from the tree.
*
* Parameters:
*
* n Address of a pointer to a node.
*
* key TKEY of item to be removed.
*
* Return values:
*
* 1 The item has been removed.
*
* 0 The tree does not contain an item yielding the
* TKEY value provided by the caller.
*/
int
tremove(struct tnode **n, int key)
{
struct tnode *trash = *n;
if (!(*n)) {
return 0;
}
if (key < TKEY((*n)->d)) {
return tremove(&(*n)->left, key);
}
if (key > TKEY((*n)->d)) {
return tremove(&(*n)->right, key);
}
*n = NULL;
if (trash->left) {
*n = tfindhighest(&(trash->left));
}
else if (trash->right) {
*n = tfindlowest(&(trash->right));
}
if (*n) {
(*n)->left = trash->left;
(*n)->right = trash->right;
}
free(trash);
return 1;
}
/*
* taccess: retrieve the datum corresponding to a given TKEY.
*
* Parameters:
*
* n Pointer to the root node.
*
* key TKEY of item to be accessed.
*
* Return values:
*
* non-NULL An item yielding the TKEY provided has been found,
* the return value points to the TDATUM attached to it.
*
* NULL The item could not be found.
*/
TDATUM *
taccess(struct tnode *n, int key)
{
if (!n) {
return NULL;
}
if (key < TKEY(n->d)) {
return taccess(n->left, key);
}
if (key > TKEY(n->d)) {
return taccess(n->right, key);
}
return &(n->d);
}
/*
* tdepthfirst: depth-first tree traversal.
*
* Parameters:
*
* n Pointer to the root node.
*
* f Worker function to be called for every node.
*
* param Additional parameter to be passed to the
* worker function.
*
* depth Recursion depth indicator. Allows the worker function
* to determine how many levels the node being processed
* is below the root node. Can be used, for example,
* for selecting the proper indentation width when
* tdepthfirst is used to print a tree dump to the screen.
*
* Most of the time, you will want to call tdepthfirst
* with a "depth" value of zero.
*/
void
tdepthfirst(struct tnode *n, TWORKER *f, int param, int depth)
{
if (!n) return;
tdepthfirst(n->left, f, param, depth + 1);
(*f)(n, param, depth);
tdepthfirst(n->right, f, param, depth + 1);
}
/*
* tbreadthfirst: breadth-first tree traversal.
*
* See tdepthfirst for details.
*/
void
tbreadthfirst(struct tnode *n, TWORKER *f, int param)
{
struct queue q;
if (!n) return;
qinit(&q);
qinsert(&q, n);
while (qremove(&q, &n)) {
(*f)(n, param, 0);
if (n->left) qinsert(&q, n->left);
if (n->right) qinsert(&q, n->right);
}
}
<p>
]]>
About Me
Back
Home Mail to me