0

您好我正在尝试使用 Java 实现其输出为相邻矩阵形式的 k 数组树。给定的输入参数是 k = 每个节点的子节点数和 d = 树的深度（高度）。

给定这些参数，我必须生成 k 数组树的相邻矩阵（写在文件上）。你能指导我实施吗？

我已经查看了以下链接，但由于我是 Java 初学者，所以我无法关注。所以有人可以指导我吗？

http://vivin.net/2010/01/30/generic-n-ary-tree-in-java/

http://sujitpal.blogspot.com/2006/05/java-data-structure-generic-tree.html

4

2 回答 2

1

我有一个k-ary 树的实现（它与您链接到的我的 n-ary tree 实现非常相似）。它不完整，但它应该给你足够的开始。

要生成邻接矩阵，您需要一个具有维度的二维数组n x k。然后，您必须遍历树并填充邻接矩阵。一行i将对应于 nodei并且matrix[i][0]tomatrix[i][k - 1]将包含对knode 子级的引用i。当然，邻接矩阵中节点的顺序将取决于您的遍历方法。

于 2013-07-24T18:54:37.657 回答
0

基于@VivinPaliath 提供的代码，我添加了一个可以生成邻接矩阵的简单（脏）脚本，其中k控制子节点的数量，d控制树的深度。KAryTreeNode的类型设置为 Integer，因为它存储了节点的索引。

输出打印到控制台。需要将类AbstractNode、AbstractTree、KAryTree、KAryTreeNode、Node、Tree和TreeTraversalOrder添加到项目中。这些类可以在@VivinPaliath 的 Github 存储库中找到。

public class KAryTreeGenerator {

    public static Integer index = 0;

    public static void populate(KAryTreeNode<Integer> node, int height, int k) {
        if (height == 0) {
            // nothing more to do
        } else {

            for (int i = 0; i < k; i++) {
                node.addChild(new KAryTreeNode<>(k, index));
                index = index + 1;
            }

            for (int i = 0; i < k; i++) {
                populate(node.getChildAt(i), height - 1, k);
            }
        }
    }

    public static void main(String[] args) {

        int k = 3; // number of children
        int d = 3; // depth

        KAryTreeNode<Integer> root = new KAryTreeNode<>(k, index);
        index = index + 1;

        KAryTree<Integer> tree = new KAryTree<>(k, root);

        d = d - 1;
        populate(tree.root, d, k);

        int size = (int)((Math.pow((double)k, (double)(d+1) ) - 1)/(k - 1));

        int[][] adjacencyMatrix = new int[size][size];

        List<KAryTreeNode<Integer>> queue = new LinkedList<>();

        queue.add(root);

        while(!queue.isEmpty()) {

            KAryTreeNode<Integer> parent = queue.remove(0);

            List<KAryTreeNode<Integer>> children = parent.getChildren();

            for(KAryTreeNode<Integer> child: children) {
                // adjacencyMatrix[child.data][parent.data] = -1; //shows the parent in the matrix
                adjacencyMatrix[parent.data][child.data] = 1;
            }
            queue.addAll(children);
        }

        for (int i = 0; i < adjacencyMatrix.length; i++) {
            StringBuilder builder = new StringBuilder();
            builder.append(Arrays.toString(adjacencyMatrix[i]));
            builder.deleteCharAt(0);
            builder.deleteCharAt(builder.toString().length()-1);
            System.out.println(builder.toString());
        }
    }
}
于 2018-03-19T10:31:30.577 回答