Category : C Source Code
Archive   : TALGOL.ZIP
Filename : TCBTREE.C
tcbtree.c
binary tree processing functions:
insert_binary() - inserts a new node in tree
search_binary() - searches for a specified occurrence of a key in the tree.
It assumes that the tree ALLOWS DUPLICATE KEYS.
If no match found returns 0.
sort_to_array() - visits nodes of trees and copies them into an array.
This operation supplies you with an ascending ordered array.
If there are more nodes in tree than space in array then the
surplus nodes are NOT included in array.
You can detect this when the returned value is
larger than the constant MAX_TREE_NODES.
delete_bintree() - deletes a node specified by the supplied key
and the occurrence number. This function returns a pointer to the
new root of the tree. (Uses recursion to locate node to delete).
remove_tree() - Removes an ENTIRE tree and de-allocates the memory space occupied
by tree nodes.
**/
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define MAX_TREE_NODES 100
#define STRING_SIZE 40
typedef struct treestruct *treeptr;
struct treedatarec
{
char key[STRING_SIZE];
/*..... put other fields here ... */
};
/*** basic tree node ***/
struct treestruct
{
struct treedatarec treedata;
treeptr left,right;
};
typedef struct treedatarec treerecarray;
/* internal functions */
void traverse_tree(treeptr root, treerecarray *sortx, int *count);
/** main functions **/
int insert_bintree(treeptr *root,struct treedatarec item);
int search_bintree(treeptr root,struct treedatarec item, int freq);
int sort_to_array(treeptr root, treerecarray *sortx);
treeptr delete_bintree(treeptr root,struct treedatarec item, int freq);
int remove_tree(treeptr *root);
int insert_bintree(treeptr *root,struct treedatarec item)
/*** inserts the data key item in a binary tree.
if the key is inserted returns 0 (otherwise 1). ***/
{
int cmpresult;
if (*root != NULL)
{
cmpresult = strcmp(item.key,(*root)->treedata.key);
/*** NOTE :
the following may be uncommented to enable this routine to
avoid inserting duplicate keys
if (cmpresult == 0) exit(1);
***/
if (cmpresult > 0) /** insert in right subtree **/
insert_bintree(&(*root)->right,item);
else /** insert in left subtree **/
insert_bintree(&(*root)->left,item);
}
else
{ /** create new root **/
*root = (treeptr) malloc(sizeof(struct treestruct));
if (*root == NULL) return 1; /** memeory allocation error **/
(*root)->treedata = item; /** store node data **/
(*root)->left = NULL;
(*root)->right = NULL;
}
return 0; /** element inserted **/
}
int search_bintree(treeptr root,struct treedatarec item, int freq)
/*** searches for a specified number of a given key in a binary tree.
returns number of occurences ***/
{
int count, cmpresult;
count = 0;
/*** traverse the full tree ***/
while ((root != NULL) && (count < freq))
{
cmpresult = strcmp(item.key,root->treedata.key);
if (cmpresult > 0)
/** goto right subtree **/
root = root->right;
else if (cmpresult < 0)
/** goto left subtree **/
root = root->left;
else
{
count++; /** key found **/
root = root->left;
}
}
return count; /** number of keys found **/
}
void traverse_tree(treeptr root, treerecarray *sortx, int *count)
/*** local function used to traverse a tree.
called by sort_to_array(). ***/
{
if (root != NULL)
{
traverse_tree(root->left,sortx,count); /** visit left subtree **/
(*count)++;
printf("\nCount is : %d", *count);
if (*count <= MAX_TREE_NODES)
strcpy(sortx[*count].key, root->treedata.key);
traverse_tree(root->right,sortx,count); /** visit right subtree **/
root = root->left;
}
}
int sort_to_array(treeptr root, treerecarray *sortx)
/*** traverses a tree and places the tree data in a sorted array ***/
{
int count;
if (root != NULL)
{
count = -1;
traverse_tree(root,sortx,&count);
return count; /** number of nodes found **/
}
return -1;
}
treeptr delete_bintree(treeptr root,struct treedatarec item, int freq)
/*** deletes a node in a binary tree ***/
{
treeptr t1,t12;
int ch;
if (root == NULL) return NULL; /** element cannot be deleted **/
ch = strcmp(root->treedata.key,item.key); /** compare elements **/
if ((ch == 0) && (--freq == 0))
{ /** element found **/
/** delete terminal node **/
if ((root->right == NULL) && (root->left == NULL))
{
free(root);
return NULL;
} /** delete node with right child only **/
else if (root->left == NULL)
{
t1 = root->right; /** make right child new root **/
free(root);
return t1;
} /** delete node with left child only **/
else if (root->right == NULL)
{
t1 = root->left; /** make left child new root **/
free(root);
return t1;
}
else
{ /** delete node with left and right child **/
t1 = root->right; /** make right node new root **/
t12 = root->right;
while (t12->left != NULL)
/** find new root's leftmost node **/
t12 = t12->left;
t12->left = root->left; /** link-in left node of old root **/
free(root);
return t1;
}
}
else if (ch == 0) root->left = delete_bintree(root->left,item,freq);
else if (ch > 0) root->left = delete_bintree(root->left,item,freq);
else root->right = delete_bintree(root->right,item,freq);
return root;
}
int remove_tree(treeptr *root)
/*** removes a binary tree by deallocating its memory spacce ***/
{
int delete_this_node;
delete_this_node = FALSE;
if (((*root)->left == NULL) && ((*root)->right == NULL))
delete_this_node = TRUE;
else
{
if ((*root)->left == NULL)
if (remove_tree(&(*root)->left))
{
free((*root)->left);
(*root)->left = NULL;
}
if ((*root)->right == NULL)
if (remove_tree(&(*root)->right))
{
free((*root)->right);
(*root)->right = NULL;
}
if (((*root)->left == NULL) && ((*root)->right == NULL))
delete_this_node = TRUE;
}
return delete_this_node; /** return status of tree removal **/
}
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/