c二叉查找树后期顺序遍历迭代使用堆栈

Question

我花了几个小时试图弄清楚为什么它不会在最后打印根节点。

它无法current=pop(

我不知道出了什么问题。

算法：

1.1 创建一个空堆栈 2.1 在根不为空时执行以下操作 a） 将根的右子级推送到堆栈。b）将根设置为根的左子级。2.2 从堆栈中弹出一个项目并将其设置为root。a） 如果弹出的项目有一个正确的子项，并且正确的子项位于堆栈的顶部，则从堆栈中删除正确的子项，将根推回并将根设置为根的右子项。b） 否则打印根的数据并将根设置为 NULL。2.3 在堆栈不为空时重复步骤 2.1 和 2.2。

我将其可视化，并将其绘制在白板上，逻辑对我来说很好。然而，当实现它时，它在最后一次迭代时崩溃。

void postOrderIterativeS1(BSTNode *root)
{
    Stack S;
    S.top = NULL;
    BSTNode *current = root;

    int shouldContinue = 1;
    while(shouldContinue)
    {

        if(current != NULL)
        {

            if(current->right != NULL){


            push(&S, current->right);
            }

            push(&S, current);



            current = current->left;
        }
        else
        {
            current = pop(&S);
            if(peek(&S) == NULL){
                shouldContinue = 0;
            }
            if(current->right != NULL && peek(&S)->item == current->right->item)
            {
                pop(&S);
                push(&S,current);
                current = current->right;
            }

            else


            {

                int items= current->item;
                printf("%d ", current->item);
                current = NULL;
            }

        }

    }
}

如果你想要完整的代码，https://pastebin.com/z4rPebrJ

执行：




Answer 1

这里至少有一个问题：

  current = pop(&S);
  if (peek(&S) == NULL) {
    shouldContinue = 0; 
    // peek(&S) is NULL here 
    // but in the if below you dereference peek(&S) which is NULL
    // and therefore you get a crash
  }
  if (current->right != NULL && peek(&S)->item == current->right->item)
  {
    pop(&S);
    push(&S, current);
    current = current->right;
  }

只要改变这一点:

if (current->right != NULL && peek(&S)->item == current->right->item)

为此：

if (shouldContinue && current->right != NULL && peek(&S)->item == current->right->item)