不使用棧非遞歸中序遍歷二叉樹該怎么做？

我learnc

算法導(dǎo)論中有一個題目，12.1-3,要求用非遞歸算法執(zhí)行中序樹遍歷。根據(jù)提示我花了很長很長的時間才寫出用棧作為輔助手段的代碼。上面提示所說的第二種算法我卻沒想出來。誰能提示一下。。

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

網(wǎng)上找到一份資料：
http://download.csdn.net/source/460388

我learnc

謝謝，我已經(jīng)下載下來了。