java - 二叉树节点值添加到ArrayList后发生变化

Question

首先，我知道必须在每次迭代中创建一个新的 Tree 实例，以免重用相同的对象，并且还具有静态对象 this和 this线程通知。我想我已经检查了代码的每个部分。

所以，我正在测试下面的代码。关于它的作用的一些信息:

第一个循环迭代根节点列表，其中子节点形成二叉树。我为每个根节点创建一个树对象并将其添加到其中，该对象还包含两个数组列表，一个用于树中的所有节点，另一个仅用于叶子。在循环中，我还为每棵树中的每个叶子随机设置从 1 到 n 的数字(其中 n 是树中叶子的数量)，并将树添加到 arrayList : possibleTrees 中。

问题:在第一个循环中，当我迭代每棵树的叶子并打印它们的编号时，它会相应地打印它们。但在它完成后，我迭代了 possibleTrees 打印所有树叶，许多值发生了变化。

这是一棵有 4 个叶子的树的代码及其下面的输出。顶部打印两次，因为一个是整数数组列表，第二个是直接从节点打印值

编辑:链接到Tree , Node类

编辑2:添加了所有拓扑类(http://)pastebin.com/sB9UV8T6

    ArrayList<Tree> possibleTrees = new ArrayList<Tree>();
    ArrayList<Integer> numbers = new ArrayList<Integer>();        
    for (int i = 0; i < numNodes; i++) {
        numbers.add(i + 1);
    }
    for (Node n : allTopologies.allBinaryTrees(numNodes)) {
        Tree tree = new Tree();

        tree.setNodesLists(n);

        Collections.shuffle(numbers);
        tree.setleafNums(n, numbers);
        tree.setRoot(n);

        possibleTrees.add(tree);

        System.out.println(numbers);
        System.out.print("[");
        for (Node l : tree.getLeaves()) {

            System.out.print(l.getLeafNum() + ", ");
        }
        System.out.println("]");
        System.out.println("");

    }
    System.out.println("-------------------------------");
    for (Tree t : possibleTrees) {
        System.out.print("[");
        for (Node l : t.getLeaves()) {

            System.out.print(l.getLeafNum() + ", ");
        }
        System.out.println("]");
        System.out.println("");
    }

输出:
[3,2,1,4][3,2,1,4,]

[2,4,1,3][2,4,1,3,]

[2,4,1,3][2,4,1,3,]

[1,3,2,4][1,3,2,4,]

[3,4,2,1][3,4,2,1,]

<小时/>

[2, 2, 1, 4, ]

[2, 4, 1, 3, ]

[2, 4, 1, 3, ]

[1, 3, 2, 1, ]

[3, 4, 2, 1, ]

提前致谢!

Answer 1

为了使您的算法正常工作，您的树不得共享节点。

但是，在 allBinaryTrees() 的内部循环中，您创建具有共享节点的树:

    for (Node lt : possibleLeftSubtrees) {
        for (Node rt : possibleRightSubtrees) {
            // make a tree of a node with lt and rt as subtrees,
            // and add it to the result
            result.add(new Node(i,lt, rt));
        }
    }

如果 possibleLeftSubtrees 有一个节点，而 possibleRightSubtrees 有两个节点，则您将创建两棵共享左节点的结果树。

<小时/>

顺便说一句，您的 Tree.clone() 方法已损坏:

Node b = new Node(2);
Node a = new Node(1, b, null);
b.setParent(a);
System.out.println(a.clone());

将引发一个StackOverflowError，因为克隆a意味着克隆其左子b，这意味着克隆其父a > 这意味着...添加无穷大。