‘壹’ 二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现
#include <iostream>
using namespace std;//二叉树链式存储的头文件
typedef char datatype;//结点属性值类型
typedef struct node // 二叉树结点类型
{
datatype data;
struct node* lchild,*rchild;
}bintnode;
typedef bintnode *bintree;
bintree root;//指向二叉树结点指针
//下面是些栈的操作 为非递归实现做准备
typedef struct stack//栈结构定义
{
bintree data[100];//data元素类型为指针
int tag[100];//为栈中元素做的标记，，用于后续遍历
int top;//栈顶指针
}seqstack;
void push(seqstack *s,bintree t)//进栈
{
s->data[++s->top]=t;
}
bintree pop(seqstack *s) //出栈
{
if(s->top!=-1)
{s->top--;
return(s->data[s->top+1]);
}
else
return NULL;
}
//按照前序遍历顺序建立一棵给定的二叉树
void createbintree(bintree *t)
{
char ch;
if((ch=getchar())== '-')
*t=NULL;
else
{
*t=(bintnode*)malloc(sizeof(bintnode));//产生二叉树根结点
(*t)->data=ch;
createbintree(&(*t)->lchild);//递归实现左孩子的建立
createbintree(&(*t)->rchild);//递归实现右孩子的建立
}
}
//二叉树前序遍历递归实现
void preorder(bintree t)//t是指针变量，而不是结点结构体变量
{if(t)
{
cout<<t->data<<" ";
preorder(t->lchild);
preorder(t->rchild);
}
}
//二叉树前序遍历非递归实现
void preorder1(bintree t)
{
seqstack s;
s.top=-1;//top 的初始值为-1；
while((t)||(s.top!=-1))//当前处理的子树不为空或者栈不为空，则循环
{
while(t)
{
cout<<t->data<<" ";//访问当前子树根结点
s.top++;
s.data[s.top]=t;
t=t->lchild;
}
if(s.top>-1)
{
t=pop(&s);//当前子树根结点出栈
t=t->rchild;//访问其右孩子
}
}
}
//二叉树中序遍历递归算法
void inorder(bintree t)
{
if(t)
{
inorder(t->lchild);
cout<<t->data<<" ";
inorder(t->rchild);
}
}
// 二叉树中序遍历非递归算法
void inorder1(bintree t)
{
seqstack s;
s.top=-1;
while((t!=NULL)||(s.top!=-1))
{
while(t)
{
push(&s,t);
t=t->lchild;//子树跟结点全部进栈
}
if(s.top!=-1)
{
t=pop(&s);
cout<<t->data<<" ";//输出跟结点，其实也就是左孩子或者有孩子（没有孩子的结点是他父亲的左孩子或者有孩子）
t=t->rchild;//进入右孩子访问
}
}
}
//后续递归遍历二叉树
void postorder(bintree t)
{
if(t)
{
postorder(t->lchild);
postorder(t->rchild);
cout<<t->data<<" ";
}
};
//后序遍历 非递归实现
void postorder1(bintree t)
{
seqstack s;
s.top=-1;
while((t)||(s.top!=-1))
{
while(t)
{
s.top++;
s.data[s.top]=t;//子树根结点进栈
s.tag[s.top]=0;//设此根结点标志初始化为0，表示左右孩子都么有访问，当访问完左子树，tag变为1；
t=t->lchild;//进入左子树访问。（左子树根结点全部进栈）
}
while((s.top>-1)&&(s.tag[s.top]==1))
{
t=s.data[s.top];
cout<<t->data<<" ";//没有孩子的根结点，也就是它父亲的左孩子或者右孩子
s.top--;
}
if(s.top>-1)
{
t=s.data[s.top];
s.tag[s.top]=1;//进入右孩子前，标志tag变为1；
t=t->rchild;//进入右孩子
}
else
t=NULL;
}
}
int main()
{
bintree tree;
cout<<"输入根结点：" ;
createbintree(&tree);
cout<<"\n 前序递归遍历二叉树；";
preorder(tree);
cout<<"\n 前序非递归遍历二叉树：";
preorder1(tree);
cout<<"\n-------------------------------\n";
cout<<"\n 中序遍历递归二叉树；";
inorder(tree);
cout<<"\n 中序非递归遍历二叉树：";
inorder1(tree);
cout<<"\n----------------------------\n";
cout<<"\n 后序递归遍历二叉树：";
postorder(tree);
cout<<"\n 后序非递归遍历二叉树：";
postorder1(tree);
cout<<endl;
}
‘贰’ 跪求！！10分奉上！统计二叉树结点个数的算法 非递归
一般情况下，涉及二叉树的很多操作都包含两个方面。一方面，由于二叉树本身的递归定义，因此用递归的思想设计其很多操作是顺理成章的；另一方面，为了控制过程的深度和节约栈空间，我们有时也会考虑用非递归的思想设计很多关于二叉树的操作。必须说明的是，非递归思想一般都需要额外栈或队列结构的支持。下面来看一下关于统计二叉树结点个数的非递归算法设计：
1、将根结点插入队列。
2、判断队列是否为空，非空执行第三步，否则执行第四步退出循环。
3、从队列中取出一个结点，同时将取出结点的儿子结点插入队列。此外，将计数器加1，再转到第二步。
4、结束循环。
注意：队列是先进先出的结构，与栈相反。
如果你根据以上仍然不能写出完整的程序，下面的程序可作为你的参考。
int size()//返回结点数函数
{
linkqueue<node*>list;//定义元素为node*型的队列
int sum=0;
list.push(root);
while(!list.empty())
{
node* p=list.top();//保存即将出队的元素
list.pop();//队列首元素出队
if(p->lchild)//左儿子不为空，即进队
list.push(p->lchild);
if(p->rchild)//同上
list.push(p->rchild);
sum++;//计数器增1
}
return sum;
}
要想完全把握以上程序你必须对队列的结构有很好的理解。此外，需要说明的是，计数器是以出队元素个数为指标进行计数的，而非进队元素。这样可使程序简洁和容易理解得多。
‘叁’ 二叉树先序遍历递归算法和非递归算法本质区别
1. 先序遍历
在先序遍历中，对节点的访问工作是在它的左右儿子被访问之前进行的。换言之，先序遍历访问节点的顺序是根节点-左儿子-右儿子。由于树可以通过递归来定义，所以树的常见操作用递归实现常常是方便清晰的。递归实现的代码如下：
void PreOrderTraversal(BinTree BT)
{
if( BT )
{
printf(“%d\n”, BT->Data); //对节点做些访问比如打印
PreOrderTraversal(BT->Left); //访问左儿子
PreOrderTraversal(BT->Right); //访问右儿子
}
}
由递归代码可以看出，该递归为尾递归（尾递归即递归形式在函数末尾或者说在函数即将返回前）。尾递归的递归调用需要用栈存储调用的信息，当数据规模较大时容易越出栈空间。虽然现在大部分的编译器能够自动去除尾递归，但是即使如此，我们不妨自己去除。非递归先序遍历算法基本思路：使用堆栈
a. 遇到一个节点，访问它，然后把它压栈，并去遍历它的左子树；
b. 当左子树遍历结束后，从栈顶弹出该节点并将其指向右儿子，继续a步骤；
c. 当所有节点访问完即最后访问的树节点为空且栈空时，停止。
实现代码如下：
void PreOrderTraversal(BinTree BT)
{
BinTree T = BT;
Stack S = CreatStack(MAX_SIZE); //创建并初始化堆栈S
while(T || !IsEmpty(S))
{
while(T) //一直向左并将沿途节点访问（打印）后压入堆栈
{
printf("%d\n", T->Data);
Push(S, T);
T = T->Left;
}
if (!IsEmpty(S))
{
T = Pop(S); //节点弹出堆栈
T = T->Right; //转向右子树
}
}
}
由以上例子可以看出，递归与非递归的本质区别就是递归是不断循环调用同一过程，非递归是循环执行同一个动作，并且非递归有入栈与出栈的过程，因此更节省存储空间。个人浅见，欢迎指正。