Atravesando un árbol binario recursivamente

Question

Estoy irremediablemente perdido cuando se trata de funciones recursivas. Estoy obligado a crear una función recursiva para recorrer un árbol binario e insertar un nuevo nodo entre valores específicos. ¿Debo volver a copiar mi función de desplazamiento y modificarla en cualquier otra función en la que la use? ¿Alguien podría evaluar la función transversal?

Creo que mi código de desplazamiento está bien.

Node traverse (Node currentNode){ 
    if (!currentNode.left.equals(null)){ 
     traverse (currentNode.left); 
     return currentNode.left; 
    } 
    if (!currentNode.right.equals(null)){ 
     traverse (currentNode.right); 
     return currentNode.right; 
    } 
    return currentNode; 
} 

Answer 1

Cuando se trata de árboles binarios, hay varios tipos diferentes de recorridos que se pueden hacer recursivamente. Están escritos en el orden en que se mencionan y se visitan (L = niño izquierdo, V = visita ese nodo, R = niño derecho).

• Dentro de la orden de recorrido (LVR)
• Invertir orden de recorrido (RVL)
• Preordenes recorrido (VLR)
• orden posterior recorrido aparece su código (LRV)

que está realizando el método de cruce del postorder, pero estás confundiendo algunas cosas. Primero, el nodo es lo que desea recorrer; el datos es lo que desea visitar. En segundo lugar, no tiene ninguna razón para devolver el nodo en sí, de la forma en que esto se implementa. Su código no permite que una condición diga 'Estoy buscando datos en particular, ¿lo tiene Mr. Node @ 0xdeadbeef?', Que se encontraría con algún tipo de parámetro de búsqueda adicional.

Una travesía académica BST solo imprime los nodos. Si desea agregar una funcionalidad de búsqueda, es solo un parámetro más, así como una verificación adicional para el nodo correcto.

He aquí un fragmento:

// Academic 

public void traverse (Node root){ // Each child of a tree is a root of its subtree. 
    if (root.left != null){ 
     traverse (root.left); 
    } 
    System.out.println(root.data); 
    if (root.right != null){ 
     traverse (root.right); 
    } 
} 

// Search with a valid node returned, assuming int 

public Node traverse (Node root, int data){ // What data are you looking for again? 
    if(root.data == data) { 
     return root; 
    } 
    if (root.left != null){ 
     return traverse (root.left, data); 
    } 
    if (root.right != null){ 
     return traverse (root.right, data); 
    } 
    return null; 
} 

Answer 2

Una función recursiva devuelve el valor de sí mismo con un parámetro modificado o una condición de finalización (salida). por ejemplo, factorial:

int factorial(int param) { 
    if (param > 1) { 
     return param * factorial(param -1); 
    } else { 
     return 1; 
    } 
} 

En su código, llama a un 'travesía', pero luego no hacen nada con el resultado ... Cuando termina su función recursiva, a su regreso definitivo será el primer hijo de la izquierda si es que existe, sino el primer hijo derecho si existe, sino el nodo raíz.

Proporcione más detalles sobre por qué necesita atravesar el árbol (también, no estoy seguro de lo que quiere decir con "copiar la función y modificarla en cualquier otra función", la idea de una función es codificar una vez -call-many)

Answer 3

Parece que estás atravesando en la metodología de preorden, pero soy un poco escéptico en cuanto a lo que deseas lograr sin comparar tu nodo actual con un valor base que define que has llegado a tu ur destino. Sugeriría dibujar un árbol simple y visualizar los pasos. Luego trata de poner eso en el código.