BerthaDusStuf Ответов: 1

Разве этот код для вставки в дерево не работает для пустых деревьев?

Я читаю jumping into c++ и в нем есть этот код, который сделан для вставки в дерево:

node* insert (node *p_tree, int key)
{
// base case--we have reached an empty tree and need to insert our new
// node here
if ( p_tree == NULL )
{
node* p_new_tree = new node;
p_new_tree->p_left = NULL;
p_new_tree->p_right = NULL;
p_new_tree->key_value = key;
return p_new_tree;
}
// decide whether to insert into the left subtree of the right subtree
// depending on the value of the node
if( key < p_tree->key_value )
{
// build a new tree based on p_tree->left by adding the key. Then
// replace the existing p_tree->left pointer with a pointer
// to the new tree. We need to set the p_tree->p_left pointer
// in case p_tree->left is NULL. (If it is not NULL,
// p_tree->p_left won't actually change but it doesn’t hurt to
// set it.)
p_tree->p_left = insert( p_tree->p_left, key );
}
else
{
// Insertion into the right is exactly symmetric to insertion
// into the left
p_tree->p_right = insert( p_tree->p_right, key );
}
return p_tree;


Мой вопрос таков: если у вас есть пустое дерево, не будет ли это работать для пустого дерева? Итак, если у вас есть только один элемент, указывающий на null, и вы пытаетесь вставить его, вы просто создадите переменную с именем p_new_tree, верно?

Что я уже пробовал:

ничего...............................................

1 Ответов

Рейтинг:
12

Patrice T

Цитата:
Разве этот код для вставки в дерево не работает для пустых деревьев?

Во-первых: прочитайте код и особенно комментарии.
// base case--we have reached an empty tree and need to insert our new
// node here

во-вторых, есть простой способ узнать ответ, сделать тестовую программу, которая вызовет процедуру с нулевым деревом и посмотрит, работает ли она.
третье: чтобы помочь вам понять, что делает этот код и как он работает, используйте отладчик и наблюдайте за ним.

Ваш код ведет себя не так, как вы ожидаете, и вы не понимаете, почему !

Существует почти универсальное решение: запускайте свой код на отладчике шаг за шагом, проверяйте переменные.
Отладчик здесь, чтобы показать вам, что делает ваш код, и ваша задача-сравнить с тем, что он должен делать.
В отладчике нет никакой магии, он не знает, что вы должны делать, он не находит ошибок, он просто помогает вам, показывая, что происходит. Когда код не делает того, что ожидается, вы близки к ошибке.
Чтобы увидеть, что делает ваш код: просто установите точку останова и посмотрите, как работает ваш код, отладчик позволит вам выполнять строки 1 на 1 и проверять переменные по мере их выполнения.
Отладчик - Википедия, свободная энциклопедия[^]
1.11 — отладка программы (пошаговое выполнение и останова) | выучить C++[^]
Отладчик здесь только для того, чтобы показать вам, что делает ваш код, и ваша задача-сравнить его с тем, что он должен делать.
-----
Научитесь правильно делать отступы в вашем коде, это покажет его структуру, и это поможет чтению и пониманию. Это также помогает выявлять структурные ошибки.
node* insert (node *p_tree, int key)
{
    // base case--we have reached an empty tree and need to insert our new
    // node here
    if ( p_tree == NULL )
    {
        node* p_new_tree = new node;
        p_new_tree->p_left = NULL;
        p_new_tree->p_right = NULL;
        p_new_tree->key_value = key;
        return p_new_tree;
    }
    // decide whether to insert into the left subtree of the right subtree
    // depending on the value of the node
    if( key < p_tree->key_value )
    {
        // build a new tree based on p_tree->left by adding the key. Then
        // replace the existing p_tree->left pointer with a pointer
        // to the new tree. We need to set the p_tree->p_left pointer
        // in case p_tree->left is NULL. (If it is not NULL,
        // p_tree->p_left won't actually change but it doesn’t hurt to
        // set it.)
        p_tree->p_left = insert( p_tree->p_left, key );
    }
    else
    {
        // Insertion into the right is exactly symmetric to insertion
        // into the left
        p_tree->p_right = insert( p_tree->p_right, key );
    }
    return p_tree;

Профессиональные редакторы программистов имеют эту функцию и другие, такие как сопоставление скобок и подсветка синтаксиса.
Блокнот++ Главная Страница[^]
личные[^]

BerthaDusStuf

Хорошо спасибо я действительно не знаю как использовать отладчик и планирую учиться в ближайшее время но я понимаю код и он работает как ожидалось но я просто думаю что он работает только в некоторых случаях

Patrice T

Постройте код тестовых случаев и посмотрите, будет ли результат в порядке или нет.

BerthaDusStuf

ок ты