home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power-Programmierung
/
CD1.mdf
/
magazine
/
drdobbs
/
1988
/
03
/
mathews
/
mathews.ls2
< prev
Wrap
Text File
|
1979-12-31
|
6KB
|
219 lines
/* 001 24-Apr-87 tbtree.c
Functions to create and traverse a threaded binary tree.
James Mathews
Blue Sky Software
172 Manor Drive
Absecon, NJ 08201
This code is hereby placed into the public domain.
*/
#include <stdio.h>
#include "tbtree.h"
#ifdef LINT_ARGS /* setup for Microsoft C V 4.0 */
#include <malloc.h>
TREE_NODE *talloc();
void add2tree(char *);
TREE_NODE *linsert(TREE_NODE *);
TREE_NODE *rinsert(TREE_NODE *);
TREE_NODE *inorder_succ(TREE_NODE *);
TREE_NODE *inorder_pred(TREE_NODE *);
#else
char *malloc();
void add2tree();
TREE_NODE *talloc(), *linsert(), *rinsert();
TREE_NODE *inorder_succ(), *indorder_pred();
#endif
/* define the root node for the threaded tree */
TREE_NODE root = { "|", 0, RBIT, &root, &root };
/**********************************************************
A D D 2 T R E E
**********************************************************/
void
add2tree(word) /* add given word to the B-tree */
char *word;
{
register int cmp;
register TREE_NODE *tp = &root;
/* search tree to find word, add it if not there */
while ((cmp = stricmp(word,tp->word)) != 0) {
if (cmp < 0) /* not equal, look to the left? */
if (tp->flags & LBIT) /* is there a left child? */
tp = tp->lchild; /* yes, go look at it */
else {
tp = linsert(tp); /* no left child, make one */
break;
}
else /* not left, look right */
if (tp->flags & RBIT) /* is there a right child? */
tp = tp->rchild; /* yes, look it over */
else {
tp = rinsert(tp); /* no right child, make one */
break;
}
}
if (cmp == 0) /* did we find the word? */
tp->usage++; /* if so bump usage count */
else { /* must have added new word */
tp->word = word; /* point it to the word */
tp->usage = 1; /* new word in town */
}
}
/**********************************************************
R I N S E R T
**********************************************************/
static TREE_NODE *
rinsert(tp) /* insert new node as right child of tp */
register TREE_NODE *tp;
{
register TREE_NODE *new;
if (new = talloc()) { /* alloc new entry */
new->rchild = tp->rchild; /* new gets what tp had */
new->flags = tp->flags & RBIT; /* as a right child */
new->lchild = tp; /* lchild is thread to tp */
tp->rchild = new; /* new is rchild of tp */
tp->flags |= RBIT; /* real node, not thread */
}
return(new);
}
/**********************************************************
L I N S E R T
**********************************************************/
static TREE_NODE *
linsert(tp) /* insert new node as left child of tp */
register TREE_NODE *tp;
{
register TREE_NODE *new;
if (new = talloc()) { /* alloc new entry */
new->lchild = tp->lchild; /* new gets what tp had */
new->flags = tp->flags & LBIT; /* as a left child */
new->rchild = tp; /* rchild is thread to tp */
tp->lchild = new; /* new is lchild of tp */
tp->flags |= LBIT; /* real node, not thread */
}
return(new);
}
/**********************************************************
T A L L O C
**********************************************************/
static TREE_NODE *
talloc() { /* allocate a TREE_NODE */
#define NODES_PER_ALLOC (50)
static TREE_NODE *tp;
static int tidx = NODES_PER_ALLOC;
/* this routine allocates space for TREE_NODE nodes. It
exists to cut down on the number of calls to malloc(). */
if (tidx < NODES_PER_ALLOC) /* free nodes from last alloc? */
return(&tp[tidx++]); /* yes, return the next one */
/* allocate another block of TREE_NODE nodes */
tp = (TREE_NODE *) malloc(sizeof(TREE_NODE) * NODES_PER_ALLOC);
if (tp == NULL) {
printf("\nOut of memory in talloc()\n");
exit();
}
tidx = 1; /* return # 1 next time */
return(tp); /* return # 0 this time */
}
/**********************************************************
I N O R D E R _ S U C C
**********************************************************/
TREE_NODE *
inorder_succ(tp) /* return in-order successor of tp */
register TREE_NODE *tp;
{
register TREE_NODE *next;
/* if the right child is a thread, it's the successor node */
next = tp->rchild;
/* but if the right child is a real node, the successor is
left-most child of the right child */
if (tp->flags & RBIT) /* real right child? */
while (next->flags & LBIT) /* find left-most */
next = next->lchild; /* child of that */
return(next); /* return successor */
}
/**********************************************************
I N O R D E R _ P R E D
**********************************************************/
TREE_NODE *
inorder_pred(tp) /* return in-order predecessor of tp */
register TREE_NODE *tp;
{
register TREE_NODE *prev;
/* if the left child is a thread, it's the predecessor */
prev = tp->lchild;
/* but if the left child is a real node, the predecessor is
right-most child of the left child */
if (tp->flags & LBIT) /* real left child? */
while (prev->flags & RBIT) /* find right-most */
prev = prev->rchild; /* child of that */
return(prev); /* return predecessor */
}