递归提交订单树浏览

Question

我想实现如下算法：

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

第1步：对于每一个叶节点n，打造一个集Sn包含叶的 指定的字母。

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

3步骤：对于每一个内部节点n与父P，分配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 

Answer 1

它非常简单直观，只有在节点没有更多的左右儿童时才标记为已访问节点。访问根节点后，算法结束。如果使用递归进行，该算法就容易得多。

为了让你的算法得到适当的设置，让你的顺序遍历返回它的赋值字符串（如果它是一个叶子，它将是一个字符）或空白字符（应该没有孩子，无论是正确的或剩下）。

在后期订单功能中，附加返回的字符串，然后返回附加的字符串。

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