二分探索木へのノード挿入
動画では、二分探索木（BST）とは何か、その主要な操作の実装方法を学びました。
この演習では、BST にノードを挿入する関数を実装します。
コードをテストするには、次の木を使用できます。
ノードには本のタイトルが入り、アルファベット順に基づく 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"))