递归后序树遍历

Question

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

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

第一步：对于每个叶子节点n，创建一个集合Sn，里面包含这个叶子节点分配的字母。

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

第三步：对于每个有父节点p的内部节点n，给n.seq分配一个字符，具体规则是：• 如果p.seq在Sn中，就让n.seq等于p.seq。 • 否则（或者如果n是根节点），就从Sn中任意选一个字符。

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

我已经完成了第一步，现在需要通过递归的方式进行后序遍历，给每个节点分配集合。我在想该怎么开始这个过程？

使用前序递归遍历树的方式是这样的（这只是一个示例，用来计算树的长度，长度由树中叶子节点的数量决定。叶子节点是指没有子节点的节点）：

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

Answer 1

这其实很简单，你只需要在一个节点没有左孩子和右孩子的时候，才把它标记为已访问。等到根节点被访问完，整个算法就结束了。如果用递归的方法来做，这个算法会更简单。

为了让你的算法得到正确的结果，在后序遍历的时候，返回一个分配的字符串（如果是叶子节点，它会是一个单独的字符），或者返回一个空字符（如果没有孩子节点，不管是左边还是右边）。

在后序遍历的函数里，把返回的字符串连接起来，然后返回这个连接后的字符串。

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