Question

求一个用c语言实现二叉树的非递归中序遍历完整程序。（用栈实现）。谢谢！

本人才疏学浅所以需要一定注释。变量名别太复杂。我知道我的要求很多，真的劳烦各位了。
我主要是在入栈的地方不太明白，所以希望哪里注释多一点

Answer 1

//但是你栈从哪里来。。。。自己写一个吗
void InOrderRecur(Tree* tree)
{    
     while(!sta.empty()) sta.pop();    
     while(!sta.empty() || tree!=NULL)
      {        
      if(tree==NULL)  
      {
            Tree* cur = sta.top();
            sta.pop();
            cout<<cur->data<<" ";
            tree=cur->rson;
        } else {
            sta.push(tree);
            tree=tree->lson;
        }
    }
}

• 1.申请一个栈，头结点为开始节点(当前节点)

• 2.如果当前节点不为空，那么将左节点压栈，即做tree=tree->lson操作，如果当前节点为空的时候打印栈顶元素，并且出栈，将 当前节点变为栈顶元素的右节点也就是做tree = cur->rson(中序遍历中，栈主要保存的是父节点元素)

• 3.不断重复步骤2直到栈空，结束程序！

追问

嗯。就是压榨传参不太明白，刚刚弄明白了！感谢。是的，最近在学数据结构所以想之间实现stl里面的东西。