c++ - 迭代前序遍历(调试)

Question

这是一个迭代版本的前序遍历。其思想是
将根压入堆栈。
如果左 child 不为空。将左 child 压入堆栈，root=root->left Else root=Top of stack;Pop;push its right child and root=root->right

它在某些树上工作，但对于某些输入树，它会打印重复值。堆栈的行为令人惊讶。它如何从 (4 5 6 8) 变为 (4 6 8)？

    void preorder(node* root)
    {stack<node*> st;
     st.push(root);
     cout<<root->val<<" \n ";
     while(!st.empty())
      {if(root->left!=NULL)
         {st.push(root->left);
          cout<<st.top()->val<<" ";
         // printstack(st);
          root=root->left;
          }
       else{root=st.top();
            st.pop();
           if(root->right!=NULL)
            {st.push(root->right);
             cout<<st.top()->val<<" ";   
             //printstack(st);
              root=root->right;
             }
           }
        }
      }

用于调试的辅助函数printstack

     void printstack(stack<node*> s)
      {stack<node*> t;
      t=s;
      while(!t.empty())
       {cout<<t.top()->val<<" ";
       t.pop();
       }
      } 

对于这个输入树，打印的堆栈在下面。 预序输出为
8 3 1 6 5 4 4 7 9

                  ______8_
                 /                \
             __3_          9
            /        \
            1      ___6
                     /    \
                     5      7
                    /
                   4

3 8

1 3 8

6 8

5 6 8

4 5 6 8

4 6 8//How is the Top of stack 4??应该是5,Stack being ( 5 6 8)

7 8

  9

Answer 1

问题出现在有左 child 但没有右 child 的节点上。当节点有右 child 时，最后一个 if block 会在下一次迭代之前更改根节点，但如果没有它，根节点不会切换。然后，下一次，我们看到一个根(已经从堆栈中弹出)有一个左 child ，所以它的左 child 被压入堆栈并再次访问。

希望对您有所帮助。