更改变量也会更改先前分配的变量

Question

我确定这是一个基本的逻辑错误，但我似乎无法修复它。在使用未排序（后序）和排序（中序）列表创建树之前，我正在对 GenericSimpleArrayList 进行排序。当我对其中一个列表进行排序时，它会同时对它们进行排序吗？我不知道为什么。

public static <AnyType extends Comparable<? super AnyType>> BinaryNode<AnyType>constructBST ( GenericSimpleArrayList<AnyType> postorder ){


    GenericSimpleArrayList <AnyType> g = postorder;

    quicksort(postorder, new SortFunctor()); //this is where i sort the list.

    GenericSimpleArrayList <AnyType> inorder = postorder;
    return constructTree(inorder, g);

}

谁能帮我解决这个问题？当我只对后序进行排序时，为什么它同时对 g 和后序进行排序？谢谢

编辑：添加了 constructTree。

public static <AnyType> BinaryNode<AnyType> constructTree(GenericSimpleArrayList<AnyType> inorder, GenericSimpleArrayList<AnyType> postorder) {
    int nodes = postorder.size();

    AnyType root = postorder.get(nodes-1);
    BinaryNode<AnyType> left = null;
    BinaryNode<AnyType> right = null;

    if (nodes > 1) {
        int rootPos = 0;
        for (int loop = 0; loop <= nodes-1; loop++) {

            if (inorder.get(loop).equals(root)) {
                rootPos = loop;
                //System.out.println(loop);
            } else {
                //System.out.println("Not found at pos: " + loop);
            }
        }

        if (rootPos != 0) {
            GenericSimpleArrayList <AnyType> leftInorder = new GenericSimpleArrayList();//(AnyType) new Object[rootPos];
            GenericSimpleArrayList <AnyType> leftPostorder = new GenericSimpleArrayList();//(AnyType[]) new Object[rootPos];
            for (int loop = 0; loop < rootPos; loop++) {
                leftInorder.add(inorder.get(loop));
                leftPostorder.add(postorder.get(loop));
            }
            left = constructTree(leftInorder, leftPostorder );
        }

        if (rootPos < nodes-1){
            GenericSimpleArrayList <AnyType> rightInorder = new GenericSimpleArrayList();//(AnyType[]) new Object[nodes - rootPos - 1];
            GenericSimpleArrayList <AnyType> rightPostorder = new GenericSimpleArrayList();//(AnyType[]) new Object[rightInorder.length];
            for (int loop = 0; loop < nodes-rootPos-1; loop++){
                rightInorder.add(inorder.get(rootPos + loop + 1));
                rightPostorder.add(postorder.get(rootPos + loop));
            }

            right = constructTree(rightInorder, rightPostorder);
        }


    }

    return new BinaryNode<AnyType>(root, left, right);

}

Answer 1

Why does it sort both g and postorder when I only sort postorder?

GenericSimpleArrayList <AnyType> g = postorder;

postorder 是对对象的引用。当您复制此 reference 时，您现在有两个 references 到一个对象。但是仍然只有一个对象。

我不知道 API 到您的自定义 ArrayList，但我想您可以做到

GenericSimpleArrayList<AnyType> g = new GenericSimpleArrayList<AnyType>(postorder);

或

GenericSimpleArrayList<AnyType> g = new GenericSimpleArrayList<AnyType>();
for(AnyType at: postorder)
    g.add(at);

您的排序实用程序很可能会就地对集合进行排序。这对于 sort 函数改变原始列表是很常见的。

如果既要保留原始顺序又要对列表进行排序，我建议先复制一份列表。

另一种方法是使用不同的结构，如 TreeMap 来记录排序后的字符串和原始位置的索引。

Answer 2

GenericSimpleArrayList <AnyType> g = postorder;

GenericSimpleArrayList <AnyType> inorder = postorder;

在这两个语句中，所有三个变量都将引用最初由 postorder 持有的相同引用。因为你在一个对象状态下做引用赋值和更新会反映到所有的引用变量中。

constructTree(inorder, g);

因此，当您进行上述调用时，您传递的是相同的引用。

Answer 3

这一行：

GenericSimpleArrayList <AnyType> g = postorder;

您只需为相同对象定义一个新名称g。如果你想让 g 成为一个不同的列表，你需要重新创建它（实际上是调用 构造函数 ）并将 postorder 的内容复制到其中.

更改变量也会更改先前分配的变量

Changing a variable changes the previously assigned variable as well

java

arrays

sorting

binary-search-tree