使用LinkedLists将子级添加到Tree中以存储Nodes的值 [英] Adding child to Tree using LinkedLists to store the value of Nodes

问题描述

好，所以我想实现一棵树，其中每个节点的子代的值都存储在LinkedList中。到目前为止，我有以下代码：

Ok so i want to implement a tree, of which the values of the children of each node are stored in a LinkedList. I have the following Code so far:

class Tree {

        class Node {
            int value;
            LinkedList<Node> children = null;

              Node(int value) {
                  this.value = value;
              }
        }

        public Node root = null;

        public void setRoot(Node root) {
            root = this.root;
        }

        public Node getRoot() {
            return root;
        }

        public void addChild(Node parent, Node child) {

        }
}

我苦苦寻找的是在这种结构中添加一个孩子的方法。我一直在寻找使用类似方式将每个节点的数据存储在LinkedLists中的站点，但找不到任何内容。

Where I struggle is finding a way to add a child to this structure. I have looked for sites using a similar way to store the data of each node in LinkedLists but I couldn't find anything.

推荐答案

在这里：

 static class Tree {
        static class Node {

            int value;
            LinkedList<Node> children;

            Node(int value) {
                this.value = value;
                this.children = new LinkedList<>();
            }

            // Override equals to detect node equality based on the value
            @Override
            public boolean equals(Object o) {
                if (this == o) {
                    return true;
                }
                if (o == null || getClass() != o.getClass()) {
                    return false;
                }

                Node node = (Node) o;

                return value == node.value;
            }

            @Override
            public int hashCode() {
                return value;
            }

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

        public Node root = null;

        // Assign the root like this not like yours which was not correct
        public void setRoot(Node root) {
            this.root = root;
        }

        public Node getRoot() {
            return root;
        }

        public void addChild(Node parent, Node child) {
            // Check if the root is null and parent not null then add child to the root
            if (root == null && parent != null) {
                root = parent;
                root.children.add(child);
                return;
            }

            // if the parent equals root then add to the root's child
            if (parent.equals(root)) {
                root.children.add(child);
                return;
            }

            // add recusively
            addRecur(root, parent, child);
        }

        private void addRecur(Node parent, Node p, Node child) {
            // base condition to the recursion
            if (parent == null) {
                return;
            }

            // if the parent equals to p then add to child
            if (parent.equals(p)) {
                parent.children.add(child);
                return;
            }

            // loop over every child and check if equals p if not do recursion
            for (Node node : parent.children) {
                if (node.equals(p)) {
                    node.children.add(child);
                    return;
                }
                addRecur(node, p, child);
            }
        }

        // print the tree
        public void print() {
            ArrayDeque<Node> queue = new ArrayDeque<>();
            queue.add(root);
            while (!queue.isEmpty()) {
                Node current = queue.poll();
                if (!current.children.isEmpty())
                    System.out.print("Parent: " + current + ", child: ");

                for (Node node : current.children) {
                    if (!queue.contains(node)) {
                        System.out.print(node + " ");
                        queue.add(node);
                    }
                }

                if (!current.children.isEmpty())
                    System.out.println();
            }
        }
    }

，来自<$ c的呼叫$ c> main 函数

    static public void main(String[] args) {
        Tree tree = new Tree();
        Tree.Node root = new Tree.Node(1);
        tree.addChild(root, new Tree.Node(2));
        tree.addChild(root, new Tree.Node(3));
        tree.addChild(root, new Tree.Node(4));
        tree.addChild(root, new Tree.Node(5));

        tree.addChild(new Tree.Node(5), new Tree.Node(6));
        tree.addChild(new Tree.Node(5), new Tree.Node(7));

        tree.addChild(new Tree.Node(6), new Tree.Node(8));
        tree.addChild(new Tree.Node(6), new Tree.Node(9));
        tree.addChild(new Tree.Node(6), new Tree.Node(15));

        tree.addChild(new Tree.Node(9), new Tree.Node(11));
        tree.addChild(new Tree.Node(9), new Tree.Node(10));
        tree.addChild(new Tree.Node(9), new Tree.Node(12));

        tree.print();
    }

，输出

Parent: 1, child: 2 3 4 5
Parent: 5, child: 6 7
Parent: 6, child: 8 9 15
Parent: 9, child: 11 10 12

这篇关于使用LinkedLists将子级添加到Tree中以存储Nodes的值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！