Arbres binaires et $n$-aires

ll.c

#include"ll.h"

/************************************************/

ll* createLL(int data, ll* next)
{
  ll* link = (ll*)malloc(sizeof(ll));
  if (link == NULL)
    {
      printf("heap overflow...\n");
      exit(0);
    }
  link->data = data;
  link->next = next;
  return link;
}

/************************************************/

void printLL(ll* l)
{
  if (l != NULL)
    {
      printf("%d ", l->data);
      printLL(l->next);
    }
  else
    printf("\n");
}

/************************************************/

void destroyLL(ll* l)
{
  if (l != NULL)
    {
      destroyLL(l->next);
      free(l);
    }
}

/************************************************/

int xInLL(ll* l, int x)
{
  if (l == NULL)
    return 0;
  return x == l->data || xInLL(l->next, x);
}

bTree.c

#include"bTree.h"

/************************************************/

bTree* createBT(bTree* left, int data, bTree* right)
{
  bTree* root = (bTree*)malloc(sizeof(bTree));
  if (root == NULL)
    {
      printf("heap overflow...\n");
      exit(0);
    }
  root->left = left;
  root->data = data;
  root->right = right;
  return root;
}

/************************************************/

void destroyBT(bTree* root)
{
  if (root != NULL)
    {
      destroyBT(root->left);
      destroyBT(root->right);
      free(root);
    }
}

/************************************************/

void printBT(bTree* root)
{
  if (root != NULL)
    {
      printf("("); 
      printBT(root->left);
      printf(", %d, ", root->data); 
      printBT(root->right);
      printf(")"); 
    }
  else
    printf("X");
}

/************************************************/

/*
*/

ll* llOfBTAux(bTree* root, ll* acc)
{
  if (root == NULL)
    return acc;
  return llOfBTAux(root->left, 
		   createLL(root->data, llOfBTAux(root->right, acc))
		   );
}

/************************************************/

ll* llOfBT(bTree* root)
{
  return llOfBTAux(root, NULL);
}

/************************************************/

/*
*/

ll* distinctllOfBTAux(bTree* root, ll* acc)
{
  if (root == NULL)
    return acc;
  if (!xInLL(acc, root->data))
    acc = createLL(root->data, acc);
  return distinctllOfBTAux(root->right, 
			   distinctllOfBTAux(root->left, acc));
}

/************************************************/

ll* distinctllOfBT(bTree* root)
{
  return distinctllOfBTAux(root, NULL);
}

/************************************************/

bTree* randomBT(int depht)
{
  if (depht < 0)
    return NULL;
  return createBT(randomBT(depht - 1), 
		  rand()%MOD, 
		  randomBT(depht - 1));
}

/************************************************/

int heightBT(bTree* root)
{
  if (root == NULL)
    return -1;
  else
    return 1 + 
      MAX(heightBT(root->left), heightBT(root->right));
}

/************************************************/

int sumBT(bTree* root)
{
  if (root == NULL)
    return 0;
  else
    return root->data 
      + sumBT(root->left) + sumBT(root->right);
}

/************************************************/

int findBT(bTree* root, int x)
{
  if (root == NULL)
    return 0;
  return (root->data == x) 
    || findBT(root->left, x) || findBT(root->right, x);
}

/************************************************/

int nbXBT(bTree* root, int x)
{
  if (root == NULL)
    return 0;
  return (root->data == x) 
    + nbXBT(root->left, x) + nbXBT(root->right, x);
}

/************************************************/

bTree* copyBT(bTree* root)
{
  if (root == NULL)
    return NULL;
  return createBT(copyBT(root->left), 
		  root->data, copyBT(root->right));
}

/************************************************/

int isALeaf(bTree* root)
{
  return (root != NULL && 
	  root->left == NULL && root->right == NULL);
}

/************************************************/

int maxBT(bTree* root)
{
  int max;
  if (root == NULL)
    {
      printf("function maxBT can't receive an empty tree\n");
      return -1;
    }
  max = root->data;
  if (root->left != NULL)
    max = MAX (max, maxBT(root->left));
  if (root->right != NULL)
    max = MAX (max, maxBT(root->right));
  return max;
}

/************************************************/

bTree* destroyLeavesBT(bTree* root)
{
  if (root == NULL)
    return NULL;
  if (isALeaf(root))
    {
      destroyBT(root);
      return NULL;
    }
  root->left = destroyLeavesBT(root->left);
  root->right = destroyLeavesBT(root->right);
  return root;
}

/************************************************/

/*
*/

int powInt(int b, int n)
{
  if (n == 0)
    return 1;
  return b * powInt(b, n - 1);
}

/************************************************/

/*
*/

bTree* integersBTAux(int n, int k)
{
  if (n < 0)
    return NULL;
  int root = powInt(2, n) + k;
  return createBT(
		  integersBTAux(n - 1, k), 
		  root,
		  integersBTAux(n - 1, root));
}

/************************************************/

bTree* integersBT(int n)
{
  return integersBTAux(n, 0);
}

/************************************************/

/*
*/

bTree* destroyRootBTAux(bTree* root)
{
  if (root == NULL || isALeaf(root))
    return NULL;
  if (root->left != NULL)
    {
      bTree* leftSon = root->left;
      root->left = destroyRootBTAux(root->left);
      leftSon->right = root->right;
      leftSon->left = root->left;
      return leftSon;
    }
  root->left = root->right;
  root->right = NULL;
  return destroyRootBTAux(root);
}

/************************************************/

bTree* destroyRootBT(bTree* root)
{
  if (root == NULL)
    return NULL;
  bTree* res = destroyRootBTAux(root);
  free(root);
  return res;
}

/************************************************/

int maxDephtBT(bTree* root, int x)
{
  if (root == NULL)
    return -1;
  int k = (root->data == x) ? 0 : -1;
  int rec = MAX(maxDephtBT(root->left, x), maxDephtBT(root->right, x));
  return (rec >= 0) ? rec + 1  : k;
}

/************************************************/

bTree* deleteXBT(bTree* root, int x)
{
  if (root == NULL)
    return NULL;
  root->left = deleteXBT(root->left, x);
  root->right = deleteXBT(root->right, x);
  return (root->data == x) ? destroyRootBT(root) : root;
}

/************************************************/

bTree* purgeBT(bTree* root)
{
  if (root == NULL)
    return NULL;
  root->left = purgeBT(deleteXBT(root->left, root->data));
  root->right = purgeBT(deleteXBT(root->right, root->data));
  return root;
}

/************************************************/

ll* findPathBT(bTree* root, int x)
{
  ll* l;
  if (root == NULL)
    return NULL;
  if (root->data == x)
    return createLL(x, NULL);
  l = findPathBT(root->left, x);
  if (l != NULL)
    return createLL(root->data, l);
  l = findPathBT(root->right, x);
  if (l != NULL)
    return createLL(root->data, l);
  return NULL;
}

tree.c

#include"tree.h"

/************************************************/

/*
  La plupart des fonctionalites sont implementees dans 
  deux fonctions, une dont le suffixe est Tree, et une 
  dont le suffixe est Sons. Les deux fonctions 
  sont generalement mutuellement recursives, ce qui 
  signifie que chacune invoque l'autre.
 */

/************************************************/

tree* createTree(int data, treeList* sons)
{
  tree* t = (tree*)malloc(sizeof(tree));
  if (t == NULL)
    {
      printf("No memory available\n");
      exit(0);
    }
  t->data = data;
  t->sons = sons;
  return t;
}

/************************************************/

treeList* createSon(tree* data, treeList* next)
{
  treeList* s = (treeList*)malloc(sizeof(treeList));
  if (s == NULL)
    {
      printf("No memory available\n");
      exit(0);
    }
  s->data = data;
  s->next = next;
  return s;
}

/************************************************/

void printSons(treeList* l)
{
  if (l != NULL)
    {
      printTree(l->data);
      if (l->next != NULL)
	{
	  printf(", ");
	  printSons(l->next);
	}
    }
}

/************************************************/

void printTree(tree* t)
{
  if (t != NULL)
    {
      printf("(%d [", t->data);
      printSons(t->sons);
      printf("])");
    }
  else
    printf("X");
}

/************************************************/

treeList* randomSonsAux(int depht, int arity, int nbSons)
{
  if (nbSons == 0)
    return NULL;
  return createSon(randomTree(depht, arity),
		   randomSonsAux(depht, arity, nbSons - 1)
		   );
}

/************************************************/

treeList* randomSons(int depht, int arity)
{
  return randomSonsAux(depht, arity, arity);
}

/************************************************/

tree* randomTree(int depht, int arity)
{
  if (depht < 0)
    return NULL;
  return createTree(rand()%MOD, 
		  randomSons(depht - 1, arity)
		  );
}

/************************************************/

void destroySons(treeList* s)
{
  if (s != NULL)
    {
      destroySons(s->next);
      destroyTree(s->data);
      free(s);
    }
}

/************************************************/

void destroyTree(tree* t)
{
  if (t != NULL)
    {
      destroySons(t->sons);
      free(t);
    }
}

/************************************************/

int countSons(treeList* s)
{
  if (s == NULL)
    return 0;
  return countTree(s->data) + countSons(s->next);
}

/************************************************/

int countTree(tree* t)
{
  if (t == NULL)
    return 0;
  return 1 + countSons(t->sons);
}

/************************************************/

int sumSons(treeList* s)
{
  if (s == NULL)
    return 0;
  return sumTree(s->data) + sumSons(s->next);
}

/************************************************/

int sumTree(tree* t)
{
  if (t == NULL)
    return 0;
  return t->data + sumSons(t->sons);
}

/************************************************/

int heightSons(treeList* s)
{
  if (s == NULL)
    return -1;
  return MAX(heightTree(s->data), heightSons(s->next));
}

/************************************************/

int heightTree(tree* t)
{
  if (t == NULL)
    return -1;
  return 1 + heightSons(t->sons);
}

/************************************************/

int findSons(treeList* s, int x)
{
  if (s == NULL)
    return 0;
  return findTree(s->data, x) || findSons(s->next, x);
}

/************************************************/

int findTree(tree* t, int x)
{
  if (t == NULL)
    return 0;
  return (x == t->data) || findSons(t->sons, x);
}

/************************************************/

int nbXSons(treeList* s, int x)
{
  if (s == NULL)
    return 0;
  return nbXTree(s->data, x) + nbXSons(s->next, x);
}

/************************************************/

int nbXTree(tree* t, int x)
{
  if (t == NULL)
    return 0;
  return (x == t->data) + nbXSons(t->sons, x);
}

/************************************************/

treeList* copySons(treeList* s)
{
  if (s == NULL)
    return NULL;
  return createSon(copyTree(s->data), copySons(s->next));
}

/************************************************/

tree* copyTree(tree* t)
{
  if (t == NULL)
    return NULL;
  return createTree(t->data, copySons(t->sons));
}

/************************************************/

tree* treeOfBTree(bTree* t)
{
  if (t == NULL)
    return NULL;
  return createTree(t->data, 
		    createSon(treeOfBTree(t->left), 
			      createSon(treeOfBTree(t->right), NULL)
			      )
		  );
}

/************************************************/

ll* llOfTreeAux(tree* t, ll* acc);

ll* llOfSons(treeList* t, ll* acc)
{
  if (t == NULL)
    return acc;
  acc = llOfSons(t->next, acc);
  return llOfTreeAux(t->data, acc);
}

/************************************************/

ll* llOfTreeAux(tree* t, ll* acc)
{
  if (t == NULL)
    return acc;
  acc = llOfSons(t->sons, acc);
  return createLL(t->data, acc);
}

/************************************************/

ll* llOfTree(tree* t)
{
  return llOfTreeAux(t, NULL);
}

/************************************************/

/*
  Concatene les deux listes l1 et l2.
*/

treeList* concatSons(treeList* l1, treeList* l2)
{
  if (l2 == NULL)
    return l1;
  if (l1 == NULL)
    return l2;
  l1->next = concatSons(l1->next, l2);
  return l1;
}

/************************************************/

tree* destroyRootTree(tree* t)
{
  if (t == NULL || t->sons == NULL)
    return NULL;
  tree* newRoot = t->sons->data;
  newRoot->sons = concatSons(newRoot->sons, t->sons->next);
  free(t);
  return newRoot;
}

/************************************************/

int maxDephtSons(treeList* s, int x)
{
  if (s == NULL)
    return -1;
  return MAX(maxDephtTree(s->data, x), 
	     maxDephtSons(s->next, x)
	     );
}

/************************************************/

int maxDephtTree(tree* t, int x)
{
  if (t == NULL)
    return -1;
  int tmp = maxDephtSons(t->sons, x);
  if (tmp != -1)
    return tmp + 1 ;
  return (t->data == x) - 1;
}

/************************************************/

treeList* deleteXSons(treeList* s, int x)
{
  if (s == NULL)
    return NULL;
  s->data = deleteXTree(s->data, x);
  s->next = deleteXSons(s->next, x);
  return s;
}

/************************************************/

tree* deleteXTree(tree* t, int x)
{
  if (t == NULL)
    return NULL;
  t->sons = deleteXSons(t->sons, x);
  return (t->data == x) ? destroyRootTree(t): t;
}

/************************************************/

treeList* deleteNullSons(treeList* s)
{
  if (s == NULL)
    return NULL;
  s->next = deleteNullSons(s->next);
  s->data = deleteNullTree(s->data);
  if (s->data != NULL)
    return s;
  treeList* tmp = s->next;
  free(s);
  return tmp;
  
}

/************************************************/

tree* deleteNullTree(tree* t)
{
  if (t == NULL)
    return NULL;
  t->sons = deleteNullSons(t->sons);
  return t;
}

genericTree.c

#include"genericTree.h"

/*-------------------------------------------------------------*/

void* easyMalloc(unsigned int size)
{
  void* a = malloc(size);
  if (a == NULL)
    {
      printf("easyMalloc : plus de memoire.");
      exit(1);
    }
  return a;
}

/*-------------------------------------------------------------*/

abP abMake(void* data, abP left, abP right)
{
  abP a = (abP)easyMalloc(sizeof(ab));
  a->data = data;
  a->left = left;
  a->right = right;
  return a;
}

/*-------------------------------------------------------------*/

void* abAgregate(abP a, 
		 void* (*f)(void* data, 
			    void* leftImage, 
			    void* rightImage))
{
  if (a == NULL)
      return f(NULL, NULL, NULL);
  return f(a->data, 
	   abAgregate(a->left, f), 
	   abAgregate(a->right, f));
}

/*-------------------------------------------------------------*/

abP abMap(abP a, void* (*f)(void*))
{
  void* mapFunction(void* data, void* left, void* right)
    {
      return abMake(f(data), left, right);
    }
  return abAgregate(a, mapFunction);
}

/*-------------------------------------------------------------*/

void abInfixApply(abP a, void (*f)(void*))
{
  if (a != NULL)
    {
      abInfixApply(a->left, f);
      f(a->data);
      abInfixApply(a->right, f);
    }
}

/*-------------------------------------------------------------*/

void abDestroy(abP a, void (*destroyData)(void*))
{
  if (a != NULL)
    {
      abDestroy(a->left, destroyData);
      abDestroy(a->right, destroyData);
      destroyData(a->data);
      free(a);
    }
}

/*-------------------------------------------------------------*/

unsigned int abHeight(abP a)
{
  unsigned int *i;
  unsigned int res;
  void* f(void* data, void* left, void* right)
    {
      unsigned int* i = (unsigned int*)easyMalloc(sizeof(unsigned int));
      if (data == NULL)
	*i = 0;
      else
	*i = (*(unsigned int *)left > *(unsigned int *)right) ? 
	  *(unsigned int *)left : *(unsigned int *)right;
      free(left);
      free(right);
      return i;
    }
  i = abAgregate(a, f);
  res = *i;
  free(i);
  return res;
}

/*-------------------------------------------------------------*/

unsigned int abSize(abP a)
{
  unsigned int *i;
  unsigned int res;
  void* f(void* data, void* left, void* right)
    {
      unsigned int* i = (unsigned int*)easyMalloc(sizeof(unsigned int));
      if (data == NULL)
	*i = 0;
      else
	*i = 1 + *(unsigned int*)left + *(unsigned int*)right;
      free(left);
      free(right);
      return i;
    }
  i = abAgregate(a, f);
  res = *i;
  free(i);
  return res;
}

/*-------------------------------------------------------------*/

void abPrint(abP a, void(*print)(void*))
{
  if (a != NULL)
    {
      printf("(");
      abPrint(a->left, print);
      printf(", ");
      print(a->data);
      printf(", ");
      abPrint(a->right, print);
      printf(")");
    }
}

/*-------------------------------------------------------------*/

int puissance(int b, int n)
{
  if (n == 0)
    return 1;
  return b * puissance(b, n-1);
}

int* makeInt(int i)
{
  int* p = (int*)easyMalloc(sizeof(int));
  *p = i;
  return p;
}

abP intTree(int inf, int sup)
{
  int mid = (inf + sup)/2;
  if (inf > sup)
    return NULL;
  return abMake(makeInt(mid), 
		intTree(inf, mid - 1), 		
		intTree(mid + 1, sup));
}

void destroyInt(void* i)
{
  free(i);
}

void printInt(void* i)
{
  printf("%d", *(int*)i);
}

int main()
{
  abP a = intTree(0, puissance(2, 5));
  abPrint(a, printInt);
  printf("\n");
  abDestroy(a, destroyInt);
  return 0;
}