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() の最初のブロックでスタックに残しています。

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

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