/* 040903 for OSN & Graphics
no treeHeader
a combi of iter and rec
iter iff only 1 branch is used (insert, delete, get and set)
rec if both branches are used (size, print, process)
*/
#include <stdio.h>
#include <stdlib.h>
#define randomCapital() ((char)(('A') + rand() % ('Z' - 'A' + 1)))
typedef enum {FALSE, TRUE} bool;
/* KEY DATA AND ELEMENT */
typedef char keyType; /* user defined */
typedef int dataType; /* user defined but not used in this program */
typedef dataType* dataPtr;
typedef struct eltType* eltPtr;
typedef struct eltType {
keyType key;
dataPtr data;
} eltType;
eltPtr createElt(keyType k, dataPtr pd); // constructor
eltPtr createElt(keyType k, dataPtr pd) {
eltPtr p = (eltPtr)malloc(sizeof(eltType));
p->key = k; p->data = pd;
return(p);
}
eltPtr destroyElt(eltPtr pe); // destructor
eltPtr destroyElt(eltPtr pe) {
free(pe);
return(pe = NULL);
}
void printKey(eltPtr pe); // output
void printKey(eltPtr pe) {printf("%c", pe->key);}
void printNull();
void printNull() {printf("%c", '*');}
/* TREENODE AND TREE */
typedef struct treeNode* treePtr;
typedef struct treeNode {
eltPtr elt;
treePtr lhs;
treePtr rhs;
int freq; // used for multiple insert
} treeNode;
typedef treePtr tree;
treePtr createNode(eltPtr pe); // constructor
treePtr createNode(eltPtr pe) {
treePtr p = (treePtr)malloc(sizeof(treeNode));
p->elt = pe;
p->lhs = p->rhs = NULL;
p->freq = 1;
return(p);
}
treePtr destroyNode(treePtr t); // destructor
treePtr destroyNode(treePtr t) {
t->elt = destroyElt(t->elt);
free(t);
return(t = NULL);
}
/* FUNCTION PROTOTYPES AND DOCUMENTATION */
tree createTree (); // constructor
tree destroyTree (tree t); // destructor
bool isEmptyTree (tree t);
int theSizeOf (tree t);
tree insert (eltPtr pe, tree t);
tree delete (keyType k, tree t);
void printTree (tree t);
/* DEFINITION OF THE FUNCTIONS */
tree createTree() {
return(NULL);
}
bool isEmptyTree(tree t) {
return(!t);
}
int theSizeOf(tree t) {
return((!t) ? (0)
: (1 + theSizeOf(t->lhs) + theSizeOf(t->rhs)));
}
tree destroyTree(tree t) { // post order is important!!
if (t) {
t->lhs = destroyTree(t->lhs);
t->rhs = destroyTree(t->rhs);
printf("%c", t->elt->key); // decoration to follow the process
t = destroyNode(t);
}
return(t);
}
tree insert(eltPtr pe, tree t) {
treePtr *c = &t ;
while ((*c) && (pe->key != (*c)->elt->key))
c = ((pe->key < (*c)->elt->key) ? &(*c)->lhs : &(*c)->rhs);
if (*c)
(*c)->freq++; // multiple insert
else
*c = createNode(pe);
return(t);
}
void swap(eltPtr *e1, eltPtr *e2); // aux function in transform
void swap(eltPtr *e1, eltPtr *e2) {
eltPtr e = *e1; *e1 = *e2; *e2 = e;
}
treePtr* lmn(treePtr* t) ;
treePtr* lmn(treePtr* t) {
treePtr *c = t;
while ((*c)->lhs) c = &(*c)->lhs;
return(c);
}
treePtr* rmn(treePtr* t) ;
treePtr* rmn(treePtr* t) {
treePtr *c = t;
while ((*c)->rhs) c = &(*c)->rhs;
return(c);
}
treePtr* transform(treePtr* t) ; // aux function in delete
treePtr* transform(treePtr* t) {
treePtr q = *t;
int sL = theSizeOf(q->lhs),
sR = theSizeOf(q->rhs);
t = (sL < sR) ? lmn(&(*t)->rhs) : rmn(&(*t)->lhs);
swap(&(*t)->elt, &q->elt);
return(t);
}
bool hasTwoChildren(treePtr t);
bool hasTwoChildren(treePtr t) {return(t->lhs && t->rhs);}
treePtr del(treePtr t); // delete case less than 2 children
treePtr del(treePtr t) {
treePtr q = t;
t = (q->lhs) ? q->lhs : q->rhs;
free(q->elt); free(q);
return(t);
}
tree delete(keyType k, tree t) ;
tree delete(keyType k, tree t) { // OK I believe
treePtr *c = &t;
while ((*c) && (k != (*c)->elt->key))
c = ((k < (*c)->elt->key) ? &(*c)->lhs : &(*c)->rhs); // 1
if (*c) { // 2
if (hasTwoChildren(*c))
c = transform(c); // 3
*c = del(*c); // 4
}
return(t);
}
// 1: now c is the address of the pointer to the node to be deleted if any
// 2: yes! a node that contains an element with key k exists
// 3: transform from two to less than two children
// 4: now the node has less than two children and is deleted
void printTree(tree t) {
if (t) {
printTree(t->lhs);
printKey(t->elt);
printTree(t->rhs);
}
else
printNull();
}
void changeKeys(tree t, keyType f(treePtr)) ; // HOF
void changeKeys(tree t, keyType f(treePtr)) {
if (t) {
changeKeys(t->lhs, f);
t->elt->key = f(t);
changeKeys(t->rhs, f);
}
}
keyType capToSmall(treePtr t) ;
keyType capToSmall(treePtr t) {return(t->elt->key + 32);}
keyType smallToCap(treePtr t) ;
keyType smallToCap(treePtr t) {return(t->elt->key - 32);}
void printKeysAndFreqs(tree t, void f(treePtr)) ; // another HOF
void printKeysAndFreqs(tree t, void f(treePtr)) {
if (t) {
printKeysAndFreqs(t->lhs, f);
f(t);
printKeysAndFreqs(t->rhs, f);
}
}
void printKeyAndFreq(treePtr t) ;
void printKeyAndFreq(treePtr t) {
printf("%2c[%2d]\t", t->elt->key, t->freq);
if ((t->elt->key - 'A') % 5 == 0) printf("\n");
}
int sumOfFreqs(tree t, int f(treePtr)) ; // yet and another HOF
int sumOfFreqs(tree t, int f(treePtr)) {
return((!t) ? 0 : sumOfFreqs(t->lhs, f) + f(t) + sumOfFreqs(t->rhs, f));
}
int getFreq(treePtr t) ;
int getFreq(treePtr t) {return(t->freq);}
int main(void) {
int i;
char c;
tree t = createTree();
srand(time(NULL));
printf("insert random capitals 26*32 = 832 times\n");
for (i = 0; i < 26*32; i++)
t = insert(createElt(randomCapital(), NULL), t);
printf("the size of the tree = %d\n", theSizeOf(t));
printf("the keys are\n");
printTree(t); printf("\n");
printf("the keys and frequencies are\n");
printKeysAndFreqs(t, printKeyAndFreq);
printf("sum of freqs = %d\n\n", sumOfFreqs(t, getFreq));
printf("change keys from capital to small letter\n");
changeKeys(t, capToSmall);
printf("the new keys are\n");
printTree(t); printf("\n");
printf("change keys back to capital letter\n");
changeKeys(t, smallToCap);
printf("the keys are\n");
printTree(t); printf("\n");
printf("delete letters D .. P\n");
for (c = 'D'; c <= 'P'; c++)
t = delete(c, t);
printTree(t); printf("\n");
printf("delete 13 random letters: ");
for (i = 0; i < 13; i++) {
c = randomCapital();
printf("%c", c);
t = delete(c, t);
}
printf("\n"); printTree(t); printf("\n");
printf("release the tree: ");
t = destroyTree(t);
printf("\n"); printTree(t); printf("\n");
printf("size of tree? %d\n", theSizeOf(t));
}