使用BST类和节点类在Python中实现二叉搜索树

Question

谁能帮我弄清楚我做错了什么，所以我得到了这个输出错误-

当我测试程序是否插入树的第一个根时，插入函数工作正常，并且成功创建了第一个根，但一旦我将根分配给当前和while循环以搜索父项，然后在其上插入新值，我就会得到NameError:/

下面是我的代码使用python的实现:

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

class BST:
  def __init__(self):
      self.root = None
  
  def insert(self, value):
    if root is None:
      root == Node(value)
     
    current = root
    while(True):
      if(value < current.value):
        if current.left:
          current.left = Node(value)
          break
        current = current.left
      else:
        if current.right:
          current.right = Node(value)
          break
        current = current.right


if __name__ == '__main__':
  tree = BST()
  tree.insert(10)
  tree.insert(5)
  tree.insert(6)
  print("Tree Inserted Successfully")

谢谢你

我正在尝试在我的二叉搜索树中插入一个新值，因此有2种情况：

• 如果BST为空（这很简单，传递正确）
• 另一种情况是当我们必须找到此节点的父节点并插入其值时，我使用while（true）并将一个新的变量电流分配给root以在遍历树时跟踪当前父节点

Answer 1

问题:

>

root应该是self.root。

== 不是赋值。它应该是 =

您应该在设置root后退出函数，而不是继续使用函数的其余部分：

if self.root is None:
  self.root = Node(value) # Assign!
  return  # don't continue

您在while循环中的if语句中的条件应该测试相反的条件。当您没有左孩子时，您应该在那里附加一个新节点，而不是当那里已经有一个节点时：

  if(value < current.value):
    if not current.left:  #  Opposite condition
      current.left = Node(value)
      break
    current = current.left
  else:
    if not current.right:  #  Opposite condition
      current.right = Node(value)
      break
    current = current.right

所有代码：

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

class BST:
  def __init__(self):
      self.root = None
  
  def insert(self, value):
    if self.root is None:  # root is an attribute, not a variable
      self.root = Node(value)  # Assign!
      return # Don't continue
     
    current = self.root
    while(True):
      if(value < current.value):
        if not current.left:  #  Opposite condition
          current.left = Node(value)
          break
        current = current.left
      else:
        if not current.right:  #  Opposite condition
          current.right = Node(value)
          break
        current = current.right


if __name__ == '__main__':
  tree = BST()
  tree.insert(10)
  tree.insert(5)
  tree.insert(6)
  print("Tree Inserted Successfully")
  print(tree.root.left.right.value)  # Should output: 6