Вставка двоичного дерева (отсортировано)

Question

Я пробовал Интернет за помощью по этой проблеме, но мне нужна помощь. Это не совсем обычная проблема вставки для двоичного дерева, поскольку мы не можем напрямую работать с самой древовидной структурой. Мой профессор написал это сам и дал нам функции, которые мы можем использовать для написания функций, относящихся к бинарным деревьям. Таким образом, я не могу использовать узлы и указатели и все. Также это в C++.

В любом случае, вот описание рекурсивной функции, которую я должен написать (вместе с моей попыткой начать работу с проблемой). Обратите внимание, что он возвращает новое дерево целиком, но фактически ничего не добавляет к существующему дереву.

tree_t insert_tree(int elt, tree_t tree) 
{ 
    /* 
    // REQUIRES; tree is a sorted binary tree 
    // EFFECTS: returns a new tree with elt inserted at a leaf such that 
    //   the resulting tree is also a sorted binary tree. 
    // 
    //   for example, inserting 1 into the tree: 
    // 
    //       4 
    //      / \ 
    //      / \ 
    //      2  5 
    //     /\ /\ 
    //       3 
    //      /\ 
    // 
    // would yield 
    //       4 
    //      / \ 
    //      / \ 
    //      2  5 
    //     /\ /\ 
    //      1 3 
    //     /\/\ 
    // 
    // Hint: an in-order traversal of a sorted binary tree is always a 
    //  sorted list, and there is only one unique location for 
    //  any element to be inserted. 
    */ 

if (elt < elt(tree_left(tree)){ 
    return insert_tree(tree_left(left)); 
} else { 
    return insert_tree(tree_right(right)); 
} 
} 

А вот функции, которые мы можем использовать:

extern bool tree_isEmpty(tree_t tree); 
    // EFFECTS: returns true if tree is empty, false otherwise 

extern tree_t tree_make(); 
    // EFFECTS: creates an empty tree. 

extern tree_t tree_make(int elt, tree_t left, tree_t right); 
    // EFFECTS: creates a new tree, with elt as it's element, left as 
    //   its left subtree, and right as its right subtree 

extern int tree_elt(tree_t tree); 
    // REQUIRES: tree is not empty 
    // EFFECTS: returns the element at the top of tree. 

extern tree_t tree_left(tree_t tree); 
    // REQUIRES: tree is not empty 
    // EFFECTS: returns the left subtree of tree 

extern tree_t tree_right(tree_t tree); 
    // REQUIRES: tree is not empty 
    // EFFECTS: returns the right subtree of tree 

extern void tree_print(tree_t tree); 
    // MODIFIES: cout 
    // EFFECTS: prints tree to cout. 

Answer 1

Вставка в нулевой элемент дерева в легко:

return tree_make(elt, tree_make(), tree_make()); 

Вставка в один-элементного дерева в также легко :

tree_t new_node = tree_make(elt, tree_make(), tree_make()); 
if(elt < tree_elt(tree)) 
    return tree_make(tree_elt(tree), new_node, tree_right(tree)); 
else 
    return tree_make(tree_elt(tree), tree_left(tree), new_node); 

В gen чтобы вставить новый элемент, вам нужно будет воссоздать всех своих родителей таким образом.

---

Часть 2: Рекурсия

У нас есть базовый случай (нулевой элемент дерева). И мы знаем, как прикрепить новое поддерево к корню нашего существующего дерева.

Итак, как получить новое поддерево? Ну, а как насчет того, что мы просто вставляем элемент в текущее поддерево?

Следующий код всегда будет придавать новый элемент на левой части дерева, но это должно быть тривиальной, чтобы исправить, как только вы его понимаете:

tree_t tree_insert(int elt, tree_t tree) 
{ 
    if(tree_empty(tree)) //base case 
     return tree_make(elt, tree_make(), tree_make()); 
    else 
     return tree_make(// make a new node 
      tree_elt(tree) // with the same value as the current one 
      tree_insert(elt, tree_left(tree)) //insert into the left subtree 
      tree_right(tree) // keep the right subtree the same 
      ); 
}