Java中的树实现（根、父节点和子节点）

Question

我需要在Java中创建一个类似附图的树形结构。我已经找到了一些相关问题，但是没有找到一个令人信服和解释清晰的答案。 应用程序业务包括食品超级类别（主菜，甜点和其他）。每个类别都可以有父项或子项等。

- Carlos

Answer 1

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

public class Node<T> {
    private List<Node<T>> children = new ArrayList<Node<T>>();
    private Node<T> parent = null;
    private T data = null;

    public Node(T data) {
        this.data = data;
    }

    public Node(T data, Node<T> parent) {
        this.data = data;
        this.parent = parent;
    }

    public List<Node<T>> getChildren() {
        return children;
    }

    public void setParent(Node<T> parent) {
        parent.addChild(this);
        this.parent = parent;
    }

    public void addChild(T data) {
        Node<T> child = new Node<T>(data);
        child.setParent(this);
        this.children.add(child);
    }

    public void addChild(Node<T> child) {
        child.setParent(this);
        this.children.add(child);
    }

    public T getData() {
        return this.data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public boolean isRoot() {
        return (this.parent == null);
    }

    public boolean isLeaf() {
        return this.children.size() == 0;
    }

    public void removeParent() {
        this.parent = null;
    }
}

例子：

import java.util.List;

Node<String> parentNode = new Node<String>("Parent"); 
Node<String> childNode1 = new Node<String>("Child 1", parentNode);
Node<String> childNode2 = new Node<String>("Child 2");     

childNode2.setParent(parentNode); 

Node<String> grandchildNode = new Node<String>("Grandchild of parentNode. Child of childNode1", childNode1); 
List<Node<String>> childrenNodes = parentNode.getChildren();

- Jonathan

---

Node<String> parentNode = new Node<String>("Parent"); \r - Jonathan

java.lang.StackOverflowError 表示程序运行时栈溢出错误。在 tree.Node 类中，第 40 行的 addChild 方法和第 29 行的 setParent 方法产生了循环调用，导致栈溢出错误。 - Serafins

是否应该有一个equals和hashCode方法？ - yegeniy

在isLeaf方法中， this.children.size == 0; 应该改为 this.children.size() == 0。 - 2016rshah

这段代码仍然会抛出StackOverflowError，真的很奇怪。 - Erdi İzgi

Answer 2

已接受的答案 在调用 setParent 或 addChild 方法时会抛出 java.lang.StackOverflowError 异常。

这是一个更简单的实现，没有这些 bug：

public class MyTreeNode<T>{
    private T data = null;
    private List<MyTreeNode> children = new ArrayList<>();
    private MyTreeNode parent = null;

    public MyTreeNode(T data) {
        this.data = data;
    }

    public void addChild(MyTreeNode child) {
        child.setParent(this);
        this.children.add(child);
    }

    public void addChild(T data) {
        MyTreeNode<T> newChild = new MyTreeNode<>(data);
        this.addChild(newChild);
    }

    public void addChildren(List<MyTreeNode> children) {
        for(MyTreeNode t : children) {
            t.setParent(this);
        }
        this.children.addAll(children);
    }

    public List<MyTreeNode> getChildren() {
        return children;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    private void setParent(MyTreeNode parent) {
        this.parent = parent;
    }

    public MyTreeNode getParent() {
        return parent;
    }
}

一些例子：

MyTreeNode<String> root = new MyTreeNode<>("Root");

MyTreeNode<String> child1 = new MyTreeNode<>("Child1");
child1.addChild("Grandchild1");
child1.addChild("Grandchild2");

MyTreeNode<String> child2 = new MyTreeNode<>("Child2");
child2.addChild("Grandchild3");

root.addChild(child1);
root.addChild(child2);
root.addChild("Child3");

root.addChildren(Arrays.asList(
        new MyTreeNode<>("Child4"),
        new MyTreeNode<>("Child5"),
        new MyTreeNode<>("Child6")
));

for(MyTreeNode node : root.getChildren()) {
    System.out.println(node.getData());
}

- Esdras Lopez

---

这个设计存在循环依赖和可变性的问题。如果需要解决这些问题，可以将父节点删除并将其放入节点到父节点的单独映射中。 - DPM

myNode.addChild(myNode) > 循环引用 > 不再是树结构 - István Békési

Answer 3

以下是符合您需求的Java实现。在treeNode类中，我使用了泛型数组来存储树形数据。我们也可以使用ArrayList或动态数组来存储树形数值。

public class TreeNode<T> {
   private T value = null;
   private TreeNode[] childrens = new TreeNode[100];
   private int childCount = 0;

    TreeNode(T value) {
        this.value = value;
    }

    public TreeNode addChild(T value) {
        TreeNode newChild = new TreeNode(value, this);
        childrens[childCount++] = newChild;
        return newChild;
    }

    static void traverse(TreeNode obj) {
        if (obj != null) {
            for (int i = 0; i < obj.childCount; i++) {
                System.out.println(obj.childrens[i].value);
                traverse(obj.childrens[i]);
            }
        }
        return;
    }

    void printTree(TreeNode obj) {
        System.out.println(obj.value);
        traverse(obj);
    }
}

以上实现的客户端类。

public class Client {
    public static void main(String[] args) {
        TreeNode menu = new TreeNode("Menu");
        TreeNode item = menu.addChild("Starter");
            item = item.addChild("Veg");
                item.addChild("Paneer Tikka");
                item.addChild("Malai Paneer Tikka");
            item = item.addChild("Non-veg");
                item.addChild("Chicken Tikka");
                item.addChild("Malai Chicken Tikka");
        item = menu.addChild("Main Course");
            item = item.addChild("Veg");
                item.addChild("Mili Juli Sabzi");
                item.addChild("Aloo Shimla Mirch");
            item = item.addChild("Non-veg");
                item.addChild("Chicken Do Pyaaza");
                item.addChild("Chicken Chettinad");
        item = menu.addChild("Desserts");
                item = item.addChild("Cakes");
                        item.addChild("Black Forest");
                        item.addChild("Black Current");
                item = item.addChild("Ice Creams");
                        item.addChild("chocolate");
                        item.addChild("Vanilla");
        menu.printTree(menu);
    }
}

输出

Menu                                                                     
Starter                                                                 
Veg                                                                
Paneer Tikka                                                        
Malai Paneer Tikka                                                    
Non-veg                                                              
Chicken Tikka                                                      
Malai Chicken Tikka                                                 
Main Course                                                      
Veg                                                             
Mili Juli Sabzi                                                   
Aloo Shimla Mirch                                                  
Non-veg                                                               
Chicken Do Pyaaza                                                   
Chicken Chettinad                                                    
Desserts                                                         
Cakes                                                            
Black Forest                                                     
Black Current                                                   
Ice Creams                                                      
chocolate                                                       
Vanilla           

- Irshad ck

Answer 4

由于@Jonathan的答案中仍存在一些错误，因此我进行了改进。为了调试目的，我覆盖了toString()方法，请确保根据您的数据相应更改。

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

/**
 * Provides an easy way to create a parent-->child tree while preserving their depth/history.
 * Original Author: Jonathan, https://dev59.com/NGIk5IYBdhLWcg3wYtNC#22419453
 */
public class TreeNode<T> {
    private final List<TreeNode<T>> children;
    private TreeNode<T> parent;
    private T data;
    private int depth;

    public TreeNode(T data) {
        // a fresh node, without a parent reference
        this.children = new ArrayList<>();
        this.parent = null;
        this.data = data;
        this.depth = 0; // 0 is the base level (only the root should be on there)
    }

    public TreeNode(T data, TreeNode<T> parent) {
        // new node with a given parent
        this.children = new ArrayList<>();
        this.data = data;
        this.parent = parent;
        this.depth = (parent.getDepth() + 1);
        parent.addChild(this);
    }

    public int getDepth() {
        return this.depth;
    }

    public void setDepth(int depth) {
        this.depth = depth;
    }

    public List<TreeNode<T>> getChildren() {
        return children;
    }

    public void setParent(TreeNode<T> parent) {
        this.setDepth(parent.getDepth() + 1);
        parent.addChild(this);
        this.parent = parent;
    }

    public TreeNode<T> getParent() {
        return this.parent;
    }

    public void addChild(T data) {
        TreeNode<T> child = new TreeNode<>(data);
        this.children.add(child);
    }

    public void addChild(TreeNode<T> child) {
        this.children.add(child);
    }

    public T getData() {
        return this.data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public boolean isRootNode() {
        return (this.parent == null);
    }

    public boolean isLeafNode() {
        return (this.children.size() == 0);
    }

    public void removeParent() {
        this.parent = null;
    }

    @Override
    public String toString() {
        String out = "";
        out += "Node: " + this.getData().toString() + " | Depth: " + this.depth + " | Parent: " + (this.getParent() == null ? "None" : this.parent.getData().toString()) + " | Children: " + (this.getChildren().size() == 0 ? "None" : "");
        for(TreeNode<T> child : this.getChildren()) {
            out += "\n\t" + child.getData().toString() + " | Parent: " + (child.getParent() == null ? "None" : child.getParent().getData());
        }
        return out;
    }
}

关于可视化：

import model.TreeNode;

/**
 * Entrypoint
 */
public class Main {
    public static void main(String[] args) {
        TreeNode<String> rootNode = new TreeNode<>("Root");
        TreeNode<String> firstNode = new TreeNode<>("Child 1 (under Root)", rootNode);
        TreeNode<String> secondNode = new TreeNode<>("Child 2 (under Root)", rootNode);
        TreeNode<String> thirdNode = new TreeNode<>("Child 3 (under Child 2)", secondNode);
        TreeNode<String> fourthNode = new TreeNode<>("Child 4 (under Child 3)", thirdNode);
        TreeNode<String> fifthNode = new TreeNode<>("Child 5 (under Root, but with a later call)");
        fifthNode.setParent(rootNode);

        System.out.println(rootNode.toString());
        System.out.println(firstNode.toString());
        System.out.println(secondNode.toString());
        System.out.println(thirdNode.toString());
        System.out.println(fourthNode.toString());
        System.out.println(fifthNode.toString());
        System.out.println("Is rootNode a root node? - " + rootNode.isRootNode());
        System.out.println("Is firstNode a root node? - " + firstNode.isRootNode());
        System.out.println("Is thirdNode a leaf node? - " + thirdNode.isLeafNode());
        System.out.println("Is fifthNode a leaf node? - " + fifthNode.isLeafNode());
    }
}

示例输出：

Node: Root | Depth: 0 | Parent: None | Children: 
    Child 1 (under Root) | Parent: Root
    Child 2 (under Root) | Parent: Root
    Child 5 (under Root, but with a later call) | Parent: Root
Node: Child 1 (under Root) | Depth: 1 | Parent: Root | Children: None
Node: Child 2 (under Root) | Depth: 1 | Parent: Root | Children: 
    Child 3 (under Child 2) | Parent: Child 2 (under Root)
Node: Child 3 (under Child 2) | Depth: 2 | Parent: Child 2 (under Root) | Children: 
    Child 4 (under Child 3) | Parent: Child 3 (under Child 2)
Node: Child 4 (under Child 3) | Depth: 3 | Parent: Child 3 (under Child 2) | Children: None
Node: Child 5 (under Root, but with a later call) | Depth: 1 | Parent: Root | Children: None
Is rootNode a root node? - true
Is firstNode a root node? - false
Is thirdNode a leaf node? - false
Is fifthNode a leaf node? - true

一些额外的信息：不要同时使用addChildren()和setParent()。因为setParent()已经更新了子项=>父项的关系，你最终会得到两个引用。

- 0x446

Answer 5

这棵树不是二叉树，因此您需要一个子元素的数组，例如List。

public Node(Object data, List<Node> children) {
    this.data = data;
    this.children = children;
}

然后创建实例。

- Arnold Galovics

Answer 6

在被接受的回答中

public Node(T data, Node<T> parent) {
    this.data = data;
    this.parent = parent;
}

应该是

public Node(T data, Node<T> parent) {
    this.data = data;
    this.setParent(parent);
}

否则，父级列表中将没有该子项。

- tognyx

---

好的，请将需要翻译的内容添加为评论。 - rassa45

Answer 7

在答案中，它创建了循环依赖关系。可以通过在子节点中移除父节点来避免这种情况，即：

public class MyTreeNode<T>{     


    private T data = null;
    private List<MyTreeNode> children = new ArrayList<>();


    public MyTreeNode(T data) {
        this.data = data;

    }

    public void addChild(MyTreeNode child) {
        this.children.add(child);
    }

    public void addChild(T data) {
        MyTreeNode<T> newChild = new MyTreeNode<>(data);
        children.add(newChild);
    }

    public void addChildren(List<MyTreeNode> children) {
        this.children.addAll(children);
    }

    public List<MyTreeNode> getChildren() {
        return children;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }


}

使用上面指定的相同示例，输出将如下所示：

{ "data": "根", "children": [ { "data": "子1", "children": [ { "data": "孙子1", "children": [] }, { "data": "孙子2", "children": [] } ] }, { "data": "子2", "children": [ { "data": "孙子3", "children": [] } ] }, { "data": "子3", "children": [] }, { "data": "子4", "children": [] }, { "data": "子5", "children": [] }, { "data": "子6", "children": [] } ] }

- Jeevana

Answer 8

组装树节点的过程类似于组装列表的过程。我们有一个构造函数用于初始化树节点的实例变量。

public Tree (Object cargo, Tree left, Tree right) { 
    this.cargo = cargo; 
    this.left = left; 
    this.right = right; 
} 

我们首先分配子节点：

Tree left = new Tree (new Integer(2), null, null); 
Tree right = new Tree (new Integer(3), null, null); 

我们可以同时创建父节点并将其链接到子节点：

Tree tree = new Tree (new Integer(1), left, right); 

- Stephen Hosea

---

上图不是二叉树。 - AJ.