C/Visual C - ayuda con arboles

#include <stdio.h>

#include <stdlib.h>

// Estructura de un nodo del árbol

struct Node {

    int key;

    struct Node* left;

    struct Node* right;

    int height;

};

// Función para obtener la altura de un nodo

int height(struct Node* N) {

    if (N == NULL)

        return 0;

    return N->height;

}

// Función para obtener el máximo de dos enteros

int max(int a, int b) {

    return (a > b) ? a : b;

}

// Función para crear un nuevo nodo

struct Node* newNode(int key) {

    struct Node* node = (struct Node*)malloc(sizeof(struct Node));

    node->key = key;

    node->left = NULL;

    node->right = NULL;

    node->height = 1; // nuevo nodo es inicialmente agregado en hoja

    return node;

}

// Rotación a la derecha

struct Node* rightRotate(struct Node* y) {

    struct Node* x = y->left;

    struct Node* T2 = x->right;

    // Realizar rotación

    x->right = y;

    y->left = T2;

    // Actualizar alturas

    y->height = max(height(y->left), height(y->right)) + 1;

    x->height = max(height(x->left), height(x->right)) + 1;

    // Devolver nueva raíz

    return x;

}

// Rotación a la izquierda

struct Node* leftRotate(struct Node* x) {

    struct Node* y = x->right;

    struct Node* T2 = y->left;

    // Realizar rotación

    y->left = x;

    x->right = T2;

    // Actualizar alturas

    x->height = max(height(x->left), height(x->right)) + 1;

    y->height = max(height(y->left), height(y->right)) + 1;

    // Devolver nueva raíz

    return y;

}

// Obtener el factor de balanceo de un nodo

int getBalance(struct Node* N) {

    if (N == NULL)

        return 0;

    return height(N->left) - height(N->right);

}

// Función para insertar un nuevo nodo

struct Node* insert(struct Node* node, int key) {

    // 1. Realizar la inserción normal

    if (node == NULL)

        return newNode(key);

    if (key < node->key)

        node->left = insert(node->left, key);

    else if (key > node->key)

        node->right = insert(node->right, key);

    else // Duplicados no son permitidos

        return node;

    // 2. Actualizar la altura del nodo ancestro

    node->height = 1 + max(height(node->left), height(node->right)));

    // 3. Obtener el factor de balanceo

    int balance = getBalance(node);

    // Si el nodo se vuelve desbalanceado, hay 4 casos

    // Caso Izquierda Izquierda

    if (balance > 1 && key < node->left->key)

        return rightRotate(node);

    // Caso Derecha Derecha

    if (balance < -1 && key > node->right->key)

        return leftRotate(node);

    // Caso Izquierda Derecha

    if (balance > 1 && key > node->left->key) {

        node->left = leftRotate(node->left);

        return rightRotate(node);

    }

    // Caso Derecha Izquierda

    if (balance < -1 && key < node->right->key) {

        node->right = rightRotate(node->right);

        return leftRotate(node);

    }

    // Retornar el puntero del nodo (sin cambios)

    return node;

}

// Función para imprimir el árbol en orden

void inOrder(struct Node* root) {

    if (root != NULL) {

        inOrder(root->left);

        printf("%d ", root->key);

        inOrder(root->right);

    }

}

// Función principal

int main() {

    struct Node* root = NULL;

    // Insertar nodos

    root = insert(root, 10);

    root = insert(root, 20);

    root = insert(root, 30);

    root = insert(root, 40);

    root = insert(root, 50);

    root = insert(root, 25);

    // Imprimir el árbol en orden

    printf("Recorrido en orden del árbol AVL: ");

    inOrder(root);

    return 0;

}