Necesito el pseudocódigo C++ que se busca a través de un árbol para encontrar el nodo con el valor de «z».

la función se da el nodo raíz del árbol, para empezar.
El árbol tiene la propiedad donde cada nodo tiene a lo más dos nodos hijos.
Cada nodo tiene 3 propiedades: a la izquierda niño, el derecho del niño, y el valor.

  • Es esta tarea?
  • no, yo se lo acabo de preguntar esto en una entrevista, quiero ver cómo lo hice yo 🙂
InformationsquelleAutor fmunshi | 2010-10-27

1 Comentario

  1. 7

    El siguiente pseudo-código hace lo que usted desea para un árbol en orden ascendente.

    def findval (node,lookfor):
        if node is null:
            return null
        if node.val is equal to lookfor:
            return node
        if node.val is less than lookfor
            return findval (node.right,lookfor)
        return findval (node.left,lookfor)
    

    a ser llamado con:

    znode = findval (root, "z")
    

    Se le dará el nodo o null si no hay ningún nodo existe.

    Si quieres evitar la recursividad, puede utilizar el proceso iterativo de solución:

    def findval (node,lookfor):
        while node is not null:
            if node.val is equal to lookfor:
                break
            if node.val is less than lookfor:
                node = node.right
            else:
                node = node.left
        return node
    

    Obviamente, hay todo tipo de mejoras que podría realizar, tales como permitir a un orden diferente, o una devolución de llamada de función de comparación, o que permiten claves duplicadas, pero este es el ejemplo canónico de un árbol binario de búsqueda.

    • esta solución supone que el derecho nodo tiene valores superiores a la izquierda del nodo, pero mi pregunta no dice eso.
    • Pero que invariablemente es el caso, ya que estos árboles fueron creados como parte de las estructuras de búsqueda. Si no es el caso, entonces usted necesita primero la profundidad o amplitud primera búsqueda.
    • El comportamiento habitual de un árbol binario es un orden ascendente. Si ese no es el caso, simplemente cambie en torno a las condiciones.
    • el punto entero de un árbol, es el fin de los nodos. Es una suposición razonable para hacer que los niños podrían ser ordenado.
    • ¿cuál es la razón para poner el cheque para el nodo que se va a NULL en el principio?
    • así que puede controlar de forma elegante vacío de un árbol (donde la raíz es null).

Dejar respuesta

Please enter your comment!
Please enter your name here