适用于树的子项的数据结构

Question

所以我想实现树的严格定义 - 没有任何循环的图形。递归地，它是具有n个子树/子节点的节点。因此，每个节点将需要某种数据结构以将其与其n个子树相关联。

• 数组，列表，序列，有序集合：儿童实际上没有排序。有一种特殊类型的树称为“有序树”，它将某种排序与节点的子节点相关联，但这似乎不合适。 例如：

  Tree(3,
    Tree(4), 
    Tree(5)
  ) == Tree(3,
    Tree(5),
    Tree(4)
  )

• 设置：未订购集，但它也不包含重复项。在功能上，如果Tree（3）== Tree（3），它是有意义的，但我们想要重复的信息，因为一个节点可以有多个Tree（3）作为子树。 例如：

  Tree(3,
    Tree(4)
  ) != Tree(3,
    Tree(4),
    Tree(4)
  )

• 袋子：无序集合，允许添加物品，但不允许任何移除。这似乎与树木中的孩子可以被移除的事实不一致。

是否有其他无序的数据结构可能更合适？我确定这是一个问题，有什么常见的解决方案？

谢谢！

Answer 1

如果孩子的命令无所谓并且允许重复，我认为List就足够了。

由于没有保证，孩子将被列入清单内或以正确的顺序插入，并且由于允许重复，因此无法使用Set，我们可以定义如何比较两棵树，以便可以比较Tree(3, ArrayList(Tree(4), Tree(5))和Tree(3, ArrayList(Tree(5), Tree(4))等于。

一种方法是 - 在比较它们是否相等时，我们可以根据它们的值对它们进行排序，并递归地比较它们。

class Tree {
    private Integer value;
    private List<Tree> children;

    // getter for value
    // getter for children

    public Tree(Integer value) {
        this.value = value;
        children = new ArrayList<>();
    }

    @Override
    public boolean equals(Object other) {
        if (other == this) {
            return true;
        }
        if (!(other instanceof Tree)) {
            return false;
        }
        Tree otherTree = (Tree) other;

        return equalUtil(this, otherTree);
    }

    private boolean equalUtil(Tree lhs, Tree rhs) {
        if(lhs == null && rhs == null) {
            return true;
        }

        if(lhs == null || rhs == null) {
            return false;
        }


        if(lhs.children.size() != rhs.children.size()) {
            return false;
        }

        // copying the children into another list to not altering
        // the tree's data ordering
        lhsChildren = lhs.children;
        Collections.sort(lhsChildren, new TreeComparator());

        rhsChildren = rhs.children;
        Collections.sort(rhsChildren, new TreeComparator());

        for(int i = 0; i < lhsChildren.size(); i++) {
            if(!equalUtil(lhsChildren[i], rhsChildren[i])) {
                return false;
            }
        }

        return true;

    }

    static class TreeComparator implements Comparator<Tree> {
        @Override
        public int compare(Tree lhs, Tree rhs) {
            return lhs.getValue().compareTo(rhs.getValue());
        }
    }
}