内容参考：http://blog.csdn.net/zbwzll2/article/details/8901994 和 http://blog.csdn.net/aoxiangzhiguanjun/article/details/8904794
递归：
//前序遍历的算法程序
void PreOrder(BiTNode *root)
{
if(root==NULL)
return ;
printf("%c ", root->data); //输出数据
PreOrder(root->lchild); //递归调用，前序遍历左子树
PreOrder(root->rchild); //递归调用，前序遍历右子树
}
//中序遍历的算法程序
void InOrder(BiTNode *root)
{
if(root==NULL)
return ;
InOrder(root->lchild); //递归调用，中序遍历左子树
printf("%c ", root->data); //输出数据
InOrder(root->rchild); //递归调用，中序遍历右子树
}
//后序遍历的算法程序
void PostOrder(BiTNode *root)
{
if(root==NULL)
return ;
PostOrder(root->lchild); //递归调用，后序遍历左子树
PostOrder(root->rchild); //递归调用，后序遍历右子树
printf("%c ", root->data); //输出数据
}
非递归
1.前序遍历
（a）
void PreOrder_Nonrecursive(BiTree T) //先序遍历的非递归
{
if(!T)
return ;
stack<BiTree> s;
while(T) // 左子树上的节点全部压入到栈中
{
s.push(T);
cout<<T->data<<" ";
T = T->lchild;
}
while(!s.empty())
{
BiTree temp = s.top()->rchild; // 栈顶元素的右子树
s.pop(); // 弹出栈顶元素
while(temp) // 栈顶元素存在右子树，则对右子树同样遍历到最下方
{
cout<<temp->data<<" ";
s.push(temp);
temp = temp->lchild;
}
}
}
（b）将a稍做修改，使其判断分的更清楚
void preOrder2(BinTree *root) //非递归前序遍历
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{//这里是判断p不为空
while(p!=NULL)
{
cout<<p->data<<" ";
s.push(p);
p=p->lchild;
}
//p为空，但栈内还有节点（左右孩子遍历之后，返回双亲节点）
if(!s.empty())
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}
（c）思路稍作变化：先压双亲节点入栈，判断栈不为空时，栈顶节点出栈，并打印。然后分别压右孩子、做孩子入栈。循环。
void PreOrder_Nonrecursive2(BiTree T) //先序遍历的非递归
{
if(!T)
return ;
stack<BiTree> s;
s.push(T);
while(!s.empty())
{
BiTree temp = s.top();
cout<<temp->data<<" ";
s.pop();
if(temp->rchild)
s.push(temp->rchild);
if(temp->lchild)
s.push(temp->lchild);
}
}
2.中序遍历
（a）
void InOrderTraverse(BiTree T) // 中序遍历的非递归
{
if(!T)
return ;
stack<BiTree> S;
BiTree curr = T->lchild; // 指向当前要检查的节点
S.push(T);
while(curr != NULL || !S.empty())
{
while(curr != NULL) // 一直向左走
{
S.push(curr);
curr = curr->lchild;
}
curr = S.top();
S.pop();
cout<<curr->data<<" ";
curr = curr->rchild;
}
}
（b）将判断分的清晰点
void inOrder2(BinTree *root) //非递归中序遍历
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
//p不为空，p指向的节点存在
while(p!=NULL)
{
s.push(p);
p=p->lchild;
}
//栈不为空，先出栈顶节点，并打印。
if(!s.empty())
{
p=s.top();
cout<<p->data<<" ";
s.pop();
p=p->rchild;
}
}
}
3.后序遍历
（a）
void PostOrder_Nonrecursive(BiTree T) // 后序遍历的非递归
{
stack<BiTree> S;
BiTree curr = T ; // 指向当前要检查的节点
BiTree previsited = NULL; // 指向前一个被访问的节点
while(curr != NULL || !S.empty()) // 栈空时结束
{
while(curr != NULL) // 一直向左走直到为空
{
S.push(curr);
curr = curr->lchild;
}
curr = S.top();
// 当前节点的右孩子如果为空或者已经被访问，则访问当前节点
if(curr->rchild == NULL || curr->rchild == previsited)
{
cout<<curr->data<<" ";
previsited = curr;
S.pop();
curr = NULL;
}
else
curr = curr->rchild; // 否则访问右孩子
}
}
（b）使用两个栈（目前找到最易懂的方法）
void PostOrder_Nonrecursive(BiTree T) // 后序遍历的非递归 双栈法
{
stack<BiTree> s1 , s2;
BiTree curr ; // 指向当前要检查的节点
s1.push(T);
while(!s1.empty()) // 栈空时结束
{
curr = s1.top();
s1.pop();
s2.push(curr);
if(curr->lchild)
s1.push(curr->lchild);
if(curr->rchild)
s1.push(curr->rchild);
}
while(!s2.empty())
{
printf("%c ", s2.top()->data);
s2.pop();
}
}
增加几个操作：
int visit(BiTree T)
{
if(T)
{
printf("%c ",T->data);
return 1;
}
else
return 0;
}
void LeverTraverse(BiTree T) //方法一、非递归层次遍历二叉树
{
queue <BiTree> Q;
BiTree p;
p = T;
if(visit(p)==1)
Q.push(p);
while(!Q.empty())
{
p = Q.front();
Q.pop();
if(visit(p->lchild) == 1)
Q.push(p->lchild);
if(visit(p->rchild) == 1)
Q.push(p->rchild);
}
}
void LevelOrder(BiTree BT) //方法二、非递归层次遍历二叉树
{
BiTNode *queue[10];//定义队列有十个空间
if (BT==NULL)
return;
int front,rear;
front=rear=0;
queue[rear++]=BT;
while(front!=rear)//如果队尾指针不等于对头指针时
{
cout<<queue[front]->data<<" "; //输出遍历结果
if(queue[front]->lchild!=NULL) //将队首结点的左孩子指针入队列
{
queue[rear]=queue[front]->lchild;
rear++; //队尾指针后移一位
}
if(queue[front]->rchild!=NULL)
{
queue[rear]=queue[front]->rchild; //将队首结点的右孩子指针入队列
rear++; //队尾指针后移一位
}
front++; //对头指针后移一位
}
}
int depth(BiTNode *T) //树的深度
{
if(!T)
return 0;
int d1,d2;
d1=depth(T->lchild);
d2=depth(T->rchild);
return (d1>d2?d1:d2)+1;
//return (depth(T->lchild)>depth(T->rchild)?depth(T->lchild):depth(T->rchild))+1;
}
int CountNode(BiTNode *T)
{
if(T == NULL)
return 0;
return 1+CountNode(T->lchild)+CountNode(T->rchild);
}
//层次遍历（相当于树的广度优先搜素）
void printNodeByLevel(Node *root)
{
if(root == NULL)
return;
queue<Node *> s; //使用队列queue存储
s.push(root);
do
{
Node *p = s.front();
s.pop();
cout << p->data << " ";
if(p->lchild)
s.push(p->lchild);
if(p->rchild)
s.push(p->rchild);
}while(!s.empty());
}