Python 中的二进制搜索树插入未返回到控制台

Question

在学习 hackerrank 中的 BST 时，我遇到了以下问题。

我的节点和二叉搜索树的类定义如下：

class Node:
    def __init__(self,info):
        self.info = info
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self,val):
        currentNode = self.root
        if currentNode is None:
            self.root = Node(val)
        elif currentNode.info > val:
            currentNode.left = insert(currentNode.left,val)
        elif currentNode.info < val:
            currentNode.right = insert(currentNode.right,val)
        return currentNode

但是，在对某些整数数组 arr return 的 for 循环使用 tree.insert(arr[i] 后，对 tree = BinarySearchTree() 执行遍历没有输出。这个逻辑对我来说似乎是正确的，我怀疑这是由于 Node 和 BST 之间的类型不同，但我不确定如何解决这个问题。

编辑：以下是来自 hackerrank 的完整代码。我唯一能够编辑的是插入功能。

class Node:
    def __init__(self, info):
        self.info = info  
        self.left = None  
        self.right = None 
        self.level = None 

    def __str__(self):
        return str(self.info) 

def preOrder(root):
    if root == None:
        return
    print (root.info, end=" ")
    preOrder(root.left)
    preOrder(root.right)
    
class BinarySearchTree:
    def __init__(self): 
        self.root = None

    def insert(self,val):
        currentNode = self.root
        if currentNode is None:
            self.root = Node(val)
        elif currentNode.info > val:
            currentNode.left = insert(currentNode.left,val)
        elif currentNode.info < val:
            currentNode.right = insert(currentNode.right,val)
        return currentNode

tree = BinarySearchTree()
t = int(input())

arr = list(map(int, input().split()))

for i in range(t):
    tree.insert(arr[i])

preOrder(tree.root)

给定的测试用例是

6
4 2 3 1 7 6

并且应该 return 4 2 3 1 7 6，但 return 没有输出。

修改：根据第一个答案修改！现在，我有下一周的错误：

Traceback (most recent call last):
    File “solution.py”, line 40, in <module>
        tree.insert(arr[i])
    File “solution.py”, line 30, in insert
        currentNode.left = insert(currentNode.left,val)
NameError: name ‘insert’ is not defined

Answer 1

我认为问题出在这里

def insert(self,val):
    currentNode = self.root
    if currentNode is None:
        currentNode = Node(val)
    elif currentNode.info > val:
        currentNode.left = insert(currentNode.left,val)
    elif currentNode.info < val:
        currentNode.right = insert(currentNode.right,val)
    return currentNode

如您所见，您做了 "insert" 节点但没有分配它，代码块

if currentNode is None:
    currentNode = Node(val)

应该是

if currentNode is None:
    self.root = Node(val)

你继续尝试遍历 Null 树

编辑：这可能不是问题所在，请提供完整代码 create() 函数在您的代码中缺失但被调用

Answer 2

将您的代码更改为

    def insert(self, val, currentNode):

        if self.root is None:
            self.root = Node(val)

        elif currentNode.info > val:
            if currentNode.left is None
                currentNode.left = Node(val)
            else:
                self.insert(val, currentNode.left)

        elif currentNode.info < val:

            if currentNode.right is None
                currentNode.right = Node(val)
            else:
                self.insert(val, currentNode.right)

并通过

调用它

 tree.insert(val,tree.root)

Answer 3

这里有一个更短的版本，它避免了嵌套的 "if" 语句并且没有 "Node" class:

class BinarySearchTree:
    def __init__(self):
        self.info = None
        self.left = None
        self.right = None

    def insert(self,val):
        if self.info is None:
            self.info = val
            self.left = BinarySearchTree()
            self.right = BinarySearchTree()
        elif self.info > val:
            self.left.insert(val)
        elif self.info < val:
            self.right.insert(val)

Python 中的二进制搜索树插入未返回到控制台

Binary Search Tree insertion in Python not returning to console

python

binary-tree

insert

binary-search-tree

python-3.x