Обход по бинарному дереву по порядку дает значение мусора и ошибку сегментации после обхода

Question

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

struct Node
{
    int data;
    Node *left;
    Node *right;
    Node(int x) 
    {
        data = x;
        left = NULL;
        right = NULL;
    }
};

Node *STACK[10] = { NULL };
int TOP = -1;

void push(Node *ptr)
{
    if(TOP < 10) {
        STACK[++TOP] = ptr;
    }
}

void stackTraversal(Node *root)
{
    Node *ptr = root; bool flag = false;
    top:
    while(ptr != NULL)
    {
        push(ptr);
        ptr = ptr->left;
    }

    ptr = STACK[TOP];
    TOP--;
    while(ptr != NULL)
    {
        cout << ptr->data << " ";
        if(ptr->right != NULL)
        {
            ptr = ptr->right;
            flag = true;
            break;
        }
        ptr = STACK[TOP];
        TOP--;
    }
    if(flag)
        goto top;
    cout << "\nTHE END\n"; 
}

int main(int argc, char const *argv[])
{
    Node *R = new Node(2); 
    Node *a = new Node(0);
    Node *b = new Node(1);
    Node *c = new Node(4);
    Node *d = new Node(5);
    Node *e = new Node(3);

    R->right = c;
    R->left = a;

    a->right = b;

    c->right = d;
    c->left = e;

    stackTraversal(R);
    cout << endl;
    return 0;
}

это дает следующий вывод.

Вывод: - 0 1 2 3 45 -786491 ошибка сегментации (ядро сброшено)

Answer 1

Как вы можете видеть из своих выходных данных, вы прошли все элементы, и последний посещенный элемент - d.

Теперь вы находитесь в этом блоке, где ptr указывает на d:

        if(ptr->right != NULL)
        {
            ptr = ptr->right;
            flag = true;
            break;
        }
        ptr = STACK[TOP];

Хорошо, d не имеет детей, вы не входите в блок if, и следующий узел, который вы планируете посетить, это ... STACK[-1].

Пересмотреть свой алгоритм. Я рекомендую избегать использования goto, если это заведомо плохая практика.

Answer 2

Ваш алгоритм появляется из стека, предполагая, что всегда будет что-то. Но как тогда ptr становится NULL для завершения второго цикла?

Как следствие, ваш счетчик стека переходит в отрицательный вызывающий UB, который (к счастью) выражается в виде ошибки времени выполнения.

Улучшение 1: определить конец

Вы попытались написать push(). Приложите дополнительные усилия для написания pop(). Убедитесь, что ваш алгоритм проверяет наличие пустого стека или что pop() возвращает nullptr, если стек пуст:

Node* pop()
{
    if (TOP>=0) { 
        return STACK[TOP--];
    }
    else {
        return nullptr;
    }
} 

Конечно, замените следующие последовательности на ptr = pop();:

ptr = STACK[TOP];
TOP--;

Все pop() сопровождаются проверкой указателя на нулевое значение, за исключением использования ptr после goto. Поэтому вам нужно добавить дополнительное условие, чтобы избежать этой ситуации:

if(flag && ptr)
    goto top;

Когда вы затем запустите программу, она отобразит элементы, но вы увидите, что недостаточное выполнение завершает процесс.

Улучшение 2: избавиться от goto

Мы находимся в 21-м веке: goto больше не является смертельным исходом, и лучше избегать в C ++, если это возможно .

Внешняя петля может элегантно заменить goto. Затем вы также можете избавиться от флага:

void stackTraversal(Node *root)
{
    ...
    while(ptr)   // outer loop: no more goto 
    {
        while(ptr) {        // push the full left
            push(ptr);
            ptr = ptr->left;
        }
        ptr = pop();       // pop top node 
        while(ptr)        
        {
            cout << ptr->data << " ";
            cout.flush();   // in case of weird things happening afterwards
            if(ptr->right) {    // explore its right branch
                ptr = ptr->right;
                break;          // this goes back to outer loop
            }
            else ptr = pop();
        }
    }
    cout << "\nTHE END\n"; 
}

Демо онлайн