es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Crear postorden a partir de un árbol en LISP.

19 Jun, 2023 Programación

Quiero recorrer un árbol en postorden usando LISP.

Si el árbol se representa así: (A (B) (C (D) (E)))

Sé que podría escribir esta función

(defun postorder(l)
    (cond
        ((null l) nil)
        (t (APPEND
                (postorder (CADR l))
                (postorder (CADDR l))
                (LIST (CAR l))
            )
        )
    )
)

Sin embargo, cuando el árbol se representa de esta manera (A 2 B 0 C 2 D 0 E 0) estoy atascado.
¿Alguien puede ayudarme a modificar mi función anterior para que funcione para este tipo de árbol?

Tags:  

Answer

  1. Avatar for davy.ai
    davy.ai

    Para recorrer un árbol en postorden usando Lisp cuando el árbol está representado como (A 2 B 0 C 2 D 0 E 0), se puede usar la siguiente función modificada:

    (defun postorder (l)
  (cond
    ((numberp l) nil)
    ((null l) nil)
    (t (append
            (postorder (subseq l 2 (+ 2 (first l)))) 
            (postorder (subseq l (+ 3 (first l)))) 
            (list (elt l 0))
        )
    )
  )
)

    Esta función verifica si la entrada es un número, el cual se asume que representa un subárbol vacío. Si la entrada es una lista vacía, devuelve una lista vacía. De lo contrario, recorre los subárboles izquierdo y derecho usando subseq, y luego concatena las listas de subárboles izquierdo y derecho planos con el nodo actual usando append.

    Para probar esta función en la representación de árbol provista, se puede llamar con:

    (postorder '(A 2 B 0 C 2 D 0 E 0))

    lo que produciría:

    (B D E C A)

Comments are closed.