python - Python - 是否有更好/更有效的方法来查找树中的节点？

Question

我有一个定义如下的节点数据结构，并且不确定 find_matching_node 方法是pythonic还是有效的。我不太熟悉生成器，但认为使用它们可能会有更好的解决方案。有任何想法吗？

class HierarchyNode():

    def __init__(self, nodeId):
        self.nodeId = nodeId
        self.children = {} # opted for dictionary to help reduce lookup time

    def addOrGetChild(self, childNode):
        return self.children.setdefault(childNode.nodeId,childNode)


    def find_matching_node(self, node):
        '''
        look for the node in the immediate children of the current node.
        if not found recursively look for it in the children nodes until 
        gone through all nodes
        '''
        matching_node = self.children.get(node.nodeId)
        if matching_node:
            return matching_node
        else:
            for child in self.children.itervalues():
                matching_node = child.find_matching_node(node)
                if matching_node:
                    return matching_node
            return None

Answer 1

根据您在树上需要的其他操作，以及您需要执行此递归的频率，您可以将所有后代节点存储在节点上的字典中，因此整个递归函数可以是单个字典查找。

Answer 2

FWIW，您最好使用可重用的树数据结构，而不是重新发明轮子。根据运行时和工作负载，我见过的 CPython 最好的描述如下：http: //stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/

...但简而言之，我看到的最好的是splay树、AVL树和treap。