算法寻找一棵树的最大宽度，不使用节点结构 [英] Algorithm to find the max width of a tree, not using node structures

问题描述

我试图找出如何计算一棵树的最大宽度。而不是使用一个典型的钢板/节点结构的，我是从一个数据库的数据基础了。我会找到一个特别的节点（人）的所有孩子，以确定对行的最大宽度：

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

所以，该树的最大上面是4。由于我没有使用传统的左/右的做法和儿童的数量可以大于2，我将如何做到这一点？

几件事情：

• 这不是功课
• 的code我下面是产生大约3200最大宽度（我计算的例子，我有得心应手最大为22）

下面是我的code截至目前：

 私人诠释calculateWidth（DEF ORG，诠释高）{

    高清allContacts = Contact.findAllByOrganization（组织）
    名单＆LT;字符串＆GT; headNodes = findHighestNode（org.id，allContacts）

    联系方式联系方式= Contact.get（的Long.parseLong（headNodes.get（0）））
    人父=新的Person（contact.id，contact.fullName）

    INT了maxWidth = 0;
    INT宽度;
    INT heightOfChart = H;
    INT I;

    对于（i = 1; I＆LT; = heightOfChart;我++）
    {
      宽度=的getWidth（父母，我）;

      如果（宽＆GT;了maxWidth）
        =了maxWidth宽度;
    }

    的System.out.println（最大宽度=+了maxWidth）
    返回（（NODE_HEIGHT + NODE_OFFSET）*（了maxWidth））
}

私人诠释的getWidth（人父，INT级）
{

  名单＆LT;人＆GT; allChildren =的getChildren（母公司）

  如果（allChildren.size（）== 0）
    返回0;

  如果（水平== 1）
    返回1;

  否则，如果（等级大于1）{
    诠释计数= 0
    对于（人子：allChildren）{
        数=计数+的getWidth（父母，1级）
    }
    返回计数
  }
}
 

解决方案

我还没有真正检查你的code，但我会用一个广度优先搜索方法。

一些伪code：

 开始只包含树的根目录。称之为CurrNodes。
了maxWidth = 1;
先从空单。称之为NextNodes。
而（CurrNodes不为空）{
   得到CurrNodes节点的所有儿童，并把它们添加到NextNodes
   如果孩子的数量是＆GT;了maxWidth，＃儿童是新了maxWidth
   CurrNodes = NextNodes
   NextNodes =空。
}
 

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:

     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?

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)

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

解决方案

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

这篇关于算法寻找一棵树的最大宽度，不使用节点结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！