关于BST后续遍历(非递归)
void post_order_stack(node*head)
{
if (head == nullptr)return;
node*cur = head;
node*q = nullptr;
stack<node*>st;
//st.push(cur);
while (!st.empty()||cur!=nullptr)
{
if (cur != nullptr)
{
st.push(cur);
cur = cur->left;
}
while (!st.empty())
{
cur = st.top();
st.pop();
if (cur->right == nullptr)
{
cout << cur->data << " ";
}
else
{
st.push(cur);
cur = cur->right;
break;
}
}
}
}
push root into stack;
while stack is not empty
{
p = peek stack
if p is leaf
print p;
pop stack;
else if the tag of p is fresh
if p has right child
push p->right into stack;
if p has left child
push p->left into stack;
mark the tag of p;
else
print t;
pop stack
}