具有自定义方法和嵌套节点类的Java n进制树类

Question

我是个初学者，我为n进制树编写了这个(工作)代码。

具体内容：

• 每个节点都要生成一个整数值。
• 每个节点都有可变数量的子节点。
• 节点应该有一个add(Node n)方法，它添加了一个子节点。
• 该树应该有一个包含(Int)方法，该方法返回一个布尔值(如果在节点中找到数字val，则为true)。
• 它应该有一个add(int... intArray)方法，如果根对应于intArray中的第一个数字，则将分支附加到根。intArray中的其他数字只有在它们不存在的情况下才会被添加(每个数字都是前面数字的子项)。
• 树应该有一个remove(int r)方法，该方法删除一个值为r(如果存在)的节点，并将其子节点附加到其父节点。如果节点恰好是根，那么根的第一个子节点就变成根。

import java.util.*;

public class NaryTree
{
    private Node root;

    static public class Node
    {
        private List<Node> children;
        private int value;

        public Node(List<Node> children, int value)
        {
            this.children = children;
            this.value = value;
        }

        public void add(Node n)
        {
            if (children == null) children = new ArrayList<>();
            children.add(n);
        }
    }

    public void add(int ... intArray) throws RootsNotEquals
    {
        if (root == null) root = new Node(null, intArray[0]);
        if (root.value != intArray[0]) { throw new RootsNotEquals(); }
        else
        {
            if (intArray.length >= 1) { intArray = Arrays.copyOfRange(intArray, 1, intArray.length); }
            add(root, intArray);
        }
    }

    public void add(Node tempRoot, int ... intArray)
    {
        boolean present = false;
        int index = -1;

        for (int i = 0; i < intArray.length; i++)
        {
            if (tempRoot.children != null)
            {
                for (int j = 0; j < tempRoot.children.size()-1; j++)
                {
                    if (tempRoot.children.get(j).value == intArray[0]) present = true;
                }
            }
            if (!present) { tempRoot.add(new Node(null, intArray[0])); }
            for (Node f : tempRoot.children)
            {
                index++;
                if (f.value == intArray[0])
                {
                    if (index <= tempRoot.children.size()-1) tempRoot = tempRoot.children.get(index);
                    if (intArray.length >= 1) intArray = Arrays.copyOfRange(intArray, 1, intArray.length);
                    add(tempRoot, intArray);
                    break;
                }
            }
            break;
        }
    }

    public void remove(int r) throws NodeNotFound
    {
        if (!contains(r)) throw new NodeNotFound();
        if (root.value == r)
        {
            for (int i = 1; i < root.children.size(); i++)
            {
                root.children.get(0).children.add(root.children.get(i));
            }
            root = root.children.get(0);
        }
        else { remove(root, r); }
    }

    public void remove(Node tempRoot, int r)
    {
        if (tempRoot.children != null)
        {
            for (int i = 0; i < tempRoot.children.size(); i++)
            {
                if (tempRoot.children.get(i).value == r)
                {
                    for (Node n : tempRoot.children.get(i).children) tempRoot.children.add(n);
                    tempRoot.children.remove(i);
                }
                else
                {
                    tempRoot = tempRoot.children.get(i);
                    remove(tempRoot, r);
                    break;
                }
            }
        }
    }

    public boolean contains(int val) { return contains(root, val); }

    private boolean contains(Node n, int val)
    {
        boolean found = false;
        if (n == null) return found;
        if (n.value == val) found = true;
        else if (n.children != null) for (Node f : n.children) { return contains(f, val); }
        return found;
    }

    public void print()
    {
        System.out.println("The root is "+root.value+".");
        for (Node n : root.children)
        {
            System.out.println(n.value+" is a child of the root.");
            printChildren(n);
        }
    }

    public void printChildren(Node n)
    {
        if (n.children != null)
        {
            for (Node child : n.children)
            {
                System.out.println("Node "+n.value+" has node "+child.value+" as a child.");
                printChildren(child);
            }
        }
    }

    public static void main(String[] args) throws RootsNotEquals, NodeNotFound
    {
        NaryTree poplar = new NaryTree();

        poplar.add( new int[] { 1, 2, 5 });
        poplar.add( new int[] { 1, 4, 0, 0 } );
        poplar.add( new int[] { 1, 3, 6 });
        poplar.add( new int[] { 1, 2, 7 });
        poplar.print();
    }
}

Answer 1

private List<Node> children;

如果您将此更改为

        private List<Node> children = new ArrayList<>();

大量的空检查将消失。这将增加内存使用量，但目前尚不清楚这会产生多大的差异。

public Node(List<Node> children, int value)

这似乎是一个寻找问题的解决方案。您的调用者根本不需要了解Node，所以这总是用null调用的。

        public Node(int value)

这样，你就能支持自然的道路。调用方只需要知道树是否包含整数。它不需要知道任何关于它如何持有它们的信息。

if (root.value != intArray[0]) { throw new RootsNotEquals(); } else

这里不需要else。throw结束当前方法。

如果要将括号放在控制结构中的单个语句上，则应该始终这样做。您有时使用更常见的单语句形式，有时使用此语句。你应该选一个。

顺便提一句，java标准是编写控制结构，如

        if (root.value != intArray[0]) {
            throw new RootsNotEquals();
        }

如果你每次都这样写的话，你的垂直空间就会比你在同一条线上和每条线上的混合空间要少。

if (intArray.length >= 1) { intArray = Arrays.copyOfRange(intArray, 1, intArray.length); } add(root, intArray);

这看起来很傻。您可以调用add，即使它是不必要的，尽管在它之前检查了正确的条件。好呀

        if (intArray.length >= 1) {
            intArray = Arrays.copyOfRange(intArray, 1, intArray.length);
            add(root, intArray);
        }

这将为您节省一个方法调用，它最终将成为一个不操作。

还可以考虑在方法开始时进行长度检查。因为如果长度为0，那么intArray[0]将抛出一个异常。所以你永远不会到达进行检查的代码。

我也认为这种方法的行为是相当愚蠢的。为了添加多个值，您需要传递根值。作为密码？在现实世界中，如果您收到了这样的要求，那么就很自然地要求删除该需求。也许它存在于这里是为了教导的目的。

for (int i = 0; i < intArray.length; i++)

为什么？在迭代结束时，您已经

break;

所以这只做过一次迭代。把它拿出来。它实际上并没有完成任何事情，而且您也从未使用过i。

if (index <= tempRoot.children.size()-1) tempRoot = tempRoot.children.get(index);

这将永远是真的，所以它可以是

                tempRoot = f;

你可以完全摆脱index。

if (intArray.length >= 1) intArray = Arrays.copyOfRange(intArray, 1, intArray.length);

再说一遍，这将永远是真的。

add(tempRoot, intArray);

这可能是

                add(f, Arrays.copyOfRange(intArray, 1, intArray.length));

注意，这每次都会创建一个新的数组。传递index变量并将[0]更改为[index]可能会更好。

在remove(int)中，

if (!contains(r)) throw new NodeNotFound();

考虑实现findParentOf(int)。因为这实际上是搜索树，查找所需的元素，忘记元素的位置，并返回true或false。然后你再去找那个元素。你会用它就像

        Node parent = findParentOf(r);
        if (r == null) {
            throw new NodeNotFound();
        }

当然，在检查它是否是根值之后(不要忘记首先检查null )，就可以这样做。