Ayuda con arboles rojo y negro

Publicado en 'Programación' por Alguno, 6 Nov 2014.





  1. Alguno

    Alguno Miembro frecuente

    Registro:
    30 Ago 2009
    Mensajes:
    140
    Likes:
    10




    Hola bueno estoy programando arboles binarios y hasta ahora los eh hecho con estructuras y punteros(mas abajo dejo parte del codigo) pero lo que quiero es hacerlo con arrays sin usar punteros(es para un trabajo de la u) y tengo el speudocodigo pero no llego entender como crear el arbol y los nodos a puro arrays , no se si podran hecharme una mano.
    Código:
    struct node//creo nodo
    {
        int dato;     // dato
        char color;  //  color
        struct node *left, *right, *padre;
    };
    struct arbol
    {
    struct node *root;
    struct node *nil;
    };
    //funcion insertar con punteros
    void insert(struct arbol* T , int dato)
    {
        struct node *z = (struct node*)malloc(sizeof(struct node));
        z->dato = dato;
        z->right = z->left = z->padre = T->nil;
         struct node *y = (struct node*)malloc(sizeof(struct node));
         y=T->nil;
        
         struct node *x = (struct node*)malloc(sizeof(struct node));
         x=T->root;
    
            while (x != T->nil)
            {
                y = x;
                if (z->dato < x->dato)
                    x = x->left;
                else
                    x = x->right;
            }
            z->padre = y;
            if (y == T->nil)
                T->root = z;
            else if(z->dato < y->dato)
                 y->left = z;
            else y->right = z;
            z->color = 'R';
            z->left = z->right = T->nil;
            insertFixUp(T,z);
        } 
    int main()
    {
         struct arbol* T = (struct arbol*)malloc(sizeof(struct arbol));
         T->root = (struct node*)malloc(sizeof(struct node));
         T->nil = (struct node*)malloc(sizeof(struct node));
         T->nil->right= T->nil->left=T->nil->padre=T->nil;
         T->root=T->nil;
         T->nil->color = 'B';
         T->root->padre = T->nil;}
    Estas solo son aprtes del codigo no es todo ya que es grande, en general creo una estructura arbol y hago las operaciones , el psudocodigo que tengo para pasarlo a array es este :
    Código:
    RB-INSERT(T, z)
    1 y ← nil[T]
    2 x ← root[T]
    3 while x ≠ nil[T]
    4do y ← x
    5if key[z] < key[x]
    6then x ← left[x]
    7else x ← right[x]
    8 p[z] ← y
    9 if y = nil[T]
    10then root[T] ← z
    11else if key[z] < key[y]
    12then left[y] ← z
    13else right[y] ← z
    14 left[z] ← nil[T]
    15 right[z] ← nil[T]
    16 color[z] ← RED
    17 RB-INSERT-FIXUP(T, z)
    
    en este la funcion insert esta con puros arrays pero no entiendo como manejan ni declaran el arbol , la idea es pasar del codigo que ya tengo en punteros a arrays como en ese pseudocodigo , espero alguna ayuda o recomendacion , gracias
     


Etiquetas: