基于@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());
}
}
}