Java에서 트리 데이터 구조를 구현하려면 어떻게 해야 합니까?

Java에서 트리 데이터 구조를 구현하려면 어떻게 해야 합니까?

Java에서 트리를 나타내는 표준 Java 라이브러리 클래스가 있습니까?

구체적으로는 다음 사항을 나타내야 합니다.

• 모든 노드의 하위 트리는 임의 개수의 하위 트리를 가질 수 있습니다.
• 각 노드(루트 다음)와 그 자식 노드에는 문자열 값이 있습니다.
• 특정 노드의 모든 자식(일종의 목록 또는 문자열 배열)과 문자열 값(즉, 노드를 입력으로 사용하고 자식 노드의 모든 문자열 값을 출력으로 반환하는 메서드)을 가져올 필요가 있습니다.

이에 사용할 수 있는 구조가 있습니까?아니면 독자적인 구조를 작성해야 합니까(실장 제안이 좋을 경우).

여기:

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.

또 다른 트리 구조:

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

실제로 JDK에는 꽤 좋은 트리 구조가 구현되어 있습니다.

javax.swing.tree, TreeModel 및 TreeNode를 확인합니다.이러한 기능은, E-M-M-M-M-M-M-M-JTreePanel하지만 실제로는 꽤 훌륭한 트리의 실장입니다.스윙 인터페이스 없이 사용하는 것을 막을 수 있는 것은 없습니다.

Java 9부터는 이러한 클래스는 '컴팩트 프로파일'에 존재하지 않으므로 사용하지 않는 것이 좋습니다.

이건 어때?

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;
  }
}

나는 일반 나무를 다루는 작은 도서관을 썼다.스윙 제품보다 훨씬 가볍습니다.나도 그것을 위한 메이븐 프로젝트가 있다.

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;
    }
}

유틸리티 메서드를 추가하여 하위 항목을 추가하거나 제거할 수 있습니다.

우선 트리가 무엇인지(도메인용) 정의부터 시작해야 합니다.이 작업은 먼저 인터페이스를 정의하는 것이 가장 좋습니다.모든 트리 구조를 변경할 수 있는 것은 아닙니다.노드를 추가하거나 삭제할 수 있는 것은 옵션 기능입니다.따라서 추가 인터페이스를 만듭니다.

값을 유지하는 노드 개체를 생성할 필요가 없습니다. 사실 대부분의 트리 구현에서 이는 주요 설계 결함 및 오버헤드로 간주됩니다.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);
        }
    }
}

지나치게 단순하지만 동작하는 코드를 언급하는 답변은 없습니다.다음은 예를 제시하겠습니다.

public class TreeNodeArray<T> {
    public T value;
    public final  java.util.List<TreeNodeArray<T>> kids =  new java.util.ArrayList<TreeNodeArray<T>>();
}

화이트보드 코딩, 인터뷰, 트리 사용 계획 중이라면 이 모든 것이 다소 장황합니다.

예를 나무가 없는 이유, 예를 들어 가 없는 이유라고 .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;
}

아니면 트라이를 원한다면:

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
[]

Java의 XML API를 문서 및 노드로 사용할 수 있습니다.XML은 문자열이 있는 트리 구조입니다.

Gareth의 답변과 마찬가지로 Default Mutable을 확인하십시오.트리 노드일반적인 것은 아니지만, 그 외에는 적절한 것 같습니다.javax.swing 패키지에 포함되어 있지만 AWT나 Swing 클래스에 의존하지 않습니다.사실, 소스코드에 코멘트가 있어요// ISSUE: this class depends on nothing in AWT -- move to java.util?

Java에는 Default Mutable과 같은 몇 가지 트리 데이터 구조가 있습니다.JDK Swing의 TreeNode, 스탠포드 파서 패키지의 Tree 및 기타 장난감 코드.그러나 이것들 중 어느 것도 일반적인 목적을 위해 충분하지는 않다.

Java-Tree 프로젝트는 Java에서 다른 범용 트리 데이터 구조를 제공하려고 합니다.이것과 다른 것의 차이점은

• 완전 무료입니다.어디서든 사용할 수 있습니다(숙제:P 제외).
• 작지만 충분히 일반적이죠.데이터 구조의 모든 것을 하나의 클래스 파일에 넣었기 때문에 복사/붙여넣기가 쉬울 것입니다.
• 그냥 장난감이 아니라.바이너리 트리 또는 제한된 작업만 처리할 수 있는 수십 개의 Java 트리 코드를 알고 있습니다.이 Tree Node는 그것보다 훨씬 많습니다.또한 예약, 후순, 너비 우선, 잎, 루트 경로 등 다양한 노드 방문 방법을 제공합니다.게다가, 반복기는 충분하기 위해서도 제공되고 있다.
• 더 많은 유틸리티가 추가됩니다.특히 당신이 github을 통해 요청을 보낸다면, 저는 이 프로젝트를 포괄적으로 하기 위해 더 많은 작업을 추가할 용의가 있습니다.

이 질문에서는 사용 가능한 데이터 구조를 묻기 때문에 트리는 목록 또는 배열에서 구성할 수 있습니다.

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

instanceof는 요소가 서브트리인지 터미널 노드인지를 판단하기 위해 사용할 수 있습니다.

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;
  ...
}

나는 과거에 이것을 위해 네스트된 지도를 사용했다.이게 제가 요즘 쓰는 건데, 아주 심플하지만 제 필요에 딱 맞아요.이게 다른 사람에게 도움이 될지도 몰라.

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"));
    }
}

경로 추가를 지원하는 "HashMap"을 기반으로 작은 "TreeMap" 클래스를 작성했습니다.

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(", "));
}

그리고 당신은 멋진 나무를 얻을 것입니다.당신의 요구에 적응하는 것은 쉬울 것입니다.

예를 들어 다음과 같습니다.

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;
    }
}

자카르타 프로젝트의 일부인 Apache JMeter에 포함된 HashTree 클래스를 사용할 수 있습니다.

HashTree 클래스는 org.apache 패키지에 포함되어 있습니다.jorphan.collections.이 패키지는 JMeter 프로젝트 이외에는 출시되지 않지만 다음과 같이 쉽게 구할 수 있습니다.

1) JMeter 소스를 다운로드합니다.

2) 새로운 패키지를 만듭니다.

3) /src/jorpan/org/apache/jorpan/collections/. Data.java를 제외한 모든 파일을 복사합니다.

4) /src/jorpan/org/apache/jorpan/util/JOrphanUtils.java도 복사합니다.

5) Hash Tree를 사용할 수 있습니다.

Java에는 사용자의 요구사항에 맞는 특정 데이터 구조가 없습니다.고객의 요건은 매우 구체적이며, 이를 위해서는 독자적인 데이터 구조를 설계해야 합니다.요건을 보면 특정 기능을 가진 n-ary 트리가 필요하다고 누구나 말할 수 있습니다.다음과 같은 방법으로 데이터 구조를 설계할 수 있습니다.

1. 트리 노드의 구조는 노드 및 하위 목록의 컨텐츠와 같습니다. 클래스 노드 {String 값; 하위 노드 나열;}
2. 특정 문자열의 자식을 취득할 필요가 있기 때문에 2가지 메서드1: 노드 searchNode(String str)는 지정된 입력과 같은 값을 가진 노드를 반환한다(BFS를 사용하여 검색한다)2: 이 메서드는 내부적으로 searchNode를 호출하여 동일한 문자열을 가진 노드를 취득한 후 전체 목록을 작성합니다.하위 및 반환 문자열 값.
3. 트리에 문자열을 삽입해야 합니다.void insert(String parent, String value)라는 메서드를 하나 작성해야 합니다.이것에 의해, 부모와 같은 값을 가지는 노드가 재차 검색되어 특정의 값으로 노드를 작성해, 검색된 부모에의 자식 리스트에 추가할 수 있습니다.

Class Node {String value;List children;}과 같은 클래스에 노드의 구조를 쓰고 다른 NodeUtils 클래스에 검색, 삽입 및 getChildren과 같은 다른 모든 메서드를 작성하여 다음과 같은 특정 트리에 대한 작업을 수행할 수도 있습니다: Class NodeUtils { public Node search (Node, Value}// BFS를 실행하고 Node}를 반환한다.

    // 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);
  }
}

자바8과 잘 어울리고 다른 의존관계가 없는 트리 라이브러리를 작성했습니다.또한 기능 프로그래밍의 일부 아이디어를 느슨하게 해석할 수 있으며 전체 트리 또는 하위 트리를 매핑/필터링/제거/검색할 수 있습니다.

https://github.com/RutledgePaulV/prune

이 구현은 인덱스에 특별한 영향을 주지 않으며 재귀에서 벗어나지 않았기 때문에 트리가 크면 성능이 저하되어 스택이 파괴될 수 있습니다.하지만 깊이가 작은 나무에서 중간 정도의 나무만 있으면 충분하다고 생각합니다.이 툴은 균등성에 대한 올바른(값 기반) 정의를 제공하며 트리를 시각화할 수 있는 toString 구현도 갖추고 있습니다.

Collection 클래스를 사용하지 않고 Tree 데이터 구조를 사용한 아래 코드를 확인하십시오.코드에는 버그/개선이 있을 수 있지만 참고용으로 사용해 주십시오.

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();

    }

}

java.util.*에서 TreeSet 클래스를 사용할 수 있습니다.바이너리 검색 트리처럼 동작하기 때문에 이미 정렬되어 있습니다.TreeSet 클래스는 Itable, Collection 및 Set 인터페이스를 구현합니다.세트처럼 반복기를 사용하여 트리를 통과할 수 있습니다.

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

Java Doc 및 기타 항목을 확인할 수 있습니다.

import java.util.Collection;
import java.util.LinkedList;
import java.util.function.BiConsumer;
import java.util.function.Function;

/**
 * @author changjin wei(魏昌进)
 * @since 2021/7/15
 */
public class TreeUtils {

    private TreeUtils() {
    }

    /**
     * @param collection this is a collection of elements
     * @param getId this is a getId Function
     * @param getParentId this is a getParentId Function
     * @param setNode this is a setNode BiConsumer
     * @param <E> the type of elements in this collection
     * @param <R> the type of the result of the function
     *
     * @return Collection
     */
    public static <E, R> Collection<E> tree(Collection<E> collection, Function<E, R> getId, Function<E, R> getParentId, BiConsumer<E, Collection<E>> setNode) {
        Collection<E> root = new LinkedList<>();
        for (E node : collection) {
            R parentId = getParentId.apply(node);
            R id = getId.apply(node);
            Collection<E> elements = new LinkedList<>();
            boolean isParent = true;
            for (E element : collection) {
                if (id.equals(getParentId.apply(element))) {
                    elements.add(element);
                }
                if (isParent && getId.apply(element).equals(parentId)) {
                    isParent = false;
                }
            }
            if (isParent) {
                root.add(node);
            }
            setNode.accept(node, elements);
        }
        return root;
    }
}

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);             
    }

}

언급URL : https://stackoverflow.com/questions/3522454/how-to-implement-a-tree-data-structure-in-java