首页 文章

k阵列树产生邻接矩阵

提问于
浏览
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

2 回答

  • 1

    我有一个k-ary tree的实现(它与你链接到的我的n-ary树实现非常相似) . 它不完整,但它应该足以让你开始 .

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

  • 0

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

    输出将打印到控制台 . 需要将类 AbstractNodeAbstractTreeKAryTreeKAryTreeNodeNodeTreeTreeTraversalOrder 添加到项目中 . 这些类可以在@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());
            }
        }
    }
    

相关问题