3

木の最大幅を計算する方法を理解しようとしています。典型的なリーフ/ノード構造を使用する代わりに、DBからのデータに基づいています。特定の「ノード」（Person）のすべての子を見つけて、ピアラインの最大幅を決定します。

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

したがって、上のツリーの最大値は4です。従来の左/右アプローチを使用しておらず、子の数が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
  }
}
4

2 に答える 2

4

私はあなたのコードを実際に検査していませんが、幅優先探索アプローチを使用します。

いくつかの疑似コード：

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.
}
于 2012-08-14T14:20:50.530 に答える
1

この問題を解決する方法は、ツリーの高さの長さのカウンター配列を使用することです。次に、探しているレベルごとに、配列内のノードのカウンターを追加できます。最終的には、最大値のインデックスを取得する必要があります。配列内。コードを変更すると、次のようになります。

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)
        }
    }
}
于 2012-08-14T15:13:37.083 に答える