如何整理我的 Java 代码，因为它有太多循环

Question

我有一个节点class用来表示一个树结构。在这个 class 中，我定义了一个应该产生以下输出的打印方法：

data
--a (1024)
--b (256)
----ba (100)
------baa (500)
------bac (25)
----bc (150)
----bd (125)
----be (75)
--c (35)
----cb (30)
----ce (50)

这是我编写打印方法的方式：

public void print(String name) {
        Node node = this.find(name);
        System.out.println(node.name);
        if (node.childrensCount != 0) {
            for (int i = 0; i < node.childrensCount; i++) {
                Node children = node.childrens[i];
                System.out.println("--" + children.name + " (" + children.value + ")");
                if (children.childrensCount != 0) {
                    for (int j = 0; j < children.childrensCount; j++) {
                        Node grandChildren = children.childrens[j];
                        System.out.println("----" + grandChildren.name + " (" + grandChildren.value + ")");
                        if (grandChildren.childrensCount != 0) {
                            for (int k = 0; k < grandChildren.childrensCount; k++) {
                                Node greatGrandChildren = grandChildren.childrens[k];
                                System.out.println("------" + greatGrandChildren.name + " (" + greatGrandChildren.value + ")");
                            }
                        }
                    }
                }
            }
        }
    }

这也是节点 class 实现，可以更好地帮助您理解场景：

public class Node {

    int value;
    String name;
    Node parent;
    int childrensCount;
    Node[] childrens = new Node[100];

    public Node(int value, String name) {
        this.value = value;
        this.name = name;
        this.childrensCount = 0;
    }

    public Node(String name) {
        this.name = name;
    }
    
    public void addChildren(Node node)
    {
        this.childrens[childrensCount] = node;
        childrensCount++;
    }
    
    public void setParent(Node parent)
    {
        this.parent = parent;
    }
    
    public boolean hasParent(){
        return this.parent != null;
    }
    
    public int sumValue(){
        int sum = 0;
        sum += this.value;
        for (int i = 0; i < childrensCount; i++) {
            sum += childrens[i].value;
        }
        return sum;
    }
}

我认为我的代码很脏，可以改进。我想定义一个递归方法，但我仍然不明白递归是如何工作的。有人可以帮我吗？

Answer 1

您可以使用递归来完成。我没有尝试重建所有复杂的数据，而是使用我自己的节点 class.

创建了一个简单的示例

class MyNode {
    String name;
    List<MyNode> nodeList;
    
    public MyNode(String name) {
        this.name = name;
    }
    
    public MyNode setNodeList(List<MyNode> list) {
        nodeList = list;
        return this;
    }
    @Override
    public String toString() {
        return name;
    }
    public List<MyNode> getNodeList() {
        return nodeList;
    }
}

    
    
MyNode m = new MyNode("a");
List<MyNode> list1 =
        List.of(new MyNode("aaa"), new MyNode("aab"),
                new MyNode("aac"), new MyNode("aad"));
List<MyNode> list2 = List.of(new MyNode("aba"),
        new MyNode("abb"), new MyNode("abc"));
List<MyNode> list3 = List.of(new MyNode("aca"),
        new MyNode("acb"), new MyNode("acc"));
List<MyNode> list4 = List.of(new MyNode("ada"),
        new MyNode("adb"), new MyNode("adc"));

List<MyNode> mainlist = List.of(new MyNode("aa").setNodeList(list1),
        new MyNode("ab").setNodeList(list2), new MyNode("ac").setNodeList(list3), new MyNode("ad").setNodeList(list4));
        

m.setNodeList(mainlist);
print(m,1);

打印

--a
----aa
------aaa
------aab
------aac
------aad
----ab
------aba
------abb
------abc
----ac
------aca
------acb
------acc
----ad
------ada
------adb
------adc

这是通过让 print 方法调用自身并调整缩进级别来实现的。
打印当前节点和级别。
如果该节点的列表是 non-null，则为列表中的每个节点调用 print 方法并重复该过程，更新级别。
在每个 return 之后，该方法从它停止的地方开始，因为它继续调用自身和 return.
这是遍历 hie-rarchical 数据集的常见过程，适用于不确定数量的级别。

public static void print(MyNode node, int level) {
    System.out.println("-".repeat(level*2) + node);
    if (node.getNodeList() != null) {
       for (MyNode n : node.getNodeList()) {
                print(n, level+1);
        }
    }
}

我建议您阅读递归过程。在某些情况下，您还可以在遍历层次结构时 return 值。

Answer 2

要定义递归方法，您首先需要确定基本案例和递归案例。在这种情况下，基本情况是传递给打印的节点为空，而递归情况是仍有子节点要打印。

因为我知道您的程序可能是学校练习，所以我将避免讨论什么可以或不可以更好地实现您的 Node class。毫无疑问，使用 Collections 框架中的 List 数据结构而不是 100 个元素的固定数组是更好的选择，但我认为你的老师希望在开始时保持简单，而你很可能没有涵盖 Collections框架，但自从您说您仍在为递归而苦苦挣扎（这完全没问题，我们都必须从某个地方开始！）。因此，我将保留您的 class 实现的原样。我只会添加一些方法和一些调整。

在这里，我实施了一个解决方案来向您展示递归打印的工作原理。请记住，我将打印实现拆分为两种方法只是为了让客户端更容易调用它。事实上，客户不应该知道也不应该为使其工作的内部实现细节而烦恼。


//Test class
public class Test {
    public static void main(String[] args) {
        Node root = new Node(1, "test1", new Node[]{
                new Node(2, "test2", new Node[]{
                        new Node(5, "test6", new Node[]{})
                }),
                new Node(3, "test3", new Node[]{
                        new Node(6, "test6", new Node[]{}),
                        new Node(7, "test7", new Node[]{
                                new Node(8, "test8", new Node[]{})
                        })
                }),
                new Node(4, "test4", new Node[]{})
        });

        root.print();
    }
}

class Node {

    int value;
    String name;
    Node parent;
    int childrenCount;
    Node[] children = new Node[100];

    public Node(int value, String name) {
        this.value = value;
        this.name = name;
        this.childrenCount = 0;
    }

    //Added second constructor only to ease the test
    public Node(int value, String name, Node[] children) {
        this.value = value;
        this.name = name;
        this.children = children;
        this.childrenCount = getNumChildren(children);
    }

    public Node(String name) {
        this.name = name;
    }

    //Fixed possible exception when added more than 100 elements
    public boolean addChildren(Node node) {
        if (childrenCount == this.children.length) {
            return false;
        }
        this.children[childrenCount++] = node;
        return true;
    }

    public void setParent(Node parent) {
        this.parent = parent;
    }

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

    public int sumValue() {
        int sum = 0;
        sum += this.value;
        for (int i = 0; i < childrenCount; i++) {
            sum += children[i].value;
        }
        return sum;
    }

    //small utility method only to compute the effective number of children when an array is passed within the new constructor
    public static int getNumChildren(Node[] children) {
        int num = 0;
        while (num < children.length && children[num] != null) {
            num++;
        }
        return num;
    }

    //print method invoked by the client of the class
    public void print() {
        printRec(this, 0);
    }

    //recursive print
    private void printRec(Node n, int numCall) {
        //identifying the base case
        if (n == null) {
            return;
        }

        //Printing as many dahses as the depth of the current child node
        for (int i = 1; i <= numCall; i++) {
            System.out.print("--");
        }

        //printing the node info
        System.out.println(n.name + " (" + n.value + ")");

        //recursively invoking the print method for each child
        for (int i = 0; i < n.childrenCount; i++) {
            printRec(n.children[i], numCall + 1);
        }
    }
}

这里我只想补充几点：

children 已经是 child 的复数形式。你不需要调用你的数组 childrens。
如果您添加的元素超过 100 个，您之前执行的 add 方法可能会引发 ArraIndexOutOfBoundsException。通常，当操作可能失败时，该方法应该 return 一个布尔值来告诉客户端操作是否成功。

如何整理我的 Java 代码，因为它有太多循环

How to tidying my Java code because it has too many looping

java

recursion

tree