二分探索木へのノードの挿入
前のビデオでは、二分探索木の概念と主要な操作の実装方法を学びました。
この演習では、二分探索木にノードを挿入する関数を書いてみましょう。
コードのテストには、次のツリーを使用します。
アルファベット順に基づいて構築されたこの二分探索木では、各ノードに本のタイトルが格納されています。
このツリーはbst変数にあらかじめ読み込まれています。
bst = CreateTree()
次のコードを使って、ノードが正しく挿入されているか確認できます。
bst.insert("Pride and Prejudice")
print(search(bst, "Pride and Prejudice"))
この演習はコースの一部です
Pythonで学ぶデータ構造とアルゴリズム
演習の手順
- 二分探索木が空かどうかを確認してください。
- 挿入するデータが現在のノードのデータより小さいかどうかを確認してください。
- 挿入するデータが現在のノードのデータより大きいかどうかを確認してください。
実践的なインタラクティブ演習
このサンプルコードを完成させて、この演習に挑戦してみましょう。
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"))