1

我正在尝试实现以下算法：

Fitch 的算法（对于一个字符序列）：

步骤 1：对于每个叶节点 n，创建一个包含叶分配字母的集合 Sn。

第 2 步：对于每个具有子 u 和 v 的内部节点 n，创建一个集合 Sn 等于： • 如果 Su ∩ Sv 不为空，则 Su ∩ Sv。• 如果Su ∩ Sv 为空，则Su U Sv。

第 3 步：对于每个具有父 p 的内部节点 n，分配 n.seq 一个字符等于： • p.seq 如果 p.seq ∈ Sn • 否则 Sn 的任何字符（或者如果 n 是根）。

我得到一个二叉树作为输入。

我已经完成了第一步，现在需要通过二叉树递归地进行后序导航，以将集合分配给每个节点。我想知道如何开始这个？

使用前序递归在树中导航是这样完成的（这只是一个计算树长度的示例，该长度取决于树中有多少叶子。叶子 = 没有孩子）：

def __len__(self):

     if self.isLeaf():
        print('base case - reached leaf!')
        return 1

    for t,w in self.children:  
        print('not leaf so sent through loop')
        numLeaves += len(t)

    return numLeaves
4

1 回答 1

1

这很简单，您只需在节点不再有左右子节点后将其标记为已访问。根节点被访问后，算法结束。如果使用递归完成，该算法会容易得多。

要为您的算法获取正确的集合，请让您的后序遍历返回它的分配字符串（如果它是叶子，它将是单个字符）或空白字符（如果没有孩子，无论是右边还是左边）。

在 post order 函数中，追加返回的字符串，然后返回追加的字符串。

http://en.wikipedia.org/wiki/Tree_traversal#Post-order

于 2013-02-28T20:30:47.950 回答