18

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

主な方法で：

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

しかし、その出力は間違っています。

与えられたツリー:

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

期待される出力:

[5、1、3]

[5、8、6]

[5、8、9]

しかし、出力は次のように生成されました。

[5、1、3]

[5、1、3、8、6]

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

誰か解ってくれませんか...

4

12 に答える 12

29

次のように再帰メソッドを呼び出します。

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

path(の代わりにnew ArrayList(path)、すべてのメソッド呼び出しで単一のオブジェクトを使用すると、元の呼び出し元に戻ると、オブジェクトは元の状態と同じ状態にならないということです。

新しいオブジェクトを作成し、元の値に初期化するだけです。この方法では、元のオブジェクトは変更されません。

于 2013-02-18T12:58:40.253 に答える
10 
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)がキーです。それぞれのパスを出力すると、要素が削除されます

于 2013-06-25T18:10:37.773 に答える
9

リストを再帰的に渡しますが、これは可変オブジェクトであるため、すべての呼び出しでリストが変更され（を呼び出すことによりList.add）、結果が混乱します。引数をすべての再帰呼び出しに複製/コピーしてpath、各ブランチ（harhar）に独自のコンテキストを提供してみてください。

于 2013-02-18T12:56:51.343 に答える
4

この方法でもできます。これが私の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);
}
于 2016-06-29T09:00:32.717 に答える
3

ここに正しい実装があります

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

ここにテストケースがあります

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

ここに出力があります

1 2 4

1 2 5 6

1 3 7
于 2016-02-18T10:01:39.933 に答える
0 
/* 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("");
}
于 2016-09-06T16:20:45.677 に答える