预序遍历(二叉树)-迭代方法

Question

我正在实现二进制树的预序遍历(无递归(。下面的代码运行到一个无限循环中。我无法理解发生了什么

void Tree::n_preorder()
{
Node* temp;        
stack s;
cout<<"nPreorder: ";
while(1)
{
s.push(root);
while(1)
{
temp = s.pop();
cout<<temp->data;
if(temp->right)
{
s.push(temp->right);        //Push right child
}
if(s.isEmpty())
{
break;
}
if(temp->left)
{
s.push(temp->left);         //Push left child
}
}
}
}

Stack 的isEmpty((函数

int isEmpty()
{
return top==-1;
}

Answer 1

外部循环从未退出：其while条件始终为true，并且没有break。您拥有的唯一break将突破内部循环，但不会突破外部循环。

您不应该需要嵌套循环来执行此操作。当你只有一个循环时，如果不把左边的子循环放在堆栈上就中断它是没有意义的，所以去掉这个条件中断，改为把!s.isEmpty()作为循环的条件：

void Tree::n_preorder()
{
Node* node;        
stack nodeStack;
cout << "nPreorder:";
nodeStack.push(root);
while (!nodeStack.isEmpty())
{
node = nodeStack.pop();
cout << " " << node->data;
// As a stack is LIFO (last-in-first-out), we add the node's children 
// on the stack in reversed order, so they get output in the correct order.
if (node->right)
{
nodeStack.push(node->right);
}
if (node->left)
{
nodeStack.push(node->left);
}
}
}

其他备注：

• 我觉得有"这样的评论是没有用的；"推左儿童">。。。因为这只是在重复——几乎逐字逐句地——人们在相应的代码行中已经看到的内容。应该对更高层次的抽象进行评论，并对"抽象"给出一些解释；为什么&"；。我在上面的代码中添加了这样一个注释来说明这一点。

• 使用更具描述性的变量名称。CCD_ 5和CCD_。

• 您需要输出一个空格来分隔不同的数据输出。