Итеративный обход в обратном порядке прерывается в корневом узле дерева

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

Проблема, я думаю, в том, что вы неправильно продолжаете всплывать в стеке, когда дети существуют справа.

Рассмотрим простой пример, где у нас есть корневой узел 1 с левым дочерним элементом 0 и правым дочерним элементом 2, и предположим, что у 2 есть правый дочерний узел с именем 3.

В первом цикле мы помещаем 1 и 0 в стек. Тогда у 0 нет левого потомка, поэтому root становится нулевым. Стек не пуст, поэтому продолжаем. 0 находится на вершине стека и не имеет правого дочернего элемента, поэтому мы входим в первую ветвь оператора if. Затем мы выводим 0, и поскольку 0 является левым дочерним элементом 1 — 1 теперь вершина стека — корень становится 2.

В этот момент возвращаемся наверх. 2 является корнем и помещается в стек. 2 не имеет левого потомка, поэтому корень становится нулевым. Стек не пуст. 2 находится на вершине стека. У него есть правый дочерний элемент, поэтому мы вводим вторую ветвь оператора if. Это делает 3 корнем.

Возвращаемся к вершине внешнего цикла. 3 является корнем и помещается в стек. 3 не имеет левого потомка, поэтому корень становится нулевым. Стек не пуст. 3 не имеет правильного потомка, поэтому мы вводим первую ветвь оператора if. Мы выводим 3. Затем, поскольку 3 является правым дочерним элементом 2 — 2 сейчас находится на вершине стека, — мы извлекаем 2 из стека, выводим 2, и корень становится нулевым.

Возвращаемся к вершине петли. Корень уже равен нулю, поэтому в стек ничего не помещается. Стек не пуст. 1 находится на вершине стека. В этот момент правильнее всего будет извлечь 1 из стека, потому что мы уже обработали его правого потомка; однако 1 находится на вершине стека и имеет правого дочернего элемента, поэтому мы входим во вторую ветвь оператора if, и 2 становится корнем. Ситуация точно такая же, как и два абзаца назад: 1 — единственный элемент в стеке, а 2 — корень, так что мы получаем бесконечный цикл обратно туда.

Если бы мы изменили пример так, чтобы у 3 также был правый дочерний элемент с именем 4, то, если я правильно понял, мы бы никогда не распечатали 2, а вывели бы в цикле 4 и 3.

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

    if (!top(s) -> right)
    {
        root = pop(s);
        printf("%d ", root -> data);

        while (!stack_isEmpty(s) && root == top(s) -> right)
        {
            root = pop(s);
            printf("%d ", root -> data);
        }
        if (!stack_isEmpty(s) && root == top(s) -> left)
        {
            // checking root == top(s) -> left is probably redundant,
            // since the code is structured so that root is either
            // a child of top(s) or null if the stack is not empty
            root = top(s) -> right;
        }
        else
        {
            root = NULL;
            // could actually break out of outer loop here, but
            // to be more consistent with code in the question
        }
    }

Публикация этого ответа, чтобы предоставить полный код решения, предложенного @Evan VanderZee

void postorder_nonrec_2(treenode *root)
{
    stack_t *s;
    stack_init(&s, 100);


    while(1)
    {
        while(root)
        {
            push(s, root);
            root = root -> left;
        }

        if(stack_isEmpty(s))
            break;

        if (!top(s) -> right)
        {
            root = pop(s);
            printf("%d ", root -> data);

            while (!stack_isEmpty(s) && root == top(s) -> right)
            {
                root = pop(s);
                printf("%d ", root -> data);
            }

            root = NULL;
        }
        else
        {
            root = top(s) -> right;
        }
    }
}