用于查找树的最大宽度而不使用节点结构的算法

I'm trying to figure out how to calculate the max width of a tree. Instead of using a typical leaf/node structure, I am basing it on data from a DB. I will find all the children of a particular "node" (Person) to determine the max width of a peer line:

我正在试图弄清楚如何计算树的最大宽度。我没有使用典型的叶/节点结构，而是基于数据库中的数据。我将找到特定“节点”（Person）的所有子节点来确定对等线的最大宽度：

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

So the max of that tree above is 4. Since I am not using a traditional left/right approach AND the number of children can be greater than 2, how would I do this?

所以上面那棵树的最大值是4.由于我没有使用传统的左/右方法而且孩子的数量可能大于2，我该怎么办呢？

Couple things:

情侣：

This is NOT homework
这不是功课
The code I have below is generate a max width of roughly 3200 (the max I calculated for the example I have handy is 22)
我下面的代码生成的最大宽度约为3200（我为方便的示例计算的最大值为22）

Here is my code as of now:

这是我现在的代码：

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
  }
}

2 个解决方案

#1

I have not really inspected your code but, I would use a breadth first search approach.

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

some psuedo code:

一些伪代码：

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.
}

#2

A way to solve the problem is using a counter array with the length of the tree height, then for each level you seek you can add the counter of the nodes in the array, in the end you just need to get the index with max value in the array. Modifying your code, it could be something like this:

解决问题的一种方法是使用具有树高的长度的计数器数组，然后对于您寻找的每个级别，您可以添加数组中节点的计数器，最后您只需要获得具有最大值的索引在数组中。修改你的代码，它可能是这样的：

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 heightOfChart = h;
    int i;
    //create the counter array, initialized with 0 values by default
    int[] levelWidth = new int[h];
    if (parent != null) {
        levelWidth[0] = 1;
        //I suppose that your "parent" var is the root of your tree.
        fillWidth(parent, 1, levelWidth);
    }
    for(int width : levelWidth) {
        maxWidth = Math.max(maxWidth, width);
    }
    return maxWidth;
}

private void fillWidth(Person parent, int level, int[] levelWidth) {
    List<Person> allChildren = getChildren(parent);
    if (allChildren != null && !allChildren.isEmptty())
        levelWidth[level] += allChildren.size();
        for(Person child : allChildren) {
            fillWidth(parent, level + 1, levelWidth)
        }
    }
}

#1