二叉树的深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归的通用做法是采用队列。
深度优先遍历二叉树。
1. 中序遍历（LDR）的递归算法：
若二叉树为空，则算法结束；否则：
中序遍历根结点的左子树；
访问根结点；
中序遍历根结点的右子树。
2. 前序遍历（DLR）的递归算法：
若二叉树为空，则算法结束，否则：
访问根结点；
前序遍历根结点的左子树；
前序遍历根结点的右子树。
3. 后序遍历（LRD）的递归算法：
若二叉树为空，则算法结束，否则：
后序遍历根结点的左子树；
后序遍历根结点的右子树；
访问根结点。
广度优先遍历二叉树。
广度优先周游二叉树(层序遍历)是用队列来实现的，从二叉树的第一层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问。
按照从根结点至叶结点、从左子树至右子树的次序访问二叉树的结点。算法：
1初始化一个队列，并把根结点入列队；
2当队列为非空时，循环执行步骤3到步骤5，否则执行6；
3出队列取得一个结点，访问该结点；
4若该结点的左子树为非空，则将该结点的左子树入队列；
5若该结点的右子树为非空，则将该结点的右子树入队列；
6结束。
非递归深度优先遍历二叉树。
栈是实现递归的最常用的结构，利用一个栈来记下尚待遍历的结点或子树，以备以后访问，可以将递归的深度优先遍历改为非递归的算法。
1. 非递归前序遍历：遇到一个结点，就访问该结点，并把此结点推入栈中，然后下降去遍历它的左子树。遍历完它的左子树后，从栈顶托出这个结点，并按照它的右链接指示的地址再去遍历该结点的右子树结构。
2. 非递归中序遍历：遇到一个结点，就把它推入栈中，并去遍历它的左子树。遍历完左子树后，从栈顶托出这个结点并访问之，然后按照它的右链接指示的地址再去遍历该结点的右子树。
3. 非递归后序遍历：遇到一个结点，把它推入栈中，遍历它的左子树。遍历结束后，还不能马上访问处于栈顶的该结点，而是要再按照它的右链接结构指示的地址去遍历该结点的右子树。遍历遍右子树后才能从栈顶托出该结点并访问之。另外，需要给栈中的每个元素加上一个特征位，以便当从栈顶托出一个结点时区别是从栈顶元素左边回来的(则要继续遍历右子树)，还是从右边回来的(该结点的左、右子树均已周游)。特征为Left表示已进入该结点的左子树，将从左边回来；特征为Right表示已进入该结点的右子树，将从右边回来。
4. 简洁的非递归前序遍历：遇到一个结点，就访问该结点，并把此结点的非空右结点推入栈中，然后下降去遍历它的左子树。遍历完左子树后，从栈顶托出一个结点，并按照它的右链接指示的地址再去遍历该结点的右子树结构。
深度优先搜索算法（Depth First Search），是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。
当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。
如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
如右图所示的二叉树：
A 是第一个访问的，然后顺序是 B、D，然后是 E。接着再是 C、F、G。
那么，怎么样才能来保证这个访问的顺序呢？
分析一下，在遍历了根结点后，就开始遍历左子树，最后才是右子树。
因此可以借助堆栈的数据结构，由于堆栈是后进先出的顺序，由此可以先将右子树压栈，然后再对左子树压栈，
这样一来，左子树结点就存在了栈顶上，因此某结点的左子树能在它的右子树遍历之前被遍历。
深度优先遍历代码片段
//深度优先遍历
void depthFirstSearch(Tree root){
stack<Node *> nodeStack; //使用C++的STL标准模板库
nodeStack.push(root);
Node *node;
while(!nodeStack.empty()){
node = nodeStack.top();
printf(format, node->data); //遍历根结点
nodeStack.pop();
if(node->rchild){
nodeStack.push(node->rchild); //先将右子树压栈
}
if(node->lchild){
nodeStack.push(node->lchild); //再将左子树压栈
}
}
}
广度优先搜索算法（Breadth First Search），又叫宽度优先搜索，或横向优先搜索。
是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。
如右图所示的二叉树，A 是第一个访问的，然后顺序是 B、C，然后再是 D、E、F、G。
那么，怎样才能来保证这个访问的顺序呢？
借助队列数据结构，由于队列是先进先出的顺序，因此可以先将左子树入队，然后再将右子树入队。
这样一来，左子树结点就存在队头，可以先被访问到。
广度优先遍历代码片段
//广度优先遍历
void breadthFirstSearch(Tree root){
queue<Node *> nodeQueue; //使用C++的STL标准模板库
nodeQueue.push(root);
Node *node;
while(!nodeQueue.empty()){
node = nodeQueue.front();
nodeQueue.pop();
printf(format, node->data);
if(node->lchild){
nodeQueue.push(node->lchild); //先将左子树入队
}
if(node->rchild){
nodeQueue.push(node->rchild); //再将右子树入队
}
}
}
完整代码:
/** * <!-- * File : binarytree.h * Author : fancy * Email : fancydeepin@yeah.net * Date : 2013-02-03 * --!> */ #include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <Stack> #include <Queue> using namespace std; #define Element char #define format "%c" typedef struct Node { Element data; struct Node *lchild; struct Node *rchild; } *Tree; int index = 0; //全局索引变量 //二叉树构造器,按先序遍历顺序构造二叉树 //无左子树或右子树用'#'表示 void treeNodeConstructor(Tree &root, Element data[]){ Element e = data[index++]; if(e == '#'){ root = NULL; }else{ root = (Node *)malloc(sizeof(Node)); root->data = e; treeNodeConstructor(root->lchild, data); //递归构建左子树 treeNodeConstructor(root->rchild, data); //递归构建右子树 } } //深度优先遍历 void depthFirstSearch(Tree root){ stack<Node *> nodeStack; //使用C++的STL标准模板库 nodeStack.push(root); Node *node; while(!nodeStack.empty()){ node = nodeStack.top(); printf(format, node->data); //遍历根结点 nodeStack.pop(); if(node->rchild){ nodeStack.push(node->rchild); //先将右子树压栈 } if(node->lchild){ nodeStack.push(node->lchild); //再将左子树压栈 } } } //广度优先遍历 void breadthFirstSearch(Tree root){ queue<Node *> nodeQueue; //使用C++的STL标准模板库 nodeQueue.push(root); Node *node; while(!nodeQueue.empty()){ node = nodeQueue.front(); nodeQueue.pop(); printf(format, node->data); if(node->lchild){ nodeQueue.push(node->lchild); //先将左子树入队 } if(node->rchild){ nodeQueue.push(node->rchild); //再将右子树入队 } } }
/** * <!-- * File : BinaryTreeSearch.h * Author : fancy * Email : fancydeepin@yeah.net * Date : 2013-02-03 * --!> */ #include "binarytree.h" int main() { //上图所示的二叉树先序遍历序列,其中用'#'表示结点无左子树或无右子树 Element data[15] = {'A', 'B', 'D', '#', '#', 'E', '#', '#', 'C', 'F','#', '#', 'G', '#', '#'}; Tree tree; treeNodeConstructor(tree, data); printf("深度优先遍历二叉树结果: "); depthFirstSearch(tree); printf("\n\n广度优先遍历二叉树结果: "); breadthFirstSearch(tree); return 0; }
来源：http://www.blogjava.net/fancydeepin/archive/2013/02/03/CPP_BinaryTreeSearch.html