Структура данных дерево в Java


Введение

У меня это общая структура данных дерево, которое не накладывает никаких ограничений на топологию: любой не-листовой узел может иметь столько непосредственные дети по желанию. Кроме того, нет никаких ограничений на то, как глубоко каждая ветвь идет либо.

Код

TreeNode.java

package net.coderodde.util;

import java.util.LinkedHashSet;
import java.util.Objects;
import java.util.Set;

/**
 * This class implements a general tree node.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Mar 27, 2018)
 * @param <E> the stored element type.
 */
public final class TreeNode<E> {

    /**
     * The element stored in this tree node. May be {@code null}.
     */
    private E element;

    /**
     * The parent node of this tree node. We need this in order to make sure
     * that there is no cycles, i.e., a node cannot be both its own predecessor
     * and successor.
     * 
     * This field is kept package-private so that the TODO
     */
    TreeNode<E> parent;

    /**
     * The set of child nodes. We will use {@link java.util.LinkedHashSet} for 
     * the child set implementation. While this allows adding/removing in 
     * average constant time, the child nodes will be ordered by their 
     * insertion order, i.e., if 'A' is first added to a specific tree node 'N', 
     * after which 'B' is added to 'N', when iterating over children of 'N', 'A'
     * will be always returned before 'B'.
     * 
     * This field is kept package-private so that the 
     * {@link TreeNodeChildrenView} can access the actual set of child tree
     * nodes.
     */
    Set<TreeNode<E>> children;

    /**
     * The view object over this tree node's children. It is kept 
     * package-private so that {@link TreeNodeChildrenView} can access it.
     */
    TreeNodeChildrenView<E> childrenView;

    /**
     * The constructor of this tree node.
     * 
     * @param element the element to set to this tree node. May be {@code null}.
     */
    TreeNode(E element) {
        this.element = element;
        this.parent = null;
    }

    /**
     * Adds a child tree node to this tree node. The new child will have a given
     * element.
     * 
     * @param element the element to set. May be {@code null}.
     * @return the newly created child node so that the client programmer can
     *         operate on it.
     */
    public TreeNode<E> addChild(E element) {
        if (children == null) {
            children = new LinkedHashSet<>();
            childrenView = new TreeNodeChildrenView<>(this);
        }

        TreeNode<E> child = new TreeNode<>(element);
        child.parent = this;
        children.add(child);
        return child;
    }

    /**
     * Returns the children of this tree node. The client programmer can
     * directly operate on this set, adding/removing tree nodes.
     * 
     * @return the children of this tree node. 
     */
    public TreeNodeChildrenView<E> getChildren() {
        if (children == null) {
            children = new LinkedHashSet<>();
            childrenView = new TreeNodeChildrenView<>(this);
        }

        return childrenView;
    }

    public E getElement() {
        return element;
    }

    public void setElement(E element) {
        this.element = element;
    }

    @Override
    public String toString() {
        return Objects.toString(element);
    }
}

TreeNodeChildrenView.java

package net.coderodde.util;

import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Objects;
import java.util.Set;

/**
 * This class provides a view over a tree nodes children. The client programmer
 * can manipulate it to his/her own liking.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Mar 27, 2018)
 * @param <E> the tree node element type.
 */
public final class TreeNodeChildrenView<E> implements Set<TreeNode<E>> {

    /**
     * The tree node that owns this view.
     */
    private final TreeNode<E> ownerTreeNode;

    /**
     * Constructs this view for the input tree node.
     * 
     * @param ownerTreeNode the tree node this children view belongs to.
     */
    TreeNodeChildrenView(TreeNode<E> ownerTreeNode) {
        this.ownerTreeNode = ownerTreeNode;
    }

    /**
     * Returns the number of children in this view.
     * 
     * @return the number of children.
     */
    @Override
    public int size() {
        return ownerTreeNode.children.size();
    }

    /**
     * Returns {@code true} only if this view has no child tree nodes.
     * 
     * @return {@code true} if this view has no child tree nodes. 
     */
    @Override
    public boolean isEmpty() {
        return ownerTreeNode.children.isEmpty();
    }

    /**
     * Returns {@code true} only if this tree node children view contains a 
     * given tree node.
     * 
     * @param o the query tree node.
     * @return {@code true} only if {@code o} is in this view.
     */
    @Override
    public boolean contains(Object o) {
        if (o == null) {
            return false;
        } else if (!(o instanceof TreeNode)) {
            return false;
        } else {
            return ownerTreeNode.children.contains(o);
        }
    }

    /**
     * Returns an iterator over this view's children.
     * 
     * @return an iterator over this view's children.
     */
    @Override
    public Iterator<TreeNode<E>> iterator() {
        return ownerTreeNode.children.iterator();
    }

    @Override
    public boolean add(TreeNode<E> treeNode) {
        Objects.requireNonNull(treeNode, "The input tree node is null.");
        checkInputTreeNodeIsNotPredecessorOfThisTreeNode(treeNode);

        // Return {@code false} whenever the input tree node is already in this
        // tree.
        if (ownerTreeNode.children.contains(treeNode)) {
            return false;
        }

        // If the input tree node belongs to a parent, disconnect it from it:
        if (treeNode.parent != null) {
            treeNode.parent.children.remove(treeNode);
        }

        // Connect the input tree node as the child of this view.
        ownerTreeNode.children.add(treeNode);
        treeNode.parent = ownerTreeNode;
        return true;
    }

    @Override
    public boolean remove(Object o) {
        if (o == null) {
            return false;
        } else if (!(o instanceof TreeNode)) {
            return false;
        }

        TreeNode<E> treeNode = (TreeNode<E>) o;
        treeNode.parent = null;
        return ownerTreeNode.children.remove(treeNode);
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        for (Object o : c) {
            if (!contains(o)) {
                return false;
            }
        }

        return true;
    }

    @Override
    public boolean addAll(Collection<? extends TreeNode<E>> c) {
        boolean modified = false;

        for (TreeNode<E> treeNode : c) {
            if (add(treeNode)) {
                modified = true;
            }
        }

        return modified;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        int numberOfChildrenBefore = size();

        Set<?> collectionAsSet = 
                (c instanceof HashSet) ? (Set<?>) c : new HashSet(c);

        Iterator<TreeNode<E>> iterator =
                ownerTreeNode.children.iterator();

        while (iterator.hasNext()) {
            TreeNode<E> currentTreeNode = iterator.next();

            if (!collectionAsSet.contains(currentTreeNode)) {
                iterator.remove();
            }
        }

        return size() < numberOfChildrenBefore;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        return ownerTreeNode.children.removeAll(c);
    }

    @Override
    public void clear() {
        ownerTreeNode.children.clear();
    }

    @Override
    public Object[] toArray() {
        throw new UnsupportedOperationException();
    }

    @Override
    public <T> T[] toArray(T[] a) {
        throw new UnsupportedOperationException();
    }

    /**
     * Checks that the input tree node is not a predecessor of itself.
     * 
     * @param treeNode the tree node to check.
     */
    private void checkInputTreeNodeIsNotPredecessorOfThisTreeNode(
            TreeNode<E> treeNode) {
        TreeNode<E> currentTreeNode = ownerTreeNode;

        while (currentTreeNode != null) {
            if (currentTreeNode == treeNode) {
                throw new IllegalStateException(
                        "Trying to create a cycle in this tree.");
            }

            currentTreeNode = currentTreeNode.parent;
        }
    }
}

Tree.java

package net.coderodde.util;

/**
 * This class implements a general tree data structure.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Mar 27, 2018)
 * @param <E> the tree node element type.
 */
public final class Tree<E> {

    /**
     * The root node. This node does not logically belong to this tree as it
     * merely provides a way of having multiple "roots". 
     */
    private final TreeNode<E> pseudoroot = new TreeNode<>(null);

    /**
     * Returns the root node. It is <b>not</b> considered to belong to the
     * actual tree. We merely want to have a way of attaching nodes to it.
     * 
     * @return the pseudoroot of this tree.
     */
    public TreeNode<E> getPseudoRoot() {
        return pseudoroot;
    }

    @Override
    public String toString() {
        return "";
    }
}

TreeToStringConverter.java

package net.coderodde.util;

/**
 * This interface defines API for converting generic trees to a textual format.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Apr 7, 2018)
 */
public interface TreeToStringConverter<E> {

    /**
     * Converts the input tree into a textual format.
     * 
     * @param tree the tree to convert.
     * @return a textual representation of the input tree according to  the
     *         implementing format.
     */
    public String toString(Tree<E> tree);
}

SimpleTreeToStringConverter.java

package net.coderodde.util;

import java.util.Objects;

/**
 * This class implements a simple converter from a 
 * {@link net.coderodde.util.Tree} to a string.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Apr 7, 2018)
 */
public final class SimpleTreeToStringConverter<E>
implements TreeToStringConverter<E> {

    /**
     * {@inheritDoc }
     */
    @Override
    public String toString(Tree<E> tree) {
        Objects.requireNonNull(tree, "The input tree is null.");
        StringBuilder stringBuilder = new StringBuilder();        

        for (TreeNode<E> root : tree.getPseudoRoot().getChildren()) {
            toString(stringBuilder, root, 0);
        }

        return stringBuilder.toString();
    }

    // Implements the actual conversion procedure.
    private void toString(StringBuilder stringBuilder, 
                          TreeNode<E> node,
                          int nodeDepth) {
        for (int i = 0; i < nodeDepth; i++) {
            stringBuilder.append(' ');
        }

        stringBuilder.append(Objects.toString(node.getElement()))
                     .append('\n');

        for (TreeNode<E> child : node.getChildren()) {
            toString(stringBuilder, child, nodeDepth + 1);
        }
    }
}

Demo.java

package net.coderodde.util;

public final class Demo {

    public static void main(String[] args) {
        Tree<Integer> tree = new Tree<>();

        // Roots:
        TreeNode<Integer> root1 = tree.getPseudoRoot().addChild(1);
        TreeNode<Integer> root2 = tree.getPseudoRoot().addChild(2);

        // Children of 1st root:
        TreeNode<Integer> root1Child1 = root1.addChild(11);
        TreeNode<Integer> root1Child2 = root1.addChild(12);

        // Children of 2nd root:
        TreeNode<Integer> root2Child1 = root2.addChild(21);
        TreeNode<Integer> root2Child2 = root2.addChild(22);
        TreeNode<Integer> root2Child3 = root2.addChild(23);

        // Children of 2nd root, second child:
        TreeNode<Integer> root2Child2Child1 = root2Child2.addChild(221);
        TreeNode<Integer> root2Child2Child2 = root2Child2.addChild(222);

        // Print the entire tree in a simple format:
        System.out.println("(Indentation communicates node depth.)");
        System.out.println(new SimpleTreeToStringConverter().toString(tree));
    }
}

Пример вывода

(Indentation communicates node depth.) 1 11 12 2 21 22 221 222 23

(Проект размещен здесь. Он содержит модульные тесты, которые проходят.)

Критика запросу

Все, что приходит на ум, я хотел бы услышать ваши предложения.



1982
1
задан 7 апреля 2018 в 05:04 Источник Поделиться
Комментарии
2 ответа

Некоторые неупорядоченные мысли:


  • В pseudoroot построить нарушает закон наименьшего удивления (по крайней мере для меня): из дерева, я ожидаю один корень, который уже содержит данные. Если мне нужно несколько из них, я использую коллекцию деревьев.

  • Хорошая идея для инкапсуляции сбора ребенка в отдельный класс.

  • Почему дерево финале? Кто-то может захотеть создать class SomethingTree extends Tree<Something> (примечание: не меня, а кого-то ;-)). Я думаю, сделать класс Final вам нужен конкретный повод (как правило, безопасность) и я не могу различить его здесь.

  • Предложение расширение: Добавить итератор или поток на глубину и ширину обход (я использую их все время на свою реализацию, дерево)

  • В целом: красиво сделано

И моя личная благодарность Вам за размещение то, что не "Программирование-вызов" на codereview :-)

2
ответ дан 9 апреля 2018 в 08:04 Источник Поделиться

TreeNode.java

1) где равен()
Вы кладете ребенка TreeNodeв Set но не реализовать equals(). Даже если ты имел в виду, что TreeNode экземпляры равны, если ссылки указывают на один объект, вы должны заявить об этом прямо, а не полагаться на значения по умолчанию выполнению в Object - это может измениться в будущем (или прошлом) версий JRE. Как правило, equals() должны всегда быть четко реализованы, если экземпляры класса помещаются в коллекцию (любую коллекцию, как все реализовать какой-то contains запроса, но особенно в Set что подразумевает понятие uniqeness)

2) нулевой инициализации переменных экземпляра
Я вижу две проблемы: одна из характеристик: вы не quering если установить значение null каждый раз, когда ребенок будет добавлен и каждый раз, когда представление просил. Вторая большая проблема заключается в том, что этот код не является потокобезопасным. несколько потоков, которые будут пытаться добавьте первый ребенок в одном и том же узле можно переопределить операции друг друга. Самое простое решение-инициализировать children экземпляр переменной в TreeNodeС конструктора.

Вы были, вероятно, пытаются реализовать отложенную инициализацию ДП, но то, что ты спас? создание пустого Set? это не дорогостоящая операция в производительности или условий памяти.

теперь, childrenView это совсем другая история. если я правильно понимаю, это необходимо только в представлении, просил (т. е. в getChildren()) так зачем создавать экземпляр, когда ребенок добавляется?

TreeNodeChildrenView.java

Сначала я был buffled, почему вы создали эту функцию. Я думаю, я понимаю, что вы хотели сделать некоторые проверки, когда клиент добавляет или удаляет дочерние узлы. Однако, у вас уже есть addChild() в TreeNode так почему бы не добавить все другие методы есть? (вы можете даже имеют перегруженную версию addChild() что можно TreeNode арг) кажется более естественным местом для меня. Что касается самого класса:

1) добавить параметризированный универсальный
Вместо реализации Set интерфейс, я бы улучшить его, добавив недостающие дженериков методов. вместо contains(Object o) пойти на contains(TreeeNode<E> node) и пусть компилятор обеспечивает безопасность типов

2) внутренний класс
TreeNodeChildrenView должны быть перемещены для внутреннего нестатического класса Treenode. ИМО - идеально подходит для этого случая - каждый вид живет только в рамках (ненулевой!) экземпляр из включающего класса.

1
ответ дан 9 апреля 2018 в 12:04 Источник Поделиться