Ракетка: Вставити нові вузли в двійкове дерево пошуку - схема, бінарне дерево, ракетка, ракетка-студенти-мови

Скажімо, ми маємо структуру двійкового дерева:

(define-struct tree-node (left right node))

У мене виникають проблеми з створенням двійкового дерева пошуку. Моя основна проблема полягає в тому, що я не знаю, як вставити вузол у дерево або перезаписати вліво або вправо в структурах make-tree-node.
Скажемо, що ми знаходимося на довжині дерева 8, і я хочу вставити новий вузол, якщо ліва або права порожня. Моя проблема тут, як я можу йти так глибоко? Чи можливо це рекурсивно, і якщо так, як я можу це зробити?

може використовувати лише міжрядковий рівень.

Відповіді:

Дизайн рецепт від Як розробляти програми відповідає на це питання. Розділ 195 спеціально стосується двійкового дерева пошуку. Проте матеріал, який вам найбільше допоможе тут, - це, мабуть, речі в розділах 8 і 9. Щоб витягнути декілька ниток для вас: спочатку потрібно визначити дані для двійкового дерева пошуку. Потім вам потрібно написати тести для різних випадків, у тому числі базову (вставити в пустий вузол). Потім слід дотримуватися шаблону, пов'язаного з вашим визначенням даних.