4

为更大的树编辑，以获取更多示例。

我有一个树结构，我需要生成所有可能的排列，但有一些限制。给定一棵这样的树：

    A1----(B1, B2)
     \    
      \___(C1)
             \__(E1, E2)
/       
-  A2----(B3, B4)
\     \     \
       \     \__(D1)
        \
         \_(F1, F2)
                |
                (D4)   

    A3----(B5, B6)
                \__(D2, D3)

或者，如果这有点模糊，这里是使用 Perl 表示法完成的相同结构：

my $nodes = [
{
    name => 'A1',
    children => [
        [ { name => 'B1', children => []  }, 
          { name => 'B2', children => []  }
        ],
        [
          { name => 'C1', 
                    children => [
                        [
                            { name => 'E1', children => [] },
                            { name => 'E2', children => [] }
                        ]
                    ]
            }
        ]
    ]
},
{
    name => 'A2',
    children => [
        [ { name => 'B3', 
                children => [
                    [
                        { name => 'D1', children => [] }
                    ]
                ] 
          },
          { name => 'B4', children => [] }
        ],
        [
          { name => 'F1', children => [] },
          { name => 'F2', children => [
                        [ { name => 'D4', children => [] } ]
                    ]
            }
        ]
    ]
},
{
    name => 'A3',
    children => [
        [ { name => 'B5', children => [] },
          { name => 'B6', children => [
                    [ { name => 'D2', children => [] },
                      { name => 'D3', children => [] }
                    ] 
                ]                 
            }
        ]
    ]
}

];

（坦率地说，如果你能在可读的Perl 中解决这个问题，我也会接受。）

我正在寻找遍历树并从顶层向下检索所有可能的“路径”。一个节点的所有后代组必须由“路径”中的 1 个成员表示。例如，在 A1 中，需要表示 (B1, B2) 之一和 (C1) 之一。因此，从 A1 下降的每条路径都将从以下任一开始：

A1 B1 C1

或者

A1 B2 C1

如果 B1、B2 或 C1 有孩子，则也需要代表这些孩子。

为上面的树手动解决这个问题，我得到了这些可能性：

A1 B1 C1 E1
A1 B1 C1 E2
A1 B2 C1 E1
A1 B2 C1 E2

A2 B3 D1 F1
A2 B3 D1 F2 D4
A2 B4 F1
A2 B4 F2 D4

A3 B5
A3 B6 D2
A3 B6 D3

这里的每个节点都是一个 DataRow 对象：

internal class DataRow
{
    internal string tag = "";
    internal int id = 0;
    internal Dictionary<string, List<DataRow>> children = null;

    internal DataRow(int id, string tagname)
    {
        this.tag = tagname;
        this.id = id;
    }        internal void AddChildren(string type, List<DataRow> drList)
    {
        if (children == null)
            children = new Dictionary<string, List<DataRow>>();
        if (!children.ContainsKey(type))
            children[type] = new List<DataRow>();
        children[type].AddRange(drList);
    }
    internal void AddChild(string type, DataRow dr)
    {
        List<DataRow> drList = new List<DataRow>();
        drList.Add(dr);
        AddChildren(type, drList);
    }
    public override string ToString()
    {
        return this.tag + " " + this.id;
    }
}

要构建上面的示例树（E 和 F 级别除外，稍后添加）：

        DataRow fullList = new DataRow(null, "");
        DataRow dr, dr2, dr3;

        // First node above
        dr = new DataRow(1, "A");
        List<DataRow> drList = new List<DataRow>();
        drList.Add(new DataRow(1, "B"));
        drList.Add(new DataRow(2, "B"));
        dr.AddChildren("B", drList);
        drList.Clear();
        dr2 = new DataRow(1, "C");
        dr2.AddChild("C", new DataRow(1, "E"));
        dr2.AddChild("C", new DataRow(2, "E"));
        drList.Add(dr2);
        dr.AddChildren("C", drList);
        fullList.AddChild("A", dr);


        // Second Node above (without the "F" stuff)
        drList.Clear();
        dr = new DataRow(3, "B");
        dr.AddChild("D", new DataRow(1, "D"));
        drList.Add(dr);
        drList.Add(new DataRow(4, "B"));
        dr = new DataRow(2, "A");
        dr.AddChildren("B", drList);
        fullList.AddChild("A", dr);

        // Third node above
        drList.Clear();
        dr3 = new DataRow(6, "B");
        dr3.AddChild("B", new DataRow(2, "D"));
        dr3.AddChild("B", new DataRow(3, "D"));
        dr2 = new DataRow(3, "A");
        dr2.AddChild("B", new DataRow(5, "B"));
        dr2.AddChild("B", dr3);
        fullList.AddChild("A", dr2);

走整棵树是微不足道的：

    internal void PermutedList()
    {
        if ( children == null ) return;
        foreach (string kidType in children.Keys)
        {
            foreach (DataRow dr in children[kidType])
            {
                dr.PermutedList();
            }
        }
    }

但这不是我需要的。这个问题是一个完整的树遍历，但是按照特定的顺序。我没有得到什么？这是一种怎样的步行方式？

我在 10 年前用 Perl 编写的这个实现混乱而缓慢，但我不能再破译我自己的代码了（真丢脸！）。

编辑：下面的图表和列表已经扩展，代码没有。

如果我能描述图表，我就可以对其进行编程。如果我知道它叫什么，我可以查一下。但我不能。所以让我进一步解释一下。

存储桶名称并不重要！

每个节点都有“孩子的桶”。A1 有两个桶，一个包含“B”，另一个包含“C”。如果这就是它的全部（并且 C 下没有存储桶），我将拥有“A1 B1 C1”和“A1 B2 C1”——所有子存储桶中至少有一个代表存在。

所以我认为每个桶都需要它的孩子的叉积（一直向下）。

4

4 回答 4

3

使用以下子：

use 5.10.0;  # for // (aka defined-or)

use subs 'enumerate';
sub enumerate {
  my($root) = @_;

  my $kids = $root->{children};
  return [ $root->{name} // () ]
    unless @$kids;

  my @results;
  foreach my $node (@{ $kids->[0] }) {
    my @fronts = map [ $root->{name} // (), @$_ ],
                     enumerate $node;

    my @below = enumerate {
      name => undef,
      children => [ @{$kids}[1 .. $#$kids ] ],
    };

    foreach my $a (@fronts) {
      foreach my $b (@below) {
        push @results => [ @$a, @$b ];
      }
    }
  }

  @results;
}

你可以打印它

foreach my $tree (@$nodes) {
  foreach my $path (enumerate $tree) {
    print "@$path\n";
  }

  print "\n";
}

获得以下输出：

A1 B1 C1 E1
A1 B1 C1 E2
A1 B2 C1 E1
A1 B2 C1 E2

A2 B3 D1 F1
A2 B3 D1 F2 D4
A2 B4 F1
A2 B4 F2 D4

A3 B5
A3 B6 D2
A3 B6 D3

我在$path上面使用过，但它会严重混淆维护您的代码的任何人，因为路径具有很好理解的含义。你可以用一点聪明的方法完全绕过命名问题：

print join "\n" =>
      map { join "" => map "@$_\n", @$_ }
      map [ enumerate($_) ] => @$nodes;
于 2010-01-22T17:48:12.457 回答
1

每个节点都应该知道其父节点 (GetParentRow)，因此您可以将父节点作为参数传递给递归方法。这样，当您到达“叶子”时，您可以递归地追踪到根。

我不确定它是否是最有效的方法，但我认为它应该会给你想要的结果。

于 2010-01-20T16:49:32.150 回答
1

可以按以下所需的任何顺序执行树遍历。对于根节点，将所有子节点放入 DATA_STRUCTURE（如下所述）。然后从 DATA_STRUCTURE 中取出一个节点，并将其所有子节点放入 DATA_STRUCTURE。继续直到 DATA_STRUCTURE 为空。

诀窍是选择正确的 DATA_STRUCTURE。对于有序（深度优先）遍历，可以使用堆栈。（孩子必须以相反的顺序被压入堆栈。）为了进行深度优先遍历，可以使用队列。

对于更复杂的订单，优先队列就是门票。只需根据您希望根据您使用的任何标准遍历树的顺序设置优先级。事实上，正确设置优先级也将表现为堆栈或队列，分别导致上述深度优先和广度优先序列。

编辑添加：

树行走算法将适用于这种类型的数据结构，因为它没有循环。只需为集合中的每个项目在数据结构中放置一个新节点。我想唯一额外的是一种表示路径的方法。

这条路很容易。你只需要这样的东西：

class Path<T>
{
    T lastNode;
    Path<T> previousNodes;
    public Path(T lastNode, Path<T> previousNodes)
    {
        this.lastNode = lastNode; this.previousNodes = previousNodes;
    }
    public IEnumerable<T> AllNodes()
    {
        return AllNodesBackwards().Reverse();
    }
    private IEnumerable<T> AllNodesBackwards()
    {
        Path<T> currentPath = this;
        while (currentPath != null)
        {
            yield return currentPath.lastNode;
            currentPath = currentPath.previousNodes;
        }
    }
    public T Node { get { return lastNode; } }
}

因此，我们所要做的就是走这条路。与此类似的东西应该可以解决问题：

[不正确的解决方案已删除]

再次编辑：

好的，我终于知道你想要什么了。在沿着树向下移动之前，您希望在每条路径中水平穿越不同“kidTypes”的孩子。

这是一个大麻烦，但我解决了它：

public void WalkPath2()
{
    Queue<Path<DataRow>> queue = new Queue<Path<DataRow>>();
    queue.Enqueue(new Path<DataRow>(this, null));

    while (queue.Count > 0)
    {
        Path<DataRow> currentPath = queue.Dequeue();
        DataRow currentNode = currentPath.Node;

        if (currentNode.children != null)
        {
            foreach (Path<DataRow> nextPath in currentNode.GetChildPermutations(currentPath))
                queue.Enqueue(nextPath);
        }
        else
        {
            foreach (DataRow node in currentPath.AllNodes())
            {
                Console.Write(node.ToString());
                Console.Write("      ");
            }
            Console.WriteLine();
        }

    }

}

private IEnumerable<Path<DataRow>> GetChildPermutations(Path<DataRow> currentPath)
{
    string firstLevelKidType = null;
    foreach (string kidType in children.Keys)
    {
        firstLevelKidType = kidType;
        break;
    }
    foreach (Path<DataRow> pathPermutation in GetNextLevelPermutations(currentPath, firstLevelKidType))
        yield return pathPermutation;
}

private IEnumerable<Path<DataRow>> GetNextLevelPermutations(Path<DataRow> currentPath, string thisLevelKidType)
{
    string nextLevelKidType = null;
    bool nextKidTypeIsTheOne = false;
    foreach (string kidType in children.Keys)
    {
        if (kidType == thisLevelKidType)
            nextKidTypeIsTheOne = true;
        else
        {
            if (nextKidTypeIsTheOne)
            {
                nextLevelKidType = kidType;
                break;
            }
        }
    }

    foreach (DataRow node in children[thisLevelKidType])
    {
        Path<DataRow> nextLevelPath = new Path<DataRow>(node, currentPath);
        if (nextLevelKidType != null)
        {
            foreach (Path<DataRow> pathPermutation in GetNextLevelPermutations(nextLevelPath, nextLevelKidType))
                yield return pathPermutation;
        }
        else
        {
            yield return new Path<DataRow>(node, currentPath);
        }
    }


}
于 2010-01-21T19:44:13.497 回答
0

首先我以为你想要所有的生成树。http://en.wikipedia.org/wiki/Spanning_tree

但后来我意识到你想要的是从树根上“跨越式行走”。

然后我意识到它（相对）简单。

Foreach leaf

Walk from the leaf to the root

end for

当然，您将需要一个真正的数据结构，我认为 Perl 的哈希值不会起作用；您需要在每个节点中都有一个“父”指针。

于 2010-01-21T19:33:35.387 回答