Category : Files from Magazines
Archive   : CUJ9201.ZIP
Filename : 1001075A
* Traversal of multiple binary trees
*/
#include
#include
#include
#define BIGINT (~(1 << ((8*sizeof(int))-1))) /* maximum integer */
#define NNODES 25 /* the number of nodes per tree */
#define NTREES 10 /* the number of binary trees to traverse */
/* binary tree node definition */
typedef struct node {
struct node *left; /* left sub-tree */
struct node *right; /* right sub-tree */
int key; /* current node value */
} NODE;
/***********************************************************************
* the following section is the single threaded example
***********************************************************************/
#ifdef SINGLE_THREAD
/* stack frame definition */
typedef struct frame {
struct node *data; /* the node being stacked */
struct frame *next; /* the next stack entry */
} FRAME;
/* push a tree node onto the stack */
void Push(FRAME **stackp, NODE *treep) {
FRAME *temp;
assert(treep != NULL);
temp = malloc(sizeof(FRAME));
assert(temp != NULL);
temp->data = treep;
temp->next = *stackp;
(*stackp) = temp;
}
/* get the top data item from the stack (without popping) */
int Top(FRAME *stackp) {
NODE *temp;
assert(stackp != NULL);
temp = stackp->data;
return(temp->key);
}
/* print the lowest value of all N trees */
void DisplayLowest(FRAME *stackp[], int *lowest) {
int current;
int topvalue;
int temp=BIGINT;
int i;
/* for each tree in the list... */
for (i=0; i < NTREES; i++) {
/* if the tree has not been completely traversed, */
if (stackp[i] != NULL) {
/* get the current key of this tree */
topvalue = Top(stackp[i]);
/* compare the current key with the other trees */
if (topvalue < temp) {
/* save the current tree number and its key */
current = i;
temp = topvalue;
}
}
}
printf("key = %d\n", temp);
*lowest = current;
}
/* removes and returns the top entry from the stack */
NODE *Pop(FRAME **stackp) {
FRAME *temp;
NODE *data;
temp = *stackp;
*stackp = (*stackp)->next;
data = temp->data;
free(temp);
return(data);
}
/* traverse the right sub-tree */
void TraverseRightSub(FRAME **stackp) {
NODE *temp;
FRAME *sframe;
/* find the right sub-tree of the current node */
temp = Pop(stackp);
temp = temp->right;
/* traverse the sub tree as far left as possible */
while (temp != NULL) {
Push(stackp, temp);
temp = temp->left;
}
}
/* determine if there are unvisited nodes */
int StacksExist(FRAME *stackp[]) {
int i;
for (i = 0; i < NTREES; i++){
if (stackp[i] != NULL)
return(1);
}
return(0);
}
void MergeTrees(NODE *treep[]) {
FRAME *stackp[NTREES];
int i;
/* preload all stacks */
for (i = 0; i < NTREES; i++) {
stackp[i] = NULL;
while (treep[i] != NULL) {
Push(&stackp[i], treep[i]);
treep[i] = treep[i]->left;
}
}
do {
DisplayLowest(stackp, &i);
TraverseRightSub(&stackp[i]);
} while(StacksExist(stackp));
}
/***********************************************************************
* the following section is the multi threaded example
***********************************************************************/
#else
#include
/* print the contents of a node (wait until it is the lowest key) */
void PrintNode(NODE *tree) {
static int CurrentKey = BIGINT;
/* wait until this node contains the lowest key value */
do {
if (CurrentKey > tree->key)
CurrentKey = tree->key;
MtCYield();
} while (CurrentKey != tree->key);
/* reinitialize the current key */
CurrentKey = BIGINT;
printf("key = %d\n", tree->key);
}
/* recursively visit the nodes in a tree */
void PrintTree(NODE *tree) {
if (tree != NULL) {
PrintTree(tree->left);
PrintNode(tree);
PrintTree(tree->right);
}
}
/* traverse multiple binary trees */
void MergeTrees(NODE **trees) {
int i;
/* create a thread for each tree... */
for (i = 0; i < NTREES; i++) {
MtCCoroutine(PrintTree(&trees[i]));
}
}
#endif
/* recursively add a node to the tree */
void AddKey(NODE **treep, int key) {
if ((*treep) == NULL) {
(*treep) = malloc(sizeof(NODE));
assert(*treep != NULL);
(*treep)->left = NULL;
(*treep)->right = NULL;
(*treep)->key = key;
} else {
if (key < (*treep)->key) {
AddKey(&((*treep)->left), key);
} else {
AddKey(&((*treep)->right), key);
}
}
}
/* build a tree of NNODES random keys */
void BuildTree(NODE **treep) {
int i;
for (i = 0; i < NNODES; i++) {
AddKey(treep, rand());
}
}
void main() {
NODE *trees[NTREES];
int i;
/* randomly build the trees */
for (i = 0; i < NTREES; i++) {
trees[i] = NULL;
BuildTree(&trees[i]);
}
/* traverse the trees as a single tree */
MergeTrees(trees);
}
Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!
This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.
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/