Skip to content
Snippets Groups Projects
Select Git revision
  • 6e70213a9f6d466ab70b49c6c31351b50afb3b32
  • master default protected
2 results

main.go

Blame
  • bin_tree.c 2.68 KiB
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    #include <stdbool.h>
    #include <math.h>
    #include "bin_tree.h"
    
    static node* position(arbre tree,int cle) {
       node* crt = tree;
       if (NULL != crt) {
          while (cle != crt->key 
                 && NULL != crt->child[(cle > crt->key)]) {
             crt = crt->child[(cle > crt->key)];
          }
       }
       return crt;
    }
    
    int arbre_depth(arbre tree) {
       if (NULL == tree) {
          return 0;
       } else {   
          return 1+fmax(arbre_depth(tree->child[0]),arbre_depth(tree->child[1]));
       }
    }
    
    int arbre_size(arbre tree) {
       if (NULL == tree) {
          return 0;
       } else {   
          return 1+arbre_size(tree->child[0])+arbre_size(tree->child[1]);
       }
    }
    
    bool arbre_insert(arbre* tree,int cle) {
       if (NULL == *tree) {
          *tree = calloc(1,sizeof(node));
          (*tree)->key = cle;
       } else {
          node* nd = position(*tree,cle);
          if (cle != nd->key) {
             nd->child[(cle > nd->key)] = calloc(1,sizeof(node));
             nd->child[(cle > nd->key)]->key = cle;
          } else {
             return false;
          }
       }
       return true;
    }
    
    static node* parent(arbre tree,node* nd) {
       assert(NULL != tree && NULL != nd);
       node* parent = NULL;
       if (nd != tree) {
          node* crt = tree;
          int cle = nd->key;
          do  {
             parent = crt;
             if (cle != crt->key) {
                crt = crt->child[(cle > crt->key)];
             }
          } while (crt != nd);
       }
       return parent;
    }
    
    
    
    
    
    
    
    bool arbre_delete(arbre* tree,int cle) {
       node* nd = position(*tree,cle);
       
       if (NULL == nd || cle != nd->key) {
          return false;
       }
    
       // terminal node
       if (NULL == nd->child[0] && NULL == nd->child[1]) {
          node* nd_parent = parent(*tree,nd);
          if (NULL == nd_parent) { // single node tree
             *tree = NULL;
          } else {
             nd_parent->child[(nd == nd_parent->child[1])] = NULL;
          }
          free(nd);
          return true;
       }
    
       for (int ind=0;ind<2;ind++) {
          if (NULL != nd->child[ind]) {
             node* next = position(nd->child[ind],cle);
             int val = next->key;
             if (NULL == nd->child[ind]->child[ind^1]) {
                nd->child[ind] = next->child[ind];
                free(next);
             } else {
                bool res = arbre_delete(tree,next->key);
             }
             nd->key = val;
             return true;
          }
       }
    }
    
    void arbre_print(arbre tree,int N) {
       if (N <= 0) {
          N = 1;
       }
       if (NULL != tree) {
          arbre_print(tree->child[1],N+1);
          for (int i=0;i<N;i++) {
             printf("    ");
          }
          printf("%d\n",tree->key);            
          arbre_print(tree->child[0],N+1);
       } 
    }
    
    bool arbre_search(arbre tree,int cle) {
       node* nd = position(tree,cle);
       return (NULL != nd && cle == nd->key);
    }