node в контексте псевдокода - это ранее выделенный узел, содержащий данные, вставляемые в дерево.Первоначальный вызывающий объект выделяет его (и это бессмысленно и никогда не делается в коде RW). В действительности, очень маловероятно, что этот шаблон будет фактически выполняться, если вы не рассматриваете библиотеку, которая потенциально перемещает узлов из одногодерево в другое, и вы хотите избежать затрат на настройку / разрушение самих узлов.
Что касается алгоритма, он довольно прост, хотя и не очень хорош:
Если оба значения current и parent равны нулю, это означает, что это должно быть первымузел в дереве отслеживается каким-то глобальным указателем root.Следовательно, root назначается непосредственно входящему узлу.
В противном случае, если current равно нулю, но parent равно , а не , если означает, что parent равнокакой-то потенциальный лист в дереве (то есть в нем есть левый, правый или оба указателя, которые имеют нулевое значение), и вы попали в нулевой указатель.Для вставки требуется сравнение с родительским значением, чтобы узнать, вешаете ли вы узел слева или справа.Обратите внимание, что это неэффективно, так как вы уже сделали это сравнение (это то, как вы попали сюда в первую очередь).
В противном случае, если current не равно нулю, мы просто проверяем,значения равны или меньше (предполагается, что больше, если ни один из них не верен), и, если это оправдано, вбивают в поддерево слева или справа.В этом случае current.left или current.right становятся рекурсивными current, а current становится parent того же рекурсивного вызова.
Вот и все.Вот как работает этот алгоритм.И, честно говоря, это маргинально.
Чтобы реализовать этот алгоритм с вашим списком аргументов (который принимает значение, а не узел для последнего аргумента), вам нужно только обеспечить, чтобы распределение узлов происходило только тогда, когда пришло время фактически зависатьit, и only then (таких случаев два.
bool recursiveInsert(Node* current, Node* parent, double value)
{
bool result = false;
if (current == NULL)
{
if (parent == NULL)
{
root = malloc(sizeof *root);
root->value = value;
root->left = root->right = NULL;
}
else
{
Node *p = malloc(sizeof *p);
p->value = value;
p->left = p->right = NULL;
if (value < parent->value)
{
parent->left = p;
}
else
{
parent->right = p;
}
result = true;
}
}
else if (value < parent->value)
result = recursiveInsert(current->left, current, value);
else if (parent->value < value)
result = recursiveInsert(current->right, current, value);
return result;
}
При вставке значения в дерево вызов будет выглядеть примерно так:
recursiveInsert(root, NULL, value);
Это не красиво, но работает. То, что оно зависит от глобального присутствия root, вероятно, является худшей частью этого алгоритма. Мультисравнение, вероятно, второе в списке гадости.
Другой подход
В идеале корень дерева передается в качестве аргумента. Далее, мы можем сделать алгоритм рекурсивным, каким он является сейчас, но больше не полагаться на некоторый глобальный root. Наконец, мы можемуменьшите количество аргументов до двух: адрес указателя (первоначально адрес корневого указателя) и вставляемое значение. спойте указатель на указатель как метод доступа к деревуd делает этот алгоритм элегантным, используя рекурсию или нет.Оба представлены ниже:
Рекурсивная вставка
bool treeInsert(Node **pp, double value)
{
bool result = false;
if (!*pp)
{
*pp = malloc(sizeof **pp);
(*pp)->value = value;
(*pp)->left = (*pp)->right = NULL;
result = true;
}
else if (value < (*pp)->value)
{
result = recursiveInsert(&(*pp)->left, value);
}
else if ((*pp)->value < value)
{
result = recursiveInsert(&(*pp)->right, value);
}
return result;
}
Итеративная вставка
bool treeInsert(Node **pp, double value)
{
bool result = false;
while (*pp)
{
if (value < (*pp)->value)
pp = &(*pp)->left;
else if ((*pp)->value < value)
pp = &(*pp)->right;
else break;
}
if (!*pp)
{
*pp = malloc(sizeof **pp);
(*pp)->value = value;
(*pp)->left = (*pp)->right = NULL;
result = true;
}
return result;
}
в любом случае вы вызываете, передавая адрес корневого указателя (таким образом,указатель на указатель), где пустая попытка обозначается корнем NULL:
treeInsert(&root, value);
Любая функция выполнит поставленную задачу.Я оставляю задачу по исправлению ошибок для вас (проверьте ваши mallocs).