Python -有没有更好/更有效的方法来在树中查找节点？

Question

我不是很精通生成器，但我认为使用它们可能会有更好的解决方案。有什么想法吗？

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

顺便说一句，你最好使用一个可重用的树形数据结构，而不是重复发明轮子。根据运行时和工作负载的不同，我所见过的最好的CPython描述如下：http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/

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