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

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 是对对象的引用。当您复制此引用 时，您现在有两个引用 到一个对象。但是仍然只有一个对象。

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

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

或

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

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

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

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