按顺序遍历 AVL 树：名称未定义

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 实例上调用（或在 class 上以实例作为第一个参数），但在 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)

Answer 2

没有通用函数r_in_order:需要添加self.获取方法引用已经在里面了。打印语句中还潜伏着一个语法错误。试试这个：

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)

这会运行，并产生以下内容（第一行是输入）。

1 3 7 5 6 4 2
Print the elements of the tree in order:
1  2  3  4  5  6  7

按顺序遍历 AVL 树：名称未定义

In Order Traversal AVL Tree: Name not defined

python

recursion

avl-tree