在Python中查找並返回樹中的節點

class WNode(object): 
    def __init__(self,w): 
     self._w=w 
     self._content=[] 
    def find(self, x): 
     if self._w is x: 
      return self 
     else: 
      for i in self._content: 
       return i.find(x) 
     return None

嗨。我有麻煩創建一個方法tree.find（self，x），如果x存在（使用遞歸），它返回樹中名稱爲x的節點。我寫的那個似乎只在某些情況下工作（在幾個級別的簡單樹中），但在其他情況下（特別是在較大的樹中），即使存在節點，它也返回None。有人知道如何創建一個返回x節點的工作find（self，x）方法？在Python中查找並返回樹中的節點

來源

2014-11-22 BamLess

@unixer我想搜索節點x。因此，如果它等於self._w（節點的名稱），它將返回節點本身，否則程序將在每個子節點中搜索一個self._w，它等於x遞歸地等於x。但顯然它不起作用 – BamLess 2014-11-22 22:46:22

請添加失敗的插入方法和測試用例。 – blaze 2014-11-22 22:49:57

@blaze我使用一個函數來創建樹。但它不起作用，即使在如下簡單的樹上：r = WNode（'1'）r._content = [WNode（'2'），WNode（'3'）]。如果我鍵入>> r.find（'1'），它將返回根節點，並且與>> r.find（'2'）相同。但是>> r.find（'3'）即使r中存在'3'節點也不會返回None – BamLess 2014-11-22 23:01:28

替代答案。與您的和Todd Tao的解決方案類似，它實現了DFS。然而，一旦它完成了一個分支的探索失敗，它會繼續下一個分支。你的代碼只搜索最左邊的分支。

class WNode(object): 

    def __init__(self,w): 
     self._w=w 
     self._content=[] 

    def find(self, x): 
     if self._w == x: 
      return self 
     else: 
      y = None 
      for i in self._content: 
       y = i.find(x) 
       if y: 
        break 
      return y 
     return None 

if __name__ == '__main__': 
    r = WNode(1) 
    r._content = [WNode(2), WNode(3), WNode(4)] 
    for i in xrange(1, 6): 
     print('find({}) = {}'.format(i, r.find(i)))

來源

2014-11-22 23:26:05 blaze

如果我手動創建一棵樹，但它不起作用由我的功能生成，我不知道爲什麼。我通過一個打印樹木的功能檢查，但手動創建和創建的功能看起來是一樣的：S – BamLess 2014-11-23 00:26:03

無法修復！我換成了== – BamLess 2014-11-23 00:37:53

ok，相應更新 – blaze 2014-11-23 01:05:44

這是因爲您的find函數僅查找最左側分支中的節點。樹下面的一個例子的思考：你正在尋找的節點C.

 A 
    / \ 
    B  C 
/\ 
D E

鑑於你find功能看起來支路B先，然後檢查D. d一直沒有孩子，因此結束for循環，返回None。由於返回的東西不會搜索其他分支。

其實如果你想在樹中找到一個節點，你應該實現BFS或DFS算法遍歷你的樹。由於您的find功能是DFS，我會爲你的代碼DFS：

def find(self,x): 
    s_list = [] 
    if self._w is x: 
    return self 
    else: 
    s_list.extend(self._content) 
    while s_list: 
     node = s_list.pop() 
     if node._w is x: 
     return node 
     else: 
     s_list.extend(node._content) 
    return None

s_list作品記錄了每個節點find應該檢查的搜索路徑。如果所有節點都已檢查，則返回None。

來源

2014-11-22 23:14:45

在Python中查找並返回樹中的節點

回答

相關問題