不使用栈非递归中序遍历二叉树该怎么做？

我learnc

算法导论中有一个题目，12.1-3,要求用非递归算法执行中序树遍历。根据提示我花了很长很长的时间才写出用栈作为辅助手段的代码。上面提示所说的第二种算法我却没想出来。谁能提示一下。。

template < typename T > class Item {     public:         Item (T v) :value(v),lchild(NULL),rchild(NULL){}     public:         T value;         Item *lchild;         Item *rchild; }; template < typename T > void inorder_nonrecur ( Item<T> *root ) {     bool add_rchild = true;     std::stack<Item<T>* > parents;     parents.push ( root );     while ( !parents.empty() ) {         Item<T> *pos = parents.top();         while ( pos ) {             if ( pos->lchild != NULL && add_rchild ) {                 parents.push ( pos->lchild );             }             pos = pos->lchild;         }         if ( !parents.empty() )  {             pos = parents.top();             parents.pop();             add_rchild = false;             printf ( "%d ", pos->value );             if ( pos->rchild != NULL ) {                 parents.push ( pos->rchild );                 add_rchild = true;             }         }     }     return ; }

scutan

网上找到一份资料：
http://download.csdn.net/source/460388

我learnc

谢谢，我已经下载下来了。