Este artículo describe el método Java para imprimir todas las rutas del árbol binario. Compártelo para su referencia, como sigue:
pregunta:
Dé un árbol binario e imprima todos los caminos.
Por ejemplo, para el siguiente árbol binario, todos sus caminos son:
8 -> 3 -> 1
8 -> 2 -> 6 -> 4
8 -> 3 -> 6 -> 7
8 -> 10 -> 14 -> 13
Ideas:
A partir del nodo raíz, coloque su propio valor en una matriz y luego pase esta matriz a su nodo hijo. El nodo infantil también pone su propio valor en esta matriz y lo pasa a su nodo infantil hasta que este nodo sea un nodo de hoja, y luego imprime la matriz. Entonces, necesitamos usar la recursión aquí.
Código:
/** Dado un árbol binario, imprime todas sus raíces a hojas, uno por línea. Utiliza un ayudante recursivo para hacer el trabajo.*/Public void printPaths (root nodo, int n) {string [] path = new String [n]; printPaths (root, ruta, 0);}/** RECURSIVO PRIMPATHS ALPER-Dado un nodo, y una matriz que contiene la ruta desde el nodo raíz hasta pero no incluir este nodo, imprime todas las rutas de roíz.*/privado void printpaths (nodo de nodo, cadena [] ruta, int // Agregar este nodo a la ruta de matriz de ruta [PathLen ++] = node.value; // es una hoja, así que imprima la ruta que condujo aquí si (node.leftchild == null && node.rightchild == null) {printArray (ruta, pathlen); } else {// de lo contrario, pruebe ambos subtrotes printPaths (node.leftchild, ruta, ruta); printPaths (node.rightChild, ruta, ruta); }}/** Utilidad que imprime cadenas desde una matriz en una línea.*/Private void printArray (string [] ints, int len) {for (int i = 0; i <len; i ++) {System.out.print (ints [i]+""); } System.out.println ();}Nota: Solo puede usar una matriz + un valor para imprimir la ruta requerida. Si usa una estructura de lista vinculada como LinkedList, no funcionará. Vale la pena analizar las razones, es muy interesante.
Para obtener más información sobre los algoritmos de Java, los lectores interesados en este sitio pueden ver los temas: "Estructura de datos Java y tutorial de algoritmo", "Resumen de las puntas de nodo de operación de Java DOM", "Resumen de Java Archivo y TIPS de operación de directorio" y "Summary of Java Cache Operation Tips" TIPS ""
Espero que este artículo sea útil para la programación Java de todos.