Как реализовать древовидную структуру данных в Java? [закрыто]

496

Существует ли какой-либо стандартный класс библиотеки Java для представления дерева в Java?

В частности, мне нужно представить следующее:

  • Поддерево в любом узле может иметь произвольное количество дочерних элементов
  • Каждый узел (после корня) и его потомки будут иметь строковое значение
  • Мне нужно получить все дочерние элементы (своего рода список или массив строк) данного узла и его строковое значение (т. Е. Метод, который будет принимать узел в качестве входных данных и возвращать все строковые значения дочернего узла в качестве выходных данных).

Есть ли какая-либо доступная структура для этого или мне нужно создать свою собственную (если это так, предложения по реализации будут хорошими).

IKL
источник
3
Если вы используете Java 8 и хотите обойти ваши узлы с помощью потоков, фильтрации и т. Д .; тогда вы можете захотеть взглянуть на Дуриан github.com/diffplug/durian
Нед Твигг
1
Вы можете использовать этот API: sourceforge.net/p/treeds4j
Мохамед Эннахди Эль Идрисси

Ответы:

306

Вот:

public class Tree<T> {
    private Node<T> root;

    public Tree(T rootData) {
        root = new Node<T>();
        root.data = rootData;
        root.children = new ArrayList<Node<T>>();
    }

    public static class Node<T> {
        private T data;
        private Node<T> parent;
        private List<Node<T>> children;
    }
}

Это базовая древовидная структура, которую можно использовать для Stringлюбого другого объекта. Довольно просто реализовать простые деревья, чтобы делать то, что вам нужно.

Все, что вам нужно добавить - это методы для добавления, удаления, обхода и конструкторы. Это Nodeосновной строительный блок Tree.

jjnguy
источник
304
Строго говоря, Treeкласс не нужен, потому что каждый Nodeможет рассматриваться как дерево.
Иоахим Зауэр
34
@ Джоа, мне нравится иметь структуру, содержащую корень. Вы можете добавить методы к классу дерева, которые имеют смысл вызывать на дереве, а не на одном узле.
Jjnguy
24
@Justin: например? Это честный вопрос: я не могу думать об одном методе, который имеет смысл для всего дерева, который не имеет смысла для поддерева.
Иоахим Зауэр
22
Я согласен с @Joa, что класс Tree не нужен. Я предпочитаю оставлять рекурсивную природу деревьев явной в коде, не добавляя отдельный класс Tree и последовательно используя класс Node. Вместо этого я называю переменную «дерево» или «корень», если необходимо четко понимать, что вы имеете дело с корневым узлом дерева.
jvdbogae
89
@Joa Я на четыре года старше с тобой полностью согласен. Nix класс дерева.
января
122

Еще одна древовидная структура:

public class TreeNode<T> implements Iterable<TreeNode<T>> {

    T data;
    TreeNode<T> parent;
    List<TreeNode<T>> children;

    public TreeNode(T data) {
        this.data = data;
        this.children = new LinkedList<TreeNode<T>>();
    }

    public TreeNode<T> addChild(T child) {
        TreeNode<T> childNode = new TreeNode<T>(child);
        childNode.parent = this;
        this.children.add(childNode);
        return childNode;
    }

    // other features ...

}

Пример использования:

TreeNode<String> root = new TreeNode<String>("root");
{
    TreeNode<String> node0 = root.addChild("node0");
    TreeNode<String> node1 = root.addChild("node1");
    TreeNode<String> node2 = root.addChild("node2");
    {
        TreeNode<String> node20 = node2.addChild(null);
        TreeNode<String> node21 = node2.addChild("node21");
        {
            TreeNode<String> node210 = node20.addChild("node210");
        }
    }
}

БОНУС
Смотрите полноценное дерево с:

  • итератор
  • поиск
  • Java / C #

https://github.com/gt4dev/yet-another-tree-structure

Grzegorz Dev
источник
2
Просто нашел вашу библиотеку чрезвычайно полезной. Спасибо. Но я хотел бы знать, как реализовать динамическое заполнение древовидной структуры на основе ссылочных отношений между родителем и ребенком. Приведенный пример: у меня есть один участник1, спонсор другого участника2, и участник2, спонсор участника 3 и так далее. Уже есть связь между записями таблиц, но я просто не уверен, что смогу заполнить их деревом, используя вашу библиотеку.
d4v1dv00
1
по состоянию на 2016 г. ссылка не содержит исходных файлов или загрузок
Шарон Бен Ашер
2
На мой взгляд, этот ответ через три года после ответа с более высоким рейтингом является более чистым. Тем не менее, я бы заменил LinkedList на ArrayList для this.children.
HopeKing
1
Я бы использовал Набор для детей.
DPM
Я могу ошибаться, но похоже, что с этой реализацией вы должны вызывать hasNext()перед каждым вызовом, next()чтобы получить действительные результаты. Это не часть Iteratorспецификации.
Роберт Льюис
97

На самом деле в JDK реализована довольно хорошая древовидная структура.

Посмотрите на javax.swing.tree , TreeModel и TreeNode . Они предназначены для использования с ним, JTreePanelно на самом деле это довольно хорошая реализация дерева, и ничто не мешает вам использовать его без интерфейса Swing.

Обратите внимание, что начиная с Java 9 вы можете не использовать эти классы, поскольку они не будут присутствовать в «Компактных профилях» .

Гарет Дэвис
источник
5
Да, я использовал их в прошлом, и они будут делать все, что вы хотите от дерева. Единственным недостатком, о котором я могу думать, является длина имен их соответствующих классов реализации: DefaultTreeModel и DefaultMutableTreeNode. Многословно, но не так уж и важно, я думаю.
Окончательное Gobblement
4
Хороший способ справиться с этим - создать пару статических методов newModel () и newNode (), а затем статически импортировать их.
Гарет Дэвис
140
Я бы не использовал библиотеки Swing для функций, не связанных с Swing. Это плохая практика кодирования . Вы никогда не знаете, как Swing реализует их деревья, каковы их зависимости и как это может измениться в будущем. Swing - это не служебная библиотека, а библиотека пользовательского интерфейса.
Ясоп
44
Я думаю, что плохая практика кодирования немного грубовата.
Гарет Дэвис
51
javax.swing.tree.TreeModel является общедоступным интерфейсом (в точности как java.util.List) и не будет иметь несовместимых изменений. Дополнительным преимуществом является то, что вы можете легко отлаживать / визуализировать свое дерево во время разработки.
lbalazscs
45

Что насчет этого?

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;

/**
  * @author ycoppel@google.com (Yohann Coppel)
  * 
  * @param <T>
  *          Object's type in the tree.
*/
public class Tree<T> {

  private T head;

  private ArrayList<Tree<T>> leafs = new ArrayList<Tree<T>>();

  private Tree<T> parent = null;

  private HashMap<T, Tree<T>> locate = new HashMap<T, Tree<T>>();

  public Tree(T head) {
    this.head = head;
    locate.put(head, this);
  }

  public void addLeaf(T root, T leaf) {
    if (locate.containsKey(root)) {
      locate.get(root).addLeaf(leaf);
    } else {
      addLeaf(root).addLeaf(leaf);
    }
  }

  public Tree<T> addLeaf(T leaf) {
    Tree<T> t = new Tree<T>(leaf);
    leafs.add(t);
    t.parent = this;
    t.locate = this.locate;
    locate.put(leaf, t);
    return t;
  }

  public Tree<T> setAsParent(T parentRoot) {
    Tree<T> t = new Tree<T>(parentRoot);
    t.leafs.add(this);
    this.parent = t;
    t.locate = this.locate;
    t.locate.put(head, this);
    t.locate.put(parentRoot, t);
    return t;
  }

  public T getHead() {
    return head;
  }

  public Tree<T> getTree(T element) {
    return locate.get(element);
  }

  public Tree<T> getParent() {
    return parent;
  }

  public Collection<T> getSuccessors(T root) {
    Collection<T> successors = new ArrayList<T>();
    Tree<T> tree = getTree(root);
    if (null != tree) {
      for (Tree<T> leaf : tree.leafs) {
        successors.add(leaf.head);
      }
    }
    return successors;
  }

  public Collection<Tree<T>> getSubTrees() {
    return leafs;
  }

  public static <T> Collection<T> getSuccessors(T of, Collection<Tree<T>> in) {
    for (Tree<T> tree : in) {
      if (tree.locate.containsKey(of)) {
        return tree.getSuccessors(of);
      }
    }
    return new ArrayList<T>();
  }

  @Override
  public String toString() {
    return printTree(0);
  }

  private static final int indent = 2;

  private String printTree(int increment) {
    String s = "";
    String inc = "";
    for (int i = 0; i < increment; ++i) {
      inc = inc + " ";
    }
    s = inc + head;
    for (Tree<T> child : leafs) {
      s += "\n" + child.printTree(increment + indent);
    }
    return s;
  }
}
MountainX
источник
5
Как DFS будет реализована на дереве, созданном с использованием этого объекта класса?
Леба-Лев
3
Как бы удаление листа было реализовано с использованием этого класса?
Гедас
2
Для чего будет использовано поле головы?
Acour83
2
Было бы здорово, если бы у этого класса была какая-то документация. Я не совсем понимаю, что методы любят setAsParentили getHeadделают, и это время, когда я действительно мог получить некоторую помощь по древовидным структурам данных. Даже первоисточник документа не имеет комментариев.
катастрофа
23

Я написал небольшую библиотеку, которая обрабатывает общие деревья. Это гораздо легче, чем качели. У меня также есть проект Maven для этого.

Вивин Палиат
источник
3
Я использую его сейчас, работает блестяще. Пришлось значительно изменить исходный код для моих собственных настроек, но это была отличная отправная точка. Спасибо Вивин!
Ясоп
20
public class Tree {
    private List<Tree> leaves = new LinkedList<Tree>();
    private Tree parent = null;
    private String data;

    public Tree(String data, Tree parent) {
        this.data = data;
        this.parent = parent;
    }
}

Очевидно, вы можете добавить служебные методы для добавления / удаления детей.

PaulJWilliams
источник
1
Это говорит о том, что родителем дерева является дерево. Я полагаю, вы пытались создать класс Tree Node.
Мадхур Бхаргава
16

Вы должны начать с определения того, что такое дерево (для домена), лучше всего это сделать сначала определив интерфейс . Не все древовидные структуры являются изменяемыми, возможность добавлять и удалять узлы должна быть дополнительной функцией, поэтому мы создаем дополнительный интерфейс для этого.

Нет необходимости создавать объекты узлов, которые содержат значения , на самом деле я вижу это как главный недостаток и издержки проектирования в большинстве реализаций дерева. Если вы посмотрите на Swing, TreeModelклассы узлов не используются ( DefaultTreeModelиспользуются только TreeNode), поскольку они на самом деле не нужны.

public interface Tree <N extends Serializable> extends Serializable {
    List<N> getRoots ();
    N getParent (N node);
    List<N> getChildren (N node);
}

Изменяемая древовидная структура (позволяет добавлять и удалять узлы):

public interface MutableTree <N extends Serializable> extends Tree<N> {
    boolean add (N parent, N node);
    boolean remove (N node, boolean cascade);
}

Учитывая эти интерфейсы, код, который использует деревья, не должен сильно заботиться о том, как реализовано дерево. Это позволяет использовать как общие, так и специализированные реализации , где вы реализуете дерево, делегируя функции другому API.

Пример: структура дерева файлов

public class FileTree implements Tree<File> {

    @Override
    public List<File> getRoots() {
        return Arrays.stream(File.listRoots()).collect(Collectors.toList());
    }

    @Override
    public File getParent(File node) {
        return node.getParentFile();
    }

    @Override
    public List<File> getChildren(File node) {
        if (node.isDirectory()) {
            File[] children = node.listFiles();
            if (children != null) {
                return Arrays.stream(children).collect(Collectors.toList());
            }
        }
        return Collections.emptyList();
    }
}

Пример: общая древовидная структура (основанная на родительских / дочерних отношениях):

public class MappedTreeStructure<N extends Serializable> implements MutableTree<N> {

    public static void main(String[] args) {

        MutableTree<String> tree = new MappedTreeStructure<>();
        tree.add("A", "B");
        tree.add("A", "C");
        tree.add("C", "D");
        tree.add("E", "A");
        System.out.println(tree);
    }

    private final Map<N, N> nodeParent = new HashMap<>();
    private final LinkedHashSet<N> nodeList = new LinkedHashSet<>();

    private void checkNotNull(N node, String parameterName) {
        if (node == null)
            throw new IllegalArgumentException(parameterName + " must not be null");
    }

    @Override
    public boolean add(N parent, N node) {
        checkNotNull(parent, "parent");
        checkNotNull(node, "node");

        // check for cycles
        N current = parent;
        do {
            if (node.equals(current)) {
                throw new IllegalArgumentException(" node must not be the same or an ancestor of the parent");
            }
        } while ((current = getParent(current)) != null);

        boolean added = nodeList.add(node);
        nodeList.add(parent);
        nodeParent.put(node, parent);
        return added;
    }

    @Override
    public boolean remove(N node, boolean cascade) {
        checkNotNull(node, "node");

        if (!nodeList.contains(node)) {
            return false;
        }
        if (cascade) {
            for (N child : getChildren(node)) {
                remove(child, true);
            }
        } else {
            for (N child : getChildren(node)) {
                nodeParent.remove(child);
            }
        }
        nodeList.remove(node);
        return true;
    }

    @Override
    public List<N> getRoots() {
        return getChildren(null);
    }

    @Override
    public N getParent(N node) {
        checkNotNull(node, "node");
        return nodeParent.get(node);
    }

    @Override
    public List<N> getChildren(N node) {
        List<N> children = new LinkedList<>();
        for (N n : nodeList) {
            N parent = nodeParent.get(n);
            if (node == null && parent == null) {
                children.add(n);
            } else if (node != null && parent != null && parent.equals(node)) {
                children.add(n);
            }
        }
        return children;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        dumpNodeStructure(builder, null, "- ");
        return builder.toString();
    }

    private void dumpNodeStructure(StringBuilder builder, N node, String prefix) {
        if (node != null) {
            builder.append(prefix);
            builder.append(node.toString());
            builder.append('\n');
            prefix = "  " + prefix;
        }
        for (N child : getChildren(node)) {
            dumpNodeStructure(builder, child, prefix);
        }
    }
}
Питер Уолсер
источник
1
Я сталкиваюсь с проблемой, когда следую этой структуре, когда делаю tree.add ("A", "B"); tree.add ("A", "C"); tree.add ("C", "D"); tree.add ("E", "A"); E является родителем A Как мы можем это сделать?
saNiks
1
Привет, saNicks! В приведенном выше коде была ошибка, из-за которой последнее отношение не добавлялось. Теперь это исправлено, и я также добавил ненулевые проверки и (что более важно): циклические проверки, которые предотвращают нарушение древовидной структуры (добавление кода или одного из его предков в качестве дочернего элемента к себе). Спасибо за подсказку!
Питер Уолсер,
1
Я исправил ошибку, если кто-то ищет исправление для этой ошибки. Что вам нужно сделать, это посмотреть, если метод add возвращает false, и если он ложный, просто создайте временный новый LinkedHashSet <N> и клонируйте список узлов дерева в него, тогда вы можете очистить дерево, добавьте родительский узел, который не был добавлен на предыдущем шаге, а затем добавьте все родительский узел tempNode обратно в родительское дерево ... Хотя, спасибо за структуру!
saNiks
2
Просто удалите эти бесполезные публичные модификаторы из ваших интерфейсов.
Хамедз
1
Как я могу создать массив JSON из этого
Pawan Pandey
12

Ни один ответ не упоминает слишком упрощенный, но работающий код, так что вот оно:

public class TreeNodeArray<T> {
    public T value;
    public final  java.util.List<TreeNodeArray<T>> kids =  new java.util.ArrayList<TreeNodeArray<T>>();
}
peenut
источник
10

Вы можете использовать любой XML API Java в качестве Document и Node. Поскольку XML представляет собой древовидную структуру со строками

Раджа Нагендра Кумар
источник
5
Отличная идея, мы могли бы использовать в памяти XML-схему, используя dom4j + jaxen xpath для поиска узлов.
Бен Рума Зид
8

Если вы делаете кодирование на доске, собеседование или даже просто планируете использовать дерево, многословия их немного.

Далее следует сказать, что причина, по которой дерево не существует, как, скажем, a Pair(о котором можно сказать то же самое), заключается в том, что вы должны инкапсулировать свои данные в классе, используя его, и самая простая реализация выглядит следующим образом:

/***
/* Within the class that's using a binary tree for any reason. You could 
/* generalize with generics IFF the parent class needs different value types.
 */
private class Node {
  public String value;
  public Node[] nodes; // Or an Iterable<Node> nodes;
}

Это действительно так для дерева произвольной ширины.

Если вам нужно двоичное дерево, его часто проще использовать с именованными полями:

private class Node { // Using package visibility is an option
  String value;
  Node left;
  Node right;
}

Или, если вы хотели Trie:

private class Node {
  String value;
  Map<char, Node> nodes;
}

Теперь вы сказали, что хотите

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

Это звучит как твоя домашняя работа.
Но так как я достаточно уверен, что любой срок уже прошел ...

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

public class kidsOfMatchTheseDays {
 static private class Node {
   String value;
   Node[] nodes;
 }

 // Pre-order; you didn't specify.
 static public List<String> list(Node node, String find) {
   return list(node, find, new ArrayList<String>(), false);
 }

 static private ArrayList<String> list(
     Node node,
     String find,
     ArrayList<String> list,
     boolean add) {
   if (node == null) {
     return list;
   }
   if (node.value.equals(find)) {
     add = true;
   }
   if (add) {
     list.add(node.value);
   }
   if (node.nodes != null) {
     for (Node child: node.nodes) {
       list(child, find, list, add);
     }
   }
   return list;
 }

 public static final void main(String... args) {
   // Usually never have to do setup like this, so excuse the style
   // And it could be cleaner by adding a constructor like:
   //     Node(String val, Node... children) {
   //         value = val;
   //         nodes = children;
   //     }
   Node tree = new Node();
   tree.value = "root";
   Node[] n = {new Node(), new Node()};
   tree.nodes = n;
   tree.nodes[0].value = "leftish";
   tree.nodes[1].value = "rightish-leafy";
   Node[] nn = {new Node()};
   tree.nodes[0].nodes = nn;
   tree.nodes[0].nodes[0].value = "off-leftish-leaf";
   // Enough setup
   System.out.println(Arrays.toString(list(tree, args[0]).toArray()));
 }
}

Это заставляет вас использовать как:

$ java kidsOfMatchTheseDays leftish
[leftish, off-leftish-leaf]
$ java kidsOfMatchTheseDays root
[root, leftish, off-leftish-leaf, rightish-leafy]
$ java kidsOfMatchTheseDays rightish-leafy
[rightish-leafy]
$ java kidsOfMatchTheseDays a
[]
dlamblin
источник
7

В том же ключе, что и в ответе Гарета, проверьте DefaultMutableTreeNode . Это не универсальный, но в остальном, кажется, отвечает всем требованиям. Хотя он находится в пакете javax.swing, он не зависит от классов AWT или Swing. На самом деле, исходный код на самом деле имеет комментарий// ISSUE: this class depends on nothing in AWT -- move to java.util?

отметка
источник
Лол, как ты вообще наткнулся на этот класс?
Пейсер
7

В Java есть пара древовидных структур данных, таких как DefaultMutableTreeNode в JDK Swing, пакет синтаксического анализатора Tree in Stanford и другие игрушечные коды. Но ничего из этого не достаточно, но достаточно мало для общего назначения.

Проект Java-дерева пытается обеспечить другую структуру данных общего назначения в Java. Разница между этим и другими

  • Абсолютно бесплатно. Вы можете использовать его где угодно (кроме домашней работы: P)
  • Маленький, но достаточно общий. Я поместил всю структуру данных в один файл класса, чтобы его было легко скопировать / вставить.
  • Не просто игрушки. Мне известны десятки кодов дерева Java, которые могут обрабатывать только двоичные деревья или ограниченные операции. Этот TreeNode гораздо больше, чем это. Он предоставляет различные способы посещения узлов, такие как предварительный заказ, почтовый заказ, первая ширина, листья, путь к корню и т. Д. Кроме того, итераторы также предусмотрены для достаточности.
  • Дополнительные утилиты будут добавлены. Я готов добавить больше операций, чтобы сделать этот проект всеобъемлющим, особенно если вы отправляете запрос через github.
Ифань Пэн
источник
5

Поскольку вопрос требует доступной структуры данных, дерево может быть построено из списков или массивов:

Object[] tree = new Object[2];
tree[0] = "Hello";
{
  Object[] subtree = new Object[2];
  subtree[0] = "Goodbye";
  subtree[1] = "";
  tree[1] = subtree;
}

instanceof может использоваться для определения того, является ли элемент поддеревом или терминальным узлом.

Олате
источник
2
Довольно некрасиво. И не работает, если ваши объекты данных могут быть массивами или списками.
user686249 12.06.15
1
Я согласен, что это некрасиво. ObjectЫ будет либо объекты листа (например, Stringс) или ветви (представленные массивами). И это работает: этот код скомпилируется, и он создает небольшое дерево Strings.
Олат
5
public abstract class Node {
  List<Node> children;

  public List<Node> getChidren() {
    if (children == null) {
      children = new ArrayList<>();
    }
    return chidren;
  }
}

Столь же простой, как это получается, и очень простой в использовании. Чтобы использовать это, расширьте это:

public class MenuItem extends Node {
  String label;
  String href;
  ...
}
Bretter
источник
3

Например :

import java.util.ArrayList;
import java.util.List;



/**
 * 
 * @author X2
 *
 * @param <T>
 */
public class HisTree<T> 
{
    private Node<T> root;

    public HisTree(T rootData) 
    {
        root = new Node<T>();
        root.setData(rootData);
        root.setChildren(new ArrayList<Node<T>>());
    }

}

class Node<T> 
{

    private T data;
    private Node<T> parent;
    private List<Node<T>> children;

    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    public Node<T> getParent() {
        return parent;
    }
    public void setParent(Node<T> parent) {
        this.parent = parent;
    }
    public List<Node<T>> getChildren() {
        return children;
    }
    public void setChildren(List<Node<T>> children) {
        this.children = children;
    }
}
JAN
источник
3

В прошлом я просто использовал для этого вложенную карту. Это то, что я использую сегодня, это очень просто, но соответствует моим потребностям. Может быть, это поможет другому.

import com.fasterxml.jackson.annotation.JsonValue;
import com.fasterxml.jackson.databind.ObjectMapper;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

/**
 * Created by kic on 16.07.15.
 */
public class NestedMap<K, V> {
    private final Map root = new HashMap<>();

    public NestedMap<K, V> put(K key) {
        Object nested = root.get(key);

        if (nested == null || !(nested instanceof NestedMap)) root.put(key, nested = new NestedMap<>());
        return (NestedMap<K, V>) nested;
    }

    public Map.Entry<K,V > put(K key, V value) {
        root.put(key, value);

        return (Map.Entry<K, V>) root.entrySet().stream().filter(e -> ((Map.Entry) e).getKey().equals(key)).findFirst().get();
    }

    public NestedMap<K, V> get(K key) {
        return (NestedMap<K, V>) root.get(key);
    }

    public V getValue(K key) {
        return (V) root.get(key);
    }

    @JsonValue
    public Map getRoot() {
        return root;
    }

    public static void main(String[] args) throws Exception {
        NestedMap<String, Integer> test = new NestedMap<>();
        test.put("a").put("b").put("c", 12);
        Map.Entry<String, Integer> foo = test.put("a").put("b").put("d", 12);
        test.put("b", 14);
        ObjectMapper mapper = new ObjectMapper();
        System.out.println(mapper.writeValueAsString(test));

        foo.setValue(99);
        System.out.println(mapper.writeValueAsString(test));

        System.out.println(test.get("a").get("b").getValue("d"));
    }
}
KIC
источник
3

Я написал небольшой класс TreeMap, основанный на HashMap, который поддерживает добавление путей:

import java.util.HashMap;
import java.util.LinkedList;

public class TreeMap<T> extends LinkedHashMap<T, TreeMap<T>> {

    public void put(T[] path) {
        LinkedList<T> list = new LinkedList<>();
        for (T key : path) {
            list.add(key);
        }
        return put(list);
    }

    public void put(LinkedList<T> path) {
        if (path.isEmpty()) {
            return;
        }
        T key = path.removeFirst();
        TreeMap<T> val = get(key);
        if (val == null) {
            val = new TreeMap<>();
            put(key, val);
        }
        val.put(path);
    }

}

Его можно использовать для хранения дерева вещей типа «T» (универсального), но (пока) не поддерживается хранение дополнительных данных в его узлах. Если у вас есть такой файл:

root, child 1
root, child 1, child 1a
root, child 1, child 1b
root, child 2
root, child 3, child 3a

Затем вы можете сделать это дерево, выполнив:

TreeMap<String> root = new TreeMap<>();
Scanner scanner = new Scanner(new File("input.txt"));
while (scanner.hasNextLine()) {
  root.put(scanner.nextLine().split(", "));
}

И вы получите красивое дерево. Это должно быть легко адаптироваться к вашим потребностям.

mevdschee
источник
2

Вы можете использовать класс HashTree, включенный в Apache JMeter, который является частью проекта Jakarta.

Класс HashTree включен в пакет org.apache.jorphan.collections. Хотя этот пакет не выпущен за пределами проекта JMeter, вы можете получить его легко:

1) Загрузите исходники JMeter .

2) Создать новый пакет.

3) Скопируйте на него / src / jorphan / org / apache / jorphan / collection /. Все файлы, кроме Data.java

4) Скопируйте также /src/jorphan/org/apache/jorphan/util/JOrphanUtils.java

5) HashTree готов к использованию.

Дэвид
источник
2

В Java нет конкретной структуры данных, которая бы соответствовала вашим требованиям. Ваши требования довольно специфичны, и для этого вам нужно разработать собственную структуру данных. Глядя на ваши требования, любой может сказать, что вам нужно некое n-арное дерево с определенными функциями. Вы можете спроектировать свою структуру данных следующим образом:

  1. Структура узла дерева будет похожа на содержимое узла и список дочерних элементов: class Node {String value; Список детей;}
  2. Вам нужно получить дочерние элементы заданной строки, поэтому у вас может быть 2 метода: 1: Node searchNode (String str) вернет узел, который имеет то же значение, что и заданный ввод (используйте BFS для поиска) 2: Список getChildren (String str): этот метод будет внутренне вызывать searchNode, чтобы получить узел, имеющий ту же строку, а затем он создаст список всех строковых значений потомков и вернет их.
  3. Вам также потребуется вставить строку в дерево. Вам нужно будет написать один метод, скажем void insert (String parent, String value): он снова будет искать узел, имеющий значение, равное parent, а затем вы можете создать узел с данным значением и добавить его в список потомков найденного родителя. ,

Я хотел бы предложить, вы пишете структуру узла в одном классе, как Class Node {String value; Перечислите дочерние элементы;} и все другие методы, такие как search, insert и getChildren, в другом классе NodeUtils, чтобы вы также могли передать корень дерева для выполнения операций над определенным деревом, например: class NodeUtils {public static Node search (Node root, String value)) {// выполнить BFS и вернуть Node}

Аман Растоги
источник
2
    // TestTree.java
// A simple test to see how we can build a tree and populate it
//
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.tree.*;

public class TestTree extends JFrame {

  JTree tree;
  DefaultTreeModel treeModel;

  public TestTree( ) {
    super("Tree Test Example");
    setSize(400, 300);
    setDefaultCloseOperation(EXIT_ON_CLOSE);
  }

  public void init( ) {
    // Build up a bunch of TreeNodes. We use DefaultMutableTreeNode because the
    // DefaultTreeModel can use it to build a complete tree.
    DefaultMutableTreeNode root = new DefaultMutableTreeNode("Root");
    DefaultMutableTreeNode subroot = new DefaultMutableTreeNode("SubRoot");
    DefaultMutableTreeNode leaf1 = new DefaultMutableTreeNode("Leaf 1");
    DefaultMutableTreeNode leaf2 = new DefaultMutableTreeNode("Leaf 2");

    // Build our tree model starting at the root node, and then make a JTree out
    // of it.
    treeModel = new DefaultTreeModel(root);
    tree = new JTree(treeModel);

    // Build the tree up from the nodes we created.
    treeModel.insertNodeInto(subroot, root, 0);
    // Or, more succinctly:
    subroot.add(leaf1);
    root.add(leaf2);

    // Display it.
    getContentPane( ).add(tree, BorderLayout.CENTER);
  }

  public static void main(String args[]) {
    TestTree tt = new TestTree( );
    tt.init( );
    tt.setVisible(true);
  }
}
Тони Нарлох
источник
3
Пожалуйста, не просто сбрасывайте код - объясните, что он делает, и особенно почему он отличается (лучше), чем все остальные ответы.
Ян Догген
2

Я написал библиотеку дерева, которая прекрасно работает с Java8 и не имеет других зависимостей. Он также дает свободную интерпретацию некоторых идей из функционального программирования и позволяет отображать / фильтровать / удалять / искать во всем дереве или поддеревьях.

https://github.com/RutledgePaulV/prune

Реализация не делает ничего особенного с индексированием, и я не отошел от рекурсии, поэтому возможно, что при больших деревьях производительность снизится, и вы можете разбить стек. Но если все, что вам нужно, это простое дерево от малой до средней глубины, я думаю, что оно работает достаточно хорошо. Он предоставляет разумное (основанное на значениях) определение равенства, а также имеет реализацию toString, которая позволяет визуализировать дерево!

RutledgePaulV
источник
1

Пожалуйста, проверьте код ниже, где я использовал древовидные структуры данных, без использования классов Collection. В коде могут быть ошибки / улучшения, но, пожалуйста, используйте это только для справки

package com.datastructure.tree;

public class BinaryTreeWithoutRecursion <T> {

    private TreeNode<T> root;


    public BinaryTreeWithoutRecursion (){
        root = null;
    }


    public void insert(T data){
        root =insert(root, data);

    }

    public TreeNode<T>  insert(TreeNode<T> node, T data ){

        TreeNode<T> newNode = new TreeNode<>();
        newNode.data = data;
        newNode.right = newNode.left = null;

        if(node==null){
            node = newNode;
            return node;
        }
        Queue<TreeNode<T>> queue = new Queue<TreeNode<T>>();
        queue.enque(node);
        while(!queue.isEmpty()){

            TreeNode<T> temp= queue.deque();
            if(temp.left!=null){
                queue.enque(temp.left);
            }else
            {
                temp.left = newNode;

                queue =null;
                return node;
            }
            if(temp.right!=null){
                queue.enque(temp.right);
            }else
            {
                temp.right = newNode;
                queue =null;
                return node;
            }
        }
        queue=null;
        return node; 


    }

    public void inOrderPrint(TreeNode<T> root){
        if(root!=null){

            inOrderPrint(root.left);
            System.out.println(root.data);
            inOrderPrint(root.right);
        }

    }

    public void postOrderPrint(TreeNode<T> root){
        if(root!=null){

            postOrderPrint(root.left);

            postOrderPrint(root.right);
            System.out.println(root.data);
        }

    }

    public void preOrderPrint(){
        preOrderPrint(root);
    }


    public void inOrderPrint(){
        inOrderPrint(root);
    }

    public void postOrderPrint(){
        inOrderPrint(root);
    }


    public void preOrderPrint(TreeNode<T> root){
        if(root!=null){
            System.out.println(root.data);
            preOrderPrint(root.left);
            preOrderPrint(root.right);
        }

    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        BinaryTreeWithoutRecursion <Integer> ls=  new BinaryTreeWithoutRecursion <>();
        ls.insert(1);
        ls.insert(2);
        ls.insert(3);
        ls.insert(4);
        ls.insert(5);
        ls.insert(6);
        ls.insert(7);
        //ls.preOrderPrint();
        ls.inOrderPrint();
        //ls.postOrderPrint();

    }

}
Амит Матур
источник
2
" без использования классов коллекции " А? Так откуда берется класс Queue? И, как сказано выше, это двоичное дерево, которое вначале не выполняется (любое количество дочерних узлов).
PhiLho
1

Вы можете использовать класс TreeSet в java.util. *. Он работает как дерево двоичного поиска, поэтому он уже отсортирован. Класс TreeSet реализует интерфейсы Iterable, Collection и Set. Вы можете перемещаться по дереву с помощью итератора, как множество.

TreeSet<String> treeSet = new TreeSet<String>();
Iterator<String> it  = treeSet.Iterator();
while(it.hasNext()){
...
}

Вы можете проверить, Java Doc и некоторые другие .

Огуз
источник
-1

Пользовательская реализация дерева Tree без использования фреймворка Collection. Он содержит различные фундаментальные операции, необходимые для реализации дерева.

class Node {

    int data;
    Node left;
    Node right;

    public Node(int ddata, Node left, Node right) {
        this.data = ddata;
        this.left = null;
        this.right = null;      
    }

    public void displayNode(Node n) {
        System.out.print(n.data + " "); 
    }

}

class BinaryTree {

    Node root;

    public BinaryTree() {
        this.root = null;
    }

    public void insertLeft(int parent, int leftvalue ) {
        Node n = find(root, parent);
        Node leftchild = new Node(leftvalue, null, null);
        n.left = leftchild;
    }

    public void insertRight(int parent, int rightvalue) {
        Node n = find(root, parent);
        Node rightchild = new Node(rightvalue, null, null);
        n.right = rightchild;
    }

    public void insertRoot(int data) {
        root = new Node(data, null, null);
    }

    public Node getRoot() {
        return root;
    }

    public Node find(Node n, int key) {     
        Node result = null;

        if (n == null)
            return null;

        if (n.data == key)
            return n;

        if (n.left != null)
            result = find(n.left, key);

        if (result == null)
            result = find(n.right, key);

        return result;
    } 

    public int getheight(Node root){
        if (root == null)
            return 0;

        return Math.max(getheight(root.left), getheight(root.right)) + 1; 
    }

    public void printTree(Node n) {     
        if (n == null)
            return;

        printTree(n.left);
        n.displayNode(n);
        printTree(n.right);             
    }

}
Шивам Верма
источник
11
Это двоичное дерево, оно не выполняется при первом требовании OP ...
PhiLho