1

下面是我用来inorder遍历a 的函数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
...
4

2 回答 2

3

您应该在打印出该元素时从堆栈中删除它。

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

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

// else  // <--- don't use else here.. Always pop
    st.pop();
于 2013-11-08T20:31:05.970 回答
0

这似乎比它需要的复杂得多，这是一个未经测试的版本，我认为会更好。

struct bst{ 
    int info;
    bst *right;
    bst *left;
};

void inorder(bst & item) {
    std::stack<bst*> st;
    bst* current = &item;
    while(current || !st.empty()) {
        if(current) {
            st.push(current);
            current = current->left;
        } else {
            current = st.top();
            st.pop();
            std::cout << current->info << std::endl;
            current = current->right;
        }
    }
}
于 2013-11-08T20:29:34.170 回答