这个递归二叉树函数类型有一些错误

Question

我尝试检查并修复代码，但我找不到此代码的任何问题

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()
    
    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)


class BinaryTree:
    def __init__(self, root):
        self.key = root
        self.left_child = None
        self.right_child = None

    def insert_left(self, new_node):
        if self.left_child == None:
            self.left_child = BinaryTree(new_node)
        else:
            t = BinaryTree(new_node)
            t.left_child = self.left_child
            self.left_child = t

    def insert_right(self, new_node):
        if self.right_child == None:
            self.right_child = BinaryTree(new_node)
        else:
            t = BinaryTree(new_node)
            t.right_child = self.right_child
            self.right_child = t

    def get_right_child(self):
        return self.right_child

    def get_left_child(self):
        return self.left_child
    
    def set_root_val(self, obj):
        self.key = obj

    def get_root_val(self):
        return self.key

    def preorder(tree):
        if tree:
            print(tree.get_root_val())
            preorder(tree.get_left_child())
            preorder(tree.get_right_child())

    def postorder(tree):
        if tree != None:
            postorder(tree.get_left_child())
            postorder(tree.get_right_child())
            print(tree.get_root_val())

    def inorder(tree):
        if tree != None:
            inorder(tree.get_left_child())
            print(tree.get_root_val())
            inorder(tree.get_right_child())


def build_parse_tree(fp_exp):
    fp_list = fp_exp.split()
    p_stack = Stack()
    e_tree = BinaryTree('')
    p_stack.push(e_tree)
    current_tree = e_tree
    for i in fp_list:
        if i == '(':
            current_tree.insert_left('')
            p_stack.push(current_tree)
            current_tree = current_tree.get_left_child()
        elif i not in ['+', '-', '*', '/', ')']:
            current_tree.set_root_val(int(i))
            parent = p_stack.pop()
            current_tree = parent
        elif i in ['+', '-', '*', '/']:
            current_tree.set_root_val(i)
            current_tree.insert_right('')
            p_stack.push(current_tree)
            current_tree = current_tree.get_right_child()
        elif i == ')':
            current_tree = p_stack.pop()
        else:
            raise ValueError
    return e_tree

if __name__ == '__main__':
    pt = build_parse_tree("( ( 10 + 5 ) * ( 3 - 2 ) )")
    pt.postorder()

我运行代码，它 return 我用这个

name 'postorder' is not defined
  File "G:\VSCode\PythonVS\BinaryTree6Feb2022.py", line 63, in postorder
    postorder(tree.get_left_child())
  File "G:\VSCode\PythonVS\BinaryTree6Feb2022.py", line 102, in <module>
    pt.postorder()

我试图使它成为一个递归函数，但我不知道我做错了什么或者我可能遗漏了什么。我仍在检查代码，但我就是找不到遗漏的东西

Answer 1

您的遍历方法 preorder、postorder 和 inorder 具有独立函数所期望的声明，但它们缩进为成为 class 的一部分，因此它们看起来像 methods.

最简单的解决方法是将它们移出 class 块，并用 postorder(pt) 替换主程序中的调用，这样就可以了。

如果您希望在 class 上将它们作为方法，以便您可以像 pt.postorder() 那样进行调用，则将参数重命名为 tree 到 self（这是通常的做法），在 method-notation 中进行递归调用，并在递归调用之前移动 if 条件：

    def postorder(self):
        print(self.get_root_val())
        if self.get_left_child():
            self.get_left_child().postorder()
        if self.get_right_child():
            self.get_right_child().postorder()

为了完整起见，我还提供了一个在开始时保留 if 条件的替代方案，但是您必须在递归调用上使用另一种语法，因为您不能在 [=22= 上调用方法]:

    def postorder(self):
        if self:
            print(self.get_root_val())
            BinaryTree.postorder(self.get_left_child())
            BinaryTree.postorder(self.get_right_child())

但这在 Python 中并不常见。

这个递归二叉树函数类型有一些错误

there is some error in this recursive binarytree function type

python

recursion

stack

binary-tree