Question imprimer tous les chemins racine à feuille dans un arbre binaire


J'essaie d'imprimer tous les chemins de la racine à la feuille dans un arbre binaire en utilisant 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 méthode principale:

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

Mais c'est donner un mauvais résultat.

arbre donné:

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

Production attendue:

[5, 1, 3]

[5, 8, 6]

[5, 8, 9]

Mais la sortie produite:

[5, 1, 3]

[5, 1, 3, 8, 6]

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

Quelqu'un peut-il le comprendre ...


15
2018-02-18 12:54


origine


Réponses:


Appelez les méthodes récursives avec:

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

Qu'est-ce qui se passe là quand vous passez le path (au lieu de new ArrayList(path) est que vous utilisez un seul objet dans toutes les méthodes appel, ce qui signifie que, lorsque vous revenez à l'appelant d'origine, l'objet n'est pas dans le même état qu'il était.

Il vous suffit de créer un nouvel objet et de l'initialiser aux valeurs d'origine. De cette façon, l'objet d'origine n'est pas modifié.


23
2018-02-18 12:58



Vous passez votre liste récursivement, mais c'est un objet mutable, donc tous les appels le modifieront (en appelant List.add) et modifier vos résultats. Essayez de cloner / copier le path argument à tous les appels récursifs pour fournir à chaque branche (harhar) son propre contexte.


9
2018-02-18 12:56



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) est la clé, il supprime l'élément une fois qu'il imprime le chemin respectif


8
2018-06-25 18:10



vous pouvez faire cela aussi. voici mon code 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);
}

2
2018-06-29 09:00



Voici la mise en œuvre correcte

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());
}

Voici le cas de test

@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();
    }
}

Voici la sortie

1 2 4

1 2 5 6

1 3 7

1
2018-02-18 10:01



/* 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("");
}

0
2017-09-06 16:20



J'ai essayé ce problème avec un ArrayList et mon programme a imprimé des chemins similaires.

J'ai donc modifié ma logique pour fonctionner correctement en maintenant une count, voici comment je l'ai fait.

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);
}

0
2018-01-17 09:41



Nous pouvons utiliser la récursivité pour y parvenir. Une structure de données correcte le rend concis et efficace.

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;


}

0
2018-06-20 02:05