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

Question

任何人都可以帮我弄清楚我做错了什么所以我得到这个输出错误--> NameError: name 'root' is undefined.

当我测试用于插入树的第一个根的程序时，插入功能正常工作并且第一个根已成功创建但是一旦我将 root 分配给 current 和 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")

谢谢

我试图在我的二叉搜索树中插入一个新值，所以有两种情况：

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

Answer 1

问题：

root 应该是 self.root.
== 不是赋值。应该是=

设置root后请退出函数，不要继续函数的其余部分:

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

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

  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

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

Implementation of a Binary Search Tree in Python with BST Class and Node Class

python

data-structures

binary-tree

binary-search-tree