使用非静态方法遍历二叉树？

Question

我编写的 BinTree class 看起来像这样：

class Tree:
    def __init__(self, key, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

    @staticmethod
    def traversal(t):
        if t is None:
            #  Do something
            pass
        else:
            #  Preorder
            Tree.traversal(t.left)
            #  Inorder
            Tree.traversal(t.right)
            #  Postorder

我很好奇用非静态方法来做这件事。我尝试这样做似乎不起作用：

def traversal(self):
    if self is None:
        #  Do something
        pass
    else:
        #  Preorder
        self.left.traversal()
        #  Inorder
        self.left.traversal()
        #  Postorder

难道是因为self不能None？

无论如何，我想知道是否可以使用递归或迭代的非静态方法进行 BinTree 遍历（甚至其他方法，如插入等）？

Answer 1

是的，在正常的方法调用中self确实不能None。¹如果是None，你会尝试调用方法时出错。²

但这只是意味着你必须稍微重新组织一下：而不是无条件地在你的子树上调用 traversal，指望如果它们是 None，它将安全地不做任何事情，你必须先检查他们是否 None 才能跳过通话。

因为 Tree 实例总是真实的（因为你没有在类型上定义 __bool__ 或 __len__ 来覆盖默认值），你可以这样检查它：

if self.left:

所以：

def traversal(self):
    #  Preorder
    if self.left: self.left.traversal()
    #  Inorder
    if self.right: self.right.traversal()
    #  Postorder

您可以类似地将每个树方法变成普通方法——但您同样必须对其中一些方法进行小的更改。

_{1.好吧，除了 NoneType 上定义的方法。显然当你 print(None) 时，在 NoneType.__str__ 方法中， self 是 None…}

_{2。好吧，这不是真的。如果您在 self.left 为 None 时尝试调用 self.left.traversal()，您将调用 NoneType.traversal，并且没有这样的方法，因此这是一个 AttributeError。但是，如果您尝试调用 Tree.traversal(self.left)，另一方面，您正在尝试使用 None 调用未绑定的 Tree 方法，这是一个 TypeError——但它是一个Python 3.x（不像2.x）实现不需要检查。到目前为止，CPython 或 PyPy 3.x 的任何版本都没有检查过，而且它们可能永远也不会检查。所以，如果你这样写，它实际上会工作。但这显然不是你应该依赖的东西。}

使用非静态方法遍历二叉树？

Binary Tree traversal with non-static methods?

python

binary-tree