如何遞歸遍歷一個樹和蟒蛇

創建訪問節點列表，我已經定義了一類樹，其由如下樹節點的列表：如何遞歸遍歷一個樹和蟒蛇

class Tree(object): 
    def __init__(self, name, nodes): 
     self.name = name 
     self.nodes = nodes 

class TreeNode(object): 
    def __init__(self, name, parent): 
     self.name = name 
     self.parent = parent

正如你所看到的，每個樹節點我只定義一個父節點。但是，我想編寫一個Tree方法，它給了我一個名爲targetNodeName的目標節點的所有父節點的列表（輸出列表還應該包含targetNodeName本身）。爲此，我編寫了一個遞歸函數，該函數在建立一個名爲results的列表時找到沒有父節點的節點（即根節點）。

def allParents(self, targetNodeName, results): 
    currentNode = next((node for node in self.nodes if node.name == targetNodeName)) 
    results.append(currentNode.name) 
    if (currentNode.parent == None): 
     print results 
     return results 
    else: 
     return results.append(self.allParents(currentNode.parent, results))

但是，我的遞歸函數沒有按預期執行。我舉了一個例子，首先定義一個三級的7節點樹，然後調用allParents方法來獲取節點'N7'的所有父節點，即['N7'，'N3'，'N1']。

# create nodes 
myTreeNodes = [] 
myTreeNodes.append(TreeNode(name = 'N1', parent = None)) 
myTreeNodes.append(TreeNode(name = 'N2', parent = 'N1')) 
myTreeNodes.append(TreeNode(name = 'N3', parent = 'N1')) 
myTreeNodes.append(TreeNode(name = 'N4', parent = 'N2')) 
myTreeNodes.append(TreeNode(name = 'N5', parent = 'N2')) 
myTreeNodes.append(TreeNode(name = 'N6', parent = 'N3')) 
myTreeNodes.append(TreeNode(name = 'N7', parent = 'N3')) 

myTree = Tree(name = 'ST1', nodes = myTreeNodes) 

a = myTree.allParents(targetNodeName = 'N7', results = []) 
print a 

> ['N7', 'N3', 'N1'] 
> None

雖然它打印出父節點的正確的列表 - 注意在功能 - 的「調試」的打印命令（即[「N7」，「N3」，「N1」]），該函數返回無，這意味着我從功能中退出，沒有任何回報。我怎樣才能解決這個問題？

來源

2016-11-22 ikonikon

使用是用於檢查該值是否等於無或不。的allParents方法可以簡化爲以下幾點：

def allParents(self, targetNodeName): 
    currentNode = next(node for node in self.nodes 
         if node.name == targetNodeName) 
    if currentNode.parent is None: 
     return [currentNode.name] 
    else: 
     return [currentNode.name] + self.allParents(currentNode.parent)

來源

2016-11-22 19:55:49

謝謝！這很好！ – ikonikon

使用debugger單步執行該方法對於確定代碼所採用的路徑非常有幫助。

使用這個我可以看到該方法最初遵循else分支，它只是導致打印語句的子調用self.allParents。問題在於results.append，它始終返回None而不是列表。

a = [] 
b = a.append(3) 
assert a == [3] 
assert b is None

的最簡單的解決辦法是分割線成原始results.append，隨後return results。

來源

2016-11-22 19:53:00 QasimK

如何遞歸遍歷一個樹和蟒蛇

回答

相關問題