ALGORITMIA EX2 2014-1 Pregunta 6

#include <stdio.h>
#include <stdlib.h>

typedef int TInfo;

typedef struct Node{
    TInfo info;
    struct Node *left, *right;
}TNode;

typedef struct tree{
    TNode* root;
}TBinaryTree;


void init_tree(TBinaryTree* T){
    T->root = NULL;
}


void insert(TBinaryTree* T, TInfo x){
    TNode* nuevo = (TNode*)malloc(sizeof(TNode));
    nuevo->info = x;
    nuevo->left = nuevo->right = NULL;

    //Caso 1: Arbol vacio
    if(T->root == NULL){
        T->root = nuevo;
        return;
    }

    TNode *p, *q;
    p = T->root;
    int flag = 0;

    while(p!=NULL){
        q = p;
        if(x < p->info){
            p = p->left;
            flag = 0;
        }else if(x > p->info){
            p = p->right;
            flag = 1;
        }
    }

    if(flag == 0){
        q->left = nuevo;
    }else{
        q->right = nuevo;
    }
}

int count_tree(TNode* node){
    if(node==NULL)
        return 0;

    return 1 + count_tree(node->left) +
                count_tree(node->right);
}


int isABBlim(TNode* node,float b){

    if(node==NULL)
        return 1;;
    float cant;
    //No estoy segura si "Cantidad(N) es el número de nodos que tiene el árbol binario cuya raı́z es N."
    //incluye al nodo root. Si es así, está bien.
    cant=(count_tree(node->left)+1)/ (double) (count_tree(node)+1);
    if (!((cant<=(1-b)) && (cant>=b)))
        return 0;

    return isABBlim(node->left,b) && isABBlim(node->right,b);
}

void main(){
    TBinaryTree T;
    init_tree(&T);

    insert(&T, 12);
    insert(&T, 7);
    insert(&T, 16);

    inorden(T.root);
    if (isABBlim(T.root,0))
        printf("Es un arbol binario balanceado por el limite\n");
    else
        printf("No es un arbol binario balanceado por el limite\n");

}