Блог

Главная - Вопросы по программированию - Симметричного приемника в по британскому летнему времени

Симметричного приемника в по британскому летнему времени

#c #algorithm #data-structures

#c #алгоритм #структуры данных

Вопрос:

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

 node * getInorderSuccessor(node * root){
struct node * current = root;
static int flag = 0;

if (root != NULL)
{
if (flag != 2)
{ 
    current->next = getInorderSuccessor(current->left);
}
    if(current ==root)
        flag = 1;
    if (flag == 1)
    {
        flag = 2;
        current->next = root;
        }
    if (flag!=2)
    {

        current->next = getInorderSuccessor(current->right);

    }

}

Ответ №1:

Предполагая, что «левый» и «правый» будет низким:

Если есть left ветки, вышестоящий узел будет в нем. Так что преемником будет самой низкой (правый) узел в left филиал.

Если нет left филиала, то нужно идти вверх по дереву (к корню) до следующего узла вверх-слева от текущего узла, т. е. до текущего узла (как мы поднимаемся дерева) — это right ветви своего родителя. Что родитель будет преемником.

В любом случае, нужно каким-то образом зная, что каждый родительский узел имеет, по крайней мере, на путь к текущему узлу… так как вам может понадобиться, чтобы перейти к корню дерева. Это может быть parent указатель в каждом узле, или какой-то список узлов по пути до текущей.

Что касается кода, я не уверен, как вы это имели в виду для работы, но:

 current->next = getInorderSuccessor(current->left);

…выглядит странно. Если current->left это большая ветка, то current->left с наследника будет по крайней мере два узла С current , поэтому он не мог быть current с непосредственным наследником. Если left это низко растущую ветку, она может не содержать current с преемника, так что это все равно не имеет смысла.

Я также не вижу return заявление в любом месте.

Ответ №2:

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

Метки: