java - 查找树的最大宽度的算法，不使用节点结构

Question

我想知道如何计算一棵树的最大宽度。我没有使用典型的叶/节点结构，而是基于来自数据库的数据。我将找到特定“节点”(人)的所有子节点以确定对等线的最大宽度:

     1
    /  \
   2    3
 / | \     \
4  5  6     7 
          /  \
         8    9

所以上面那棵树的最大值是 4。因为我没有使用传统的左/右方法，而且 child 的数量可以大于 2，我该怎么做呢？

一些事情:

• 这不是家庭作业
• 我下面的代码生成的最大宽度大约为 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
  }
}

Answer 1

我没有真正检查过您的代码，但我会使用广度优先搜索方法。

一些伪代码:

start with list containing just the trees root. call it CurrNodes.
maxWidth = 1;
start with empty list. call it NextNodes.
while(CurrNodes is not empty) {
   get all children of nodes in CurrNodes and add them to NextNodes
   if number of children is > maxWidth, # of children is the new maxWidth
   CurrNodes = NextNodes
   NextNodes = empty.
}