c++ - 即使在执行流程到达包含 while 的函数结束后，while 循环也会无限执行而无需任何递归调用

Question

下面是我用于 inorder 遍历 binary search tree 的函数。一切正常，直到循环 while(!st.empty()) 终止，但之后执行流程再次转到 while(!st.empty()) 因此循环变成无限循环

节点结构

class bst{ 
private:
    bst *lLink;
    int info;
    bst *rLink;

friend void inorder(bst &);
 };
void inorder(bst &);

调用部分

string c;
cout<<"\na, b or c ?";
cin>>c;

 if(c == "a")
 {
  inorder(nodeVec[0]);  //nodeVec is vector containing all nodes (objects) of tree with first element as root
 }

 //......

函数

void inorder(bst &item)
{
stack<bst> st;
st.push(item);


while((st.top()).getLeftChild()!=NULL)
{
    st.push(*((st.top()).getLeftChild()));
}

while(!st.empty())
{
    if(st.top().getInfo()==item.getInfo()) //true if traversal is done with all
                                           //left subtree of root and only oneitem remained in stack i.e. only root remained
    {                                     
        cout<<st.top().getInfo()<<endl;

        if(st.top().getRightChild()!=NULL)
            inorder(*(item.getRightChild()));

        else
            st.pop();
    }

    else{
    cout<<st.top().getInfo()<<endl;
    if(st.top().getRightChild()!=NULL)
    {
        bst curr=*(st.top().getRightChild());
        st.pop();
        st.push(curr);
    }
    else{
        st.pop();
    }
    }
}
 cout<<st.empty();  //for testing, this prints 1
} //execution goes here and then again at while(!st.empty())

假设树是这样的:

      69
     /  \
    43  89
   /   /
  24  73
 /
14
 \
  21

它给出输出

14
21
24
43
69
73
89
69   //loop starts again
73
89
69
73
89
...

Answer 1

当打印出来时，您应该从堆栈中删除该元素。

您将它留在 if() 的第一个 block 中的堆栈中，该 block 检查树的左侧是否已完成。

if(st.top().getRightChild()!=NULL)
    inorder(*(item.getRightChild()));

// else  // <--- don't use else here.. Always pop
    st.pop();