java - programar - Imprime todas las rutas de raíz a hoja en un árbol binario

programar un arbol binario de busqueda en java

Question

Estoy tratando de imprimir todas las rutas de raíz a hoja en un árbol binario utilizando Java.

public void printAllRootToLeafPaths(Node node,ArrayList path) 
{
    if(node==null)
    {
        return;
    }
    path.add(node.data);

    if(node.left==null && node.right==null)
    {
        System.out.println(path);
        return;
    }
    else
    {
        printAllRootToLeafPaths(node.left,path);
        printAllRootToLeafPaths(node.right,path);
    }      
}

En el método principal:

 bst.printAllRootToLeafPaths(root, new ArrayList());

Pero está dando salida incorrecta.

árbol dado

   5
  / /
 /   /
1     8
 /    //
  /  /  /
  3  6   9

Rendimiento esperado:

[5, 1, 3]

[5, 8, 6]

[5, 8, 9]

Pero la salida produjo:

[5, 1, 3]

[5, 1, 3, 8, 6]

[5, 1, 3, 8, 6, 9]

¿Alguien puede resolverlo?

Answer 1

Aquí está la implementación correcta

public static <T extends Comparable<? super T>> List<List<T>> printAllPaths(BinaryTreeNode<T> node) {
    List <List<T>> paths = new ArrayList<List<T>>();
    doPrintAllPaths(node, paths, new ArrayList<T>());
    return paths;
}

private static <T extends Comparable<? super T>> void doPrintAllPaths(BinaryTreeNode<T> node, List<List<T>> allPaths, List<T> path) {
    if (node == null) {
        return ;
    }
    path.add(node.getData());
    if (node.isLeafNode()) {
        allPaths.add(new ArrayList<T>(path));   

    } else {
        doPrintAllPaths(node.getLeft(), allPaths, path);
        doPrintAllPaths(node.getRight(), allPaths, path);
    }
    path.remove(node.getData());
}

Aquí está el caso de prueba

@Test
public void printAllPaths() {
    BinaryTreeNode<Integer> bt = BinaryTreeUtil.<Integer>fromInAndPostOrder(new Integer[]{4,2,5,6,1,7,3}, new Integer[]{4,6,5,2,7,3,1});
    List <List<Integer>> paths = BinaryTreeUtil.printAllPaths(bt);

    assertThat(paths.get(0).toArray(new Integer[0]), equalTo(new Integer[]{1, 2, 4}));
    assertThat(paths.get(1).toArray(new Integer[0]), equalTo(new Integer[]{1, 2, 5, 6}));
    assertThat(paths.get(2).toArray(new Integer[0]), equalTo(new Integer[]{1, 3, 7}));

    for (List<Integer> list : paths) {          
        for (Integer integer : list) {
            System.out.print(String.format(" %d", integer));
        }
        System.out.println();
    }
}

Aquí está la salida

1 2 4

1 2 5 6

1 3 7

Answer 2

Está pasando su lista de forma recursiva, pero ese es un objeto mutable, por lo que todas las llamadas lo modificarán (llamando a List.add ) y List.add sus resultados. Intente clonar / copiar el argumento de la path a todas las llamadas recursivas para proporcionar a cada rama (harhar) su propio contexto.

Answer 3

Llama a los métodos recursivos con:

printAllRootToLeafPaths(node.left, new ArrayList(path));
printAllRootToLeafPaths(node.right, new ArrayList(path));

Lo que sucede allí cuando pasa la path (en lugar de la new ArrayList(path) es que usa un solo objeto en todos los métodos de llamada, lo que significa que, cuando regresa al llamante original, el objeto no se encuentra en el mismo estado que estaba.

Solo necesita crear un nuevo objeto e inicializarlo a los valores originales. De esta manera el objeto original no se modifica.

Answer 4

Podemos usar la recursión para lograrlo. La estructura de datos correcta lo hace conciso y eficiente.

List<LinkedList<Tree>> printPath(Tree root){

    if(root==null)return null;

    List<LinkedList<Tree>> leftPath= printPath(root.left);
    List<LinkedList<Tree>> rightPath= printPath(root.right);

    for(LinkedList<Tree> t: leftPath){
         t.addFirst(root);
    }
    for(LinkedList<Tree> t: rightPath){
         t.addFirst(root);
    }


 leftPath.addAll(rightPath);

 return leftPath;


}

Answer 5

Probé este problema con un ArrayList y mi programa imprimió rutas similares.

Así que modifiqué mi lógica para que funcione correctamente manteniendo un count interno, así es como lo hice.

private void printPaths(BinaryNode node, List<Integer> paths, int endIndex) {
        if (node == null)
            return;
        paths.add(endIndex, node.data);
        endIndex++;
        if (node.left == null && node.right == null) {
            //found the leaf node, print this path
            printPathList(paths, endIndex);
        } else {
            printPaths(node.left, paths, endIndex);
            printPaths(node.right, paths, endIndex);
        }
    }

public void printPaths() {
    List<Integer> paths = new ArrayList<>();
    printPaths(root, paths, 0);
}

Answer 6

Puedes hacer lo siguiente,

public static void printTreePaths(Node<Integer> node) {
    int treeHeight = treeHeight(node);
    int[] path = new int[treeHeight];
    printTreePathsRec(node, path, 0);

}

private static void printTreePathsRec(Node<Integer> node, int[] path, int pathSize) {
    if (node == null) {
        return;
    }

    path[pathSize++] = node.data;

    if (node.left == null & node.right == null) {
        for (int j = 0; j < pathSize; j++ ) {
            System.out.print(path[j] + " ");
        }
        System.out.println();
    }

     printTreePathsRec(node.left, path, pathSize);
     printTreePathsRec(node.right, path, pathSize);
}

public static int treeHeight(Node<Integer> root) {
    if (root == null) {
        return 0;
    }

    if (root.left != null) {
        treeHeight(root.left);
    }

    if (root.right != null) {
        treeHeight(root.right);
    }

    return Math.max(treeHeight(root.left), treeHeight(root.right)) + 1;

}

Answer 7

Puedes hacerlo de esta manera también. Aquí está mi código de Java.

public void printPaths(Node r,ArrayList arr)
{
    if(r==null)
    {
        return;
    }
    arr.add(r.data);
    if(r.left==null && r.right==null)
    {
        printlnArray(arr);
    }
    else
    {
        printPaths(r.left,arr);
        printPaths(r.right,arr);
    }

     arr.remove(arr.size()-1);
}

Answer 8

/* Given a binary tree, print out all of its root-to-leaf
   paths, one per line. Uses a recursive helper to do the work.*/
void printPaths(Node node) 
{
    int path[] = new int[1000];
    printPathsRecur(node, path, 0);
}

/* Recursive helper function -- given a node, and an array containing
   the path from the root node up to but not including this node,
   print out all the root-leaf paths. */
void printPathsRecur(Node node, int path[], int pathLen) 
{
    if (node == null)
        return;

    /* append this node to the path array */
    path[pathLen] = node.data;
    pathLen++;

    /* it''s a leaf, so print the path that led to here */
    if (node.left == null && node.right == null)
        printArray(path, pathLen);
    else
        { 
        /* otherwise try both subtrees */
        printPathsRecur(node.left, path, pathLen);
        printPathsRecur(node.right, path, pathLen);
    }
}

/* Utility that prints out an array on a line */
void printArray(int ints[], int len) 
{
    int i;
    for (i = 0; i < len; i++) 
        System.out.print(ints[i] + " ");
    System.out.println("");
}

Answer 9

public void PrintAllPossiblePath(Node node,List<Node> nodelist)
{
    if(node != null)
    {
            nodelist.add(node);
            if(node.left != null)
            {
                PrintAllPossiblePath(node.left,nodelist);
            }
            if(node.right != null)
            {
                PrintAllPossiblePath(node.right,nodelist);
            }
            else if(node.left == null && node.right == null)
            {

            for(int i=0;i<nodelist.size();i++)
            {
                System.out.print(nodelist.get(i)._Value);
            }
            System.out.println();
            }
            nodelist.remove(node);
    }
}

nodelist.remove(node) es la clave, elimina el elemento una vez que imprime la ruta respectiva