时间戳

首页 > 解决方案 > 在java中的n-ary树中找到一个不包含最大子节点数的节点

java - 在java中的n-ary树中找到一个不包含最大子节点数的节点

问题描述

我在使用递归函数时遇到了麻烦。树中的每个节点最多可以有三个孩子。

这是节点结构的实现。（节点类是树类中的嵌套类）

public final class Node<E> {
    private Node<E> parent;
    private List<Node<E>> children;
    private E value;
    private int maxChildren;

    public Node(int k, E value) {
        parent = null;
        children = new ArrayList<>();
        this.value = value;
        maxChildren = k;
    }

    public Node<E> findNode(Node<E> node) {
        /* find the first node without 3 children */

        if (node.numchildren() != arity) { /* arity is 3 in this case */
            return node;
        } else {
            newchildren = reverse(node.children); /* reverse because I want to scan from right to left */
            for (Node temp : newchildren) {
                return findNode(temp);
            }
        }
    }
}

这里的问题是，我试图找到深度最小的节点（最接近根），最右边的节点没有 3 个子节点。但是我在上面实现它的方式，它将以“后序遍历”方式检查节点。

例如，[tree example] = 在这棵树中，该方法旨在返回 n3，因为 n3 具有最小深度（1），并且在满足条件的节点中最右边。但是，使用上面的代码，我认为它会返回节点 n7，因为它从 n4 遍历到 n7，而不是从 n4 到 n3。有人可以帮我找到解决方案吗？

标签： java

解决方案

出于某种原因，我看不到您的图像，但是如果您想从右到左遍历，最简单的方法是将您的 for 循环更改为从结束索引开始并向后移动，即：

public Node<E> findNode(Node<E> node) {
    /* find the first node without 3 children */

    if (node.numchildren() != arity) { 
        return node;
    } else {
        List<Node<E>> newchildren = node.children; 
        for (int i = newchildren.size(); i > 0; i--) {
            return findNode(newchildren.get(i));
        }
    }
}

推荐阅读