使用非节点结构的算法来查找树的最大宽度

Question

我正在试图计算树的最大宽度。不使用典型的叶子/节点结构，而是基于来自数据库的数据。我将查找特定“节点”(人)的所有子代，以确定同级行的最大宽度:

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

- user82302124

---

请注意，每个节点可以拥有多于两个孩子的二叉树不是二叉树，只是一棵普通的树。此外，我认为你所说的“宽度”通常被称为“高度”或“深度”。最后，我认为对于任意树来说计算这个最大值是不可能的。 - yshavit

实际上，等等，你的意思是树的最大高度/深度，还是任何一个节点所拥有的最大子节点数？（编辑：或者是maba的定义，或其他定义？） - yshavit

你所说的“宽度”，是指示例中的 4 5 6 7 吗？也就是某个深度上的最大宽度？ - maba

是的 - 从高度h开始，我将检查每一行的宽度（因此第1行=1，第2行=2，第3行=4，第4行=2），最大宽度为4。 - user82302124

我猜我的回答来晚了。 - Luiggi Mendoza

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

- Colin D

---

这几乎就是我所做的 - 我会在清理后发布我的答案以供将来使用。 - user82302124

Answer 2

解决问题的一种方法是使用一个计数器数组，其长度为树的高度，然后对于每个要查找的级别，您可以将数组中节点的计数器相加，在最后您只需要获取数组中最大值的索引即可。修改您的代码，可能会像这样：

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

- Luiggi Mendoza