我解決了一個練習，我必須將遞回演算法應用于如此定義的樹：
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
我必須將葉子的資料與父母的資料連接起來，依此類推，直到我們到達將擁有所有葉子資料總和的根。我以這種方式解決了它并且它有效，但它似乎非常曲折和機械：
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()
基本上我檢查傳遞的節點樹是否有子節點：如果沒有，它保持相同的資料。如果有孩子，我檢查是否有侄女：在這種情況下，我重新啟動演算法，直到我可以將一些葉子放到前終端節點，然后我將葉子值相加以將該總和放入他們父母的資料中。然后，我在第一個 while 回圈之后使用代碼對根節點進行操作，因此將其名稱作為所有葉子的總和。最后一段代碼用于使每個步驟中的兄弟姐妹的代碼都可以。我該如何改進它？
uj5u.com熱心網友回復：
在我看來，您的方法執行了很多冗余的遞回呼叫。
例如，您的代碼中的這個回圈：
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回傳為節點及其所有兄弟節點計算的資料。這避免了執行前一個解決方案的 while 回圈。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/411305.html
標籤：