我正在试图计算树的最大宽度。不使用典型的叶子/节点结构,而是基于来自数据库的数据。我将查找特定“节点”(人)的所有子代,以确定同级行的最大宽度:
1
/ \
2 3
/ | \ \
4 5 6 7
/ \
8 9
因为我没有使用传统的左右方法,而且子节点数量可以大于2,因此上述树的最大值是4。那么我该如何做呢?
有几点需要注意:
- 这不是作业
- 我现在的代码生成的最大宽度大约是3200(我手头的示例计算出的最大宽度为22)
以下是我的当前代码:
private int calculateWidth(def org, int h) {
def allContacts = Contact.findAllByOrganization(org)
List<String> headNodes = findHighestNode(org.id, allContacts )
Contact contact = Contact.get(Long.parseLong(headNodes.get(0)))
Person parent = new Person(contact.id, contact.fullName)
int maxWidth = 0;
int width;
int heightOfChart = h;
int i;
for(i = 1; i <= heightOfChart; i++)
{
width = getWidth(parent, i);
if(width > maxWidth)
maxWidth = width;
}
System.out.println("The max width is = " + maxWidth)
return ((NODE_HEIGHT + NODE_OFFSET) * (maxWidth))
}
private int getWidth(Person parent, int level)
{
List<Person> allChildren = getChildren(parent)
if(allChildren.size() == 0)
return 0;
if(level == 1)
return 1;
else if (level > 1) {
int count = 0
for(Person child : allChildren) {
count = count + getWidth(parent, level-1)
}
return count
}
}
4 5 6 7
吗?也就是某个深度上的最大宽度? - maba