递归算法非常的简单。先访问跟节点，然后访问左节点，再访问右节点。如果不用递归，那该怎么做呢？仔细
一.先序遍历
看一下递归程序，就会发现，其实每次都是走树的左分支(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);
}
}
}
参考文献：http://blog.csdn.net/kofsky/article/details/2886453
