python - 我当前的二叉搜索树实现有什么问题？最后打印树只打印根

Question

我正在尝试实现二叉搜索树的类实例，但我认为我的插入函数有问题。

节点类:

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

BST 类:

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

  def insert(self, node):
    def helper(current, node):
      if current is None:
        current = node
      else:
        if node.data < current.data:
          helper(current.left, node)
        elif node.data > current.data:
          helper(current.right, node)

    return helper(self.root, node)

  def inorder(self, current):
    if current:
      self.inorder(current.left)
      print(current.data)
      self.inorder(current.right)

我调用的函数:

tree = BST()
tree.root = Node(3)
tree.insert(Node(2))
tree.insert(Node(7))
tree.insert(Node(9))
tree.insert(Node(7))
tree.insert(Node(4))
tree.insert(Node(89))
tree.insert(Node(6))
tree.insert(Node(2))
tree.inorder(tree.root)

Answer 1

分配 current = node 不会编辑任何对象，它只是重新分配局部变量 current。您需要修改节点以添加子节点。试试这个:

def helper(current, node):
    if node.data < current.data:
            if (current.left is None):
                current.left = node
                return
            else:
                helper(current.left, node)
        elif node.data > current.data:
          if (current.right is None):
              current.right = node
              return
          else:
              helper(current.right, node)