递归算法非常的简单。先访问跟节点，然后访问左节点，再访问右节点。如果不用递归，那该怎么做呢？仔细

一.先序遍历

　　看一下递归程序，就会发现，其实每次都是走树的左分支(left)，直到左子树为空，然后开始从递归的最深处返回，然后开始恢复递归现场，访问右子树。

由于一直走到最左边后，需要逐步返回到父节点访问右节点，因此必须有一个措施能够对节点序列回溯。

　　可以用栈记忆：在访问途中将依次遇到的节点保存下来。由于节点出现次序与恢复次序是反序的，因此是一个先

进后出结构，需要用栈；还可以节点增加指向父节点的指针。 

void preOrder1(TNode* root) {     Stack S;     while ((root != NULL) || !S.empty())     {         if (root != NULL)         {             Visit(root);             S.push(root);       // 先序就体现在这里了，先访问，再入栈             root = root->left;  // 依次访问左子树         }         else         {             root = S.pop();     // 回溯至父亲节点             root = root->right;         }     } }

　　

void preOrder2(TNode* root) {     if ( root != NULL)     {         Stack S;         S.push(root);         while (!S.empty())         {             TNode* node = S.pop();              Visit(node);          // 先访问根节点，然后根节点就无需入栈了             S.push(node->right);  // 先push的是右节点，再是左节点             S.push(node->left);         }     } }

　　

二.中序遍历

　　

void InOrder1(TNode* root) {     Stack S;     while ( root != NULL || !S.empty() )     {         while( root != NULL )   // 左子树入栈         {             S.push(root);             root = root->left;         }         if ( !S.empty() )         {             root = S.pop();             Visit(root->data);   // 访问根结点             root = root->right;  // 通过下一次循环实现右子树遍历         }     } }

　　

 

三.后序遍历

　　不写了……

四.层次遍历

　　

// 层序遍历伪代码：非递归版本，用队列完成 void LevelOrder(TNode *root) {     Queue Q;     Q.push(root);     while (!Q.empty())     {         node = Q.front();        // 取出队首值并访问         Visit(node);         if (NULL != node->left)  // 左孩子入队         {                       Q.push(node->left);             }         if (NULL != node->right) // 右孩子入队         {             Q.push(node->right);         }     } }

　　

参考文献：