python - 有序遍历AVL树 : Name not defined

Question

我只是想知道有人能帮助我吗？我正在尝试对 AVL 树进行中序遍历。但我不断收到一个错误，表明我的函数名称“r_in_order”未定义。这里发生了什么，我错过了什么？这是代码:

class Node:
    """ A node in a BST. It may have left and right subtrees """
    def __init__(self, item, left = None, right = None):
        self.item = item
        self.left = left
        self.right = right

class BST:
    """ An implementation of a Binary Search Tree """
    def __init__(self):
        self.root = None

    def recurse_add(self, ptr, item):
        if ptr == None:
            return Node(item)
        elif item < ptr.item:
            ptr.left = self.recurse_add(ptr.left, item)
        elif item > ptr.item:
            ptr.right = self.recurse_add(ptr.right, item)
        return ptr

    def add(self, item):
        """ Add this item to its correct position on the tree """
        self.root = self.recurse_add(self.root, item)

    def r_count(self, ptr):
        if ptr == None:
            return 0
        else:
            return 1 + self.r_count(ptr.left) + self.r_count(ptr.right)

    def count(self): 
        return self.r_count(self.root)

    def r_height(self, ptr):
        if ptr == None:
            return 0
        else:
            return 1 + max(self.r_height(ptr.left), self.r_height(ptr.right))

    def height(self): 
        return self.r_height(self.root)

    def r_in_order(self, ptr):
        if ptr != None:
            r_in_order(ptr.left)
            print(ptr.item + " ", end="")
            r_in_order(ptr.right)


    def in_order(self): 
        return self.r_in_order(self.root)

然后我用这个测试代码:

import sys
from BST import BST

def main():
    # Read each test case
    line = sys.stdin.readline()
    items = line.strip().split()
    nums = [int(item) for item in items]

    tree = BST()


    for num in nums:
        tree.add(num)

    print("Print the elements of the tree in order:")
    tree.in_order()

if __name__ == "__main__":
    main()

Answer 1

r_in_order是BST的一种方法。它只能在 BST 实例(或以实例作为第一个参数的类)上调用，但在 r_in_order 本身的定义中，您尝试使用它没有一个。因此从技术上讲，它不存在于您尝试使用它的命名空间中。

您的函数定义应如下所示:

def r_in_order(self, ptr):
    if ptr != None:
        self.r_in_order(ptr.left)
        print(ptr.item + " ", end="")
        self.r_in_order(ptr.right)