Подходящая структура данных для детей из дерева - PullRequest
Новая
       34

Подходящая структура данных для детей из дерева

0 голосов
/ 10 сентября 2018

Итак, я хотел реализовать строгое определение дерева - графа без циклов. Рекурсивно это узел с 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) )

  • Сумка: неупорядоченная коллекция, которая позволяет добавлять элементы, но не допускает их удаления. Похоже, это не согласуется с тем фактом, что дочерние элементы дерева можно удалить.

Существуют ли другие неупорядоченные структуры данных, которые могут быть более подходящими? Я уверен, что это было проблемой раньше, и каковы общие решения?

Спасибо!

1 Ответ

0 голосов
/ 10 сентября 2018

Если порядок детей не имеет значения, и дублирование разрешено, я думаю, 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());
        }
    }
}
...