向二叉搜索树插入节点

在视频中，您学习了什么是二叉搜索树（BST）以及如何实现其主要操作。

在本练习中，您将实现一个函数，用于向 BST 插入一个节点。

为测试您的代码，您可以使用下列这棵树：

Graphical representation of a binary search tree.

各节点包含书名，按字母顺序构建 BST。

这棵树已预加载在变量 bst 中：

bst = CreateTree()

您可以用以下代码检查节点是否正确插入：

bst.insert("Pride and Prejudice")
print(search(bst, "Pride and Prejudice"))

本练习是课程的一部分

Python 中的数据结构与算法

查看课程

练习说明

检查 BST 是否为空。
检查待插入的数据是否小于当前节点的数据。
检查待插入的数据是否大于当前节点的数据。

交互式实操练习

通过完成这段示例代码来试试这个练习。

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

  def insert(self, data):
    new_node = TreeNode(data)
    # Check if the BST is empty
    if ____ == None:
      self.root = new_node
      return
    else:
      current_node = self.root
      while True:
        # Check if the data to insert is smaller than the current node's data
        if ____ < ____:
          if current_node.left_child == None:
            current_node.left_child = new_node
            return 
          else:
            current_node = current_node.left_child
        # Check if the data to insert is greater than the current node's data
        elif ____ > ____:
          if current_node.right_child == None:
            current_node.right_child = new_node
            return
          else:
            current_node = current_node.right_child

bst = CreateTree()
bst.insert("Pride and Prejudice")
print(search(bst, "Pride and Prejudice"))

编辑并运行代码