连接树数据 - 如何简化我的代码？

Question

我解决了一个练习，在这个练习中我必须将递归算法应用于如此定义的树：

class GenericTree:
    """ A tree in which each node can have any number of children. 
    
        Each node is linked to its parent and to its immediate sibling on the right
    """
    
    def __init__(self, data):
        self._data = data
        self._child = None
        self._sibling = None
        self._parent = None

我必须将叶子的数据与 parents 的数据连接起来，依此类推，直到我们到达将具有所有叶子数据总和的根。我以这种方式解决了它并且它有效但它似乎非常曲折和机械：

    def marvelous(self):
        """ MODIFIES each node data replacing it with the concatenation 
            of its leaves data 
            
            - MUST USE a recursive solution
            - assume node data is always a string

        """
        if not self._child: #If there isn't any child
            self._data=self._data #the value remains the same
        if self._child: #If there are children
            if self._child._child: #if there are niece
                self._child.marvelous() #reapply the function to them
            else: #if not nieces
                self._data=self._child._data #initializing the name of our root node with the name of its 1st son
                #if there are other sons, we'll add them to the root name
                if self._child._sibling: #check
                    current=self._child._sibling #iterating through the sons-siblings line
                    while current: 
                        current.marvelous() #we reapplying the function to them to replacing them with their concatenation (bottom-up process)
                        self._data+=current._data #we sum the sibling content to the node data
                        current=current._sibling #next for the iteration
            #To add the new names to the new root node name:
            self._data="" #initializing the root str value
            current=self._child #having the child that through recursion have the correct str values, i can sum all them to the root node
            while current:
                self._data+=current._data
                current=current._sibling
        if self._sibling: #if there are siblings, they need to go through the function themselves
            self._sibling.marvelous()

基本上我会检查传递的节点树是否有children：如果没有，它会保留相同的数据。如果有 children，我检查是否有侄女：在这种情况下，我重新启动算法，直到我可以将一些叶子添加到 pre-terminal 节点，然后我对叶子值求和以将该总和加到它们的值上parents'数据。然后，我用第一个 while 循环后的代码作用于根节点，因此将其名称作为所有叶子的总和。最后一段代码用于使代码在每个步骤中都适合兄弟姐妹。我该如何改进它？

Answer 1

在我看来，您的方法执行了很多冗余的递归调用。

例如，您代码中的这个循环：

                    while current: 
                        current.marvelous()
                        self._data += current._data
                        current = current._sibling

没有用，因为递归调用无论如何都会由最后一个执行您方法中的说明 (self._sibling.marvelous())。除了，您更新 self._data 然后在循环之后立即重置 self._data 到 "".

我试图简化它并想出了这个似乎工作。

    def marvelous(self):
        if self.child:
            self.child.marvelous()

            # at that point we know that the data for all the tree
            # rooted in self have been computed.  we collect these
            self.data = ""
            current = self.child
            while current:
                self.data += current.data
                current = current.sibling

        if self.sibling:
            self.sibling.marvelous()

这里有一个更简单的解决方案：

    def marvelous2(self):
        if not self.child:
            result = self.data
        else:
            result = self.child.marvelous2()
            self.data = result
        if self.sibling:
            result += self.sibling.marvelous2()
        return result

marvelous2 returns 为节点及其所有兄弟节点计算的数据。这样就避免了执行前面方案的while循环

连接树数据 - 如何简化我的代码？

Concatenating tree data - How to simplify my code?

python

string

tree

recursion

concatenation