Inorder наследник в BST

Question

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

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);

    }

}

Answer 1

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

Answer 2

Предполагая, что "left" является высоким, а "right" - низким:

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

Если нет ветви left, нам нужно идти вверх по дереву (к корню) до следующегоузел вверх находится слева от текущего узла, то есть до тех пор, пока текущий узел (по мере продвижения вверх по дереву) не станет right ветвью его родителя.Этот родитель будет преемником.

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

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

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

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

Я также нигде не вижу оператора return.