树的深度算法作为函数定义，而不是作为方法定义

Question

我写了一个算法来递归地获取树的深度。作为函数定义，它有效：

def tree_depth_f(tree):
    """Counts the maximum depth of a tree."""        
    def recursive_count(node):
        """Recursive count function."""
        childs = tree[node]
        if childs == None:
            return 0
        else:
            maxh = 0
            for i in xrange(len(childs)):
                h = recursive_count(childs[i])
                if maxh < h:
                    maxh = h                
            return int(1 + maxh)

    root = tree['root']
    depth = recursive_count(root)
    return depth

但是与方法定义相同的算法不起作用：

class MyClass:
    def __init__():
        pass

    def tree_depth(self, tree):
        """Counts the maximum depth of a tree."""        
        def recursive_count(node):
            """Recursive count function."""
            self.childs = tree[node]
            if self.childs == None:
                return 0
            else:
                self.maxh = 0
                for i in xrange(len(self.childs)):
                    self.h = recursive_count(self.childs[i])
                    if self.maxh < self.h:
                        self.maxh = self.h                
                return int(1 + self.maxh)

        self.root = tree['root']
        self.depth = recursive_count(self.root)
        return self.depth

tree 是一个列表字典。这就是我测试这些代码的方式：

tree = {0: [1], 1: [2], 2: [3, 4], 3: None, 4: None, 'root': 0}
m = MyClass()
print "As a function:", tree_depth_f(tree)
print "As a method:", m.tree_depth(tree)

这是本例中 tree 的图形表示：

函数定义工作正常，但是当我使用方法定义时，出现以下错误：

TypeError: 'NoneType' object has no attribute '__getitem__'
    at Answer.py. in recursive_count on line 102
    at Answer.py. in recursive_count on line 102
    at Answer.py. in recursive_count on line 102
    at Answer.py. in tree_depth on line 108
    at Answer.py. in <module> on line 157

原代码中第102、108、157行指向这些：

102: self.h = recursive_count(self.childs[i])
108: self.depth = recursive_count(self.root)
157: print "As a method:", m.tree_depth(tree)

经过大量debug，我发现当方法定义找到叶子（self.childs为None的节点）开始递归返回时，self.childs父节点的也是 None。我不知道为什么。函数定义工作正常。你们能帮帮我吗？

Answer 1

您正在修改 self.childs，它在这里有效地充当全局变量（因为它被记录在对象上，通过对递归函数的不同调用持续存在）。每个节点没有一个对象，只有一个对象，句号。所以没有“self.childs的父节点”，你只有一个self.childs，在一个self上。当递归从 return 0 分支退出时，变量 self.childs 为 None.

在你的函数代码中，你的childs是一个局部变量，所以每次函数调用都会得到一个单独的副本；你真的需要这个，无论是在方法上还是在函数上。

删除self.即可，不需要childs是实例变量。事实上，任何变量都不需要是实例变量，因为您没有使用任何面向对象的功能。

树的深度算法作为函数定义，而不是作为方法定义

An algorithm of tree's depth works as a function definition, but not as a method definition

python

oop

tree

recursion

depth