0

Estoy aprendiendo a usar los árboles binarios en c++ y no acabo de caer en como resolver este algoritmo correctamente.

Partiendo de un árbol binario, mi objetivo es imprimir los nodos finales entre paréntesis por emparejamientos de la siguiente forma:

introducir la descripción de la imagen aquí

salida: ((1 4)(2 3))

mi código:

void imprimir(struct arbol a){
    if(a.val == 0) return;
    if(a->der == 0 and a->izq == 0) cout << a->val << " ";
    else cout << "(";
    imprimir(a->izq);
    imprimir(a->der);
    cout << ")";   
}

Estoy usando un struct arbol con val(valor nodo) y der,izq(hijos). Entiendo que la manera de ir leyendo el árbol y cómo saber si estás en una hoja es la correcta pero me cuesta pensar la manera recursiva de sacar los paréntesis.

Muchas gracias de antemano! :)

1 respuesta 1

1

Los paréntesis únicamente deben imprimirse cuando te encuentras en el nodo que precede a los nodos finales. En este caso, asumiendo un arbol de base plana, bastaría con comprobar si existe cualquiera de los 4 nietos de un nodo dado.

void imprimir(struct arbol a){
    if(a.val == 0) return;
    if(a->der == 0 and a->izq == 0)
        cout << a->val << " ";
    else if (a->der->der == nullptr) 
        cout << "(";

    imprimir(a->izq);
    imprimir(a->der);

    if (a->der->der == nullptr) 
        cout << ")";   
}

Con los paréntesis principales no puedes hacer gran cosa salvo que tengas alguna forma de detectar cuándo te encuentras en el primer nodo. La alternativa sencilla es imprimir los paréntesis exteriores manualmente:

std::cout << "(";
imprimir(root);
std::cout << ")";

Por cierto, nota que en C++ struct arbol a se convierte en arbol a. La palabra struct únicamente es necesaria cuando estás declarando tipos, no variables.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.