对"plain-list-tree-structure"进行排序的算法

Question

对不起，那个主题，我没有找到更好的标题：-）

我有一个树结构，这是我的"节点"类：

public class Categoria implements Serializable {
    private static final long serialVersionUID = 1L;
    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;
    @NotNull
    private String name;
    @OneToMany(cascade=CascadeType.ALL,fetch=FetchType.EAGER)
    @JoinColumn(name = "parent_id")
    private List<Categoria> children = new LinkedList<Categoria>();
    @ManyToOne(fetch=FetchType.LAZY)
    @JoinColumn(
        name = "parent_id",
        insertable=false,
        updatable=false
    )
    private Categoria parent;
    @Transient
    private Integer depth;
    private Integer orderNumber;
... getters, setters, ....
}

不要关心休眠/JPA 注释，它们没有问题，只要想想一个理想的 pojo 世界。

我制作了一个递归方法，该方法构建了一个相邻节点的"普通"列表。所以，想象这棵树：

grandfather
 |_ father
    |_ son1
    |_ son2
 |_ uncle
grandmother
 |_ mother

我们将得到一个这样的结果列表（数字是"深度"）：- 祖父 （1）- 父亲 （2）- 儿子1 （3）- 儿子2 （3）- 叔叔（2）- 祖母 （1）- 母亲 （2）

一切都很好。

现在我想让我的用户编辑节点排序（在相同深度节点之间），我的意思是：如果我想要上面列表中的"son2"在"son1"之前怎么办？

所以我很难添加一个"orderNumber"属性：所有orderNumber最初都是0。然后我的用户将 son1 的订单编号设置为 99，将 son2 的订单编号设置为 88。

问题是：如何重新排列结果列表以根据订单号进行排序？

但是等等....我只想对"子列表"进行排序，这样儿子排序绝对与"父亲"和"叔叔"排序无关！

感谢您帮助我们。

编辑：你们都错过了一件事。我没有很好地解释自己。下面是一个示例：

• 祖父（深度：1，订单号：1）
• 父亲（深度：2，订单号：1）
• 儿子1 （深度：3， 订单号：1）
• 儿子2 （深度：3， 订单号：2）
叔
• 叔（深度：2，订单号：2）
• 祖母（深度：1，订单号：2）
• 母（深度：2，订货号：1）

现在我想交换 son1 和 son2，因此结果列表将是：

• 祖父（深度：1，订单号：1）
• 父亲（深度：2，订单号：1）
• 儿子2 （深度：3， 订单号：1）
• 儿子1 （深度：3， 订单号：2）
叔
• 叔（深度：2，订单号：2）
• 祖母（深度：1，订单号：2）
• 母（深度：2，订货号：1）

我如何为此目的实现排序/比较？

Answer 1

让 Categoria 实现 Comparable。创建自定义 compareTo 实现，您可以在其中按深度排序，并按附加 OrderNumber 属性决定的领带排序。这将适用于任何可排序的集合。

但是，根据您使用该树结构解决的问题，可能更适合为您的树实现自定义迭代器，而不是递归创建"列表快照"？

Answer 2

您可以使用 Collections.sort（） 和适当的比较器对子列表进行显式排序。

如果在创建列表时排序已知，则可以使用带有比较器的有序集（如 TreeSet）而不是 LinkedList。因此，插入时将对项目进行排序。

Answer 3

我会让你的类实现Comparable，在compareTo方法中，我会使用字段depth和orderNumber来计算顺序。完成此操作后，您可以使用 Collectoins.sort（） 对列表进行排序。

示例代码：

public class Categoria implements Serializable, Comparable<Categoria> {
    private static final long serialVersionUID = 1L;
    // ... omitting other fields/annotations/getters/setters
    private Integer depth;
    private Integer orderNumber;
    @Override
    public int compareTo(Categoria other) {
        if (depth < other.depth)
            return -1;
        if (depth > other.depth)
            return 1;
        // if we get here the two objects have the same depth, so we compare 
        // based on orderNumber
        if (orderNumber < other.orderNumber)
            return -1;
        if (orderNumber > other.orderNumber)
            return 1;
        return 0;
    }
}

Answer 4

我需要它：

private List<Categoria> getAlberoCategorie(Categoria root, int profondita) {
        List<Categoria> tmpList = new ArrayList<Categoria>();
        root.setProfondita(profondita);
        if ( root.getParent() != null ) {
            Hibernate.initialize(root.getTraduzioni());
            tmpList.add(root);
        }       
        List<Categoria> children = root.getChildren();
        Collections.sort(children, new Comparator<Categoria>() {
            @Override
            public int compare(Categoria o1, Categoria o2) {
                return o1.getOrdinamento().compareTo(o2.getOrdinamento());
            }
        });
        if (!children.isEmpty()) {
            profondita++;
            for (Categoria figlia : children) {
                List<Categoria> discendenza = getAlberoCategorie(figlia,profondita);                
                tmpList.addAll(discendenza);
            }
        }       
        return tmpList;
    }

无论如何，谢谢大家！