1、递归就是函数调用函数本身，运行起来就是函数嵌套函数，层层嵌套，所以函数调用、参数堆栈都是不小的开销，但是程序简单。
2、非递归就是不断地对参数入栈、出栈，省去了函数层层展开、层层调用的开销。虽然参数出入栈次数多了，但是一般都开辟固定的足够大的内存来一次性开辟、重复使用。
3、非递归是从堆栈的角度来编写程序，速度快，但代码复杂。
递归是从问题本身的逻辑角度来编写，虽然速度相对慢，但代码容易理解。
如果对速度要求不高，建议用递归方式。
4、摘录例子如下：
#includestdio.h
#includestdlib.h
typedefstructBiTNode
{
chardata;
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;//二叉树的节点类型
typedefstructQNode
{
BiTNodedata;
structQNode*next;
}QNode,*QueuePtr;//队列节点类型
typedefstruct
{
QueuePtrfront;
QueuePtrrear;
}LinkQueue;//队列的头尾指针
voidInitQueue(LinkQueue*Q)//创建队列
{
Q-front=Q-rear=(QueuePtr)malloc(sizeof(QNode));
Q-rear-next=NULL;
}
voidEnQueue(LinkQueue*Q,BiTNodee)//入队操作
{
QueuePtrp;
p=(QueuePtr)malloc(sizeof(QNode));
p-data=e;
p-next=NULL;
Q-rear-next=p;
Q-rear=p;
}
BiTNodeDeQueue(LinkQueue*Q)//出对操作
{
BiTNodee;QueuePtrp;
p=Q-front-next;
e=p-data;
Q-front-next=p-next;
if(Q-rear==p)
Q-rear=Q-front;
free(p);
return(e);
}
intQueueEmpty(LinkQueue*Q)//判断队列是否为空
{
if(Q-front==Q-rear)
return1;
else
return0;
}
BiTreeCreateBiTree()//创建二叉树
{
charp;BiTreeT;
scanf(\"%c\",
if(p==\'\')
T=NULL;
else
{
T=(BiTNode*)malloc(sizeof(BiTNode));
T-data=p;
T-lchild=CreateBiTree(T-lchild);
T-rchild=CreateBiTree(T-rchild);
}
return(T);
}
voidPreOrder(BiTreeT)//先序
{
if(T!=NULL)
{
printf(\"%c\",T-data);
PreOrder(T-lchild);
PreOrder(T-rchild);
}
}
voidLevelOrder(BiTreeT)//层次遍历
{
LinkQueueQ;BiTNodep;
InitQueue(
EnQueue(
while(!QueueEmpty(
printf(\"%c\",p.data);
if(p.lchild!=NULL)
EnQueue(
if(p.rchild!=NULL)
EnQueue(
}
}
voidmain()
{
BiTreeTa;
Ta=CreateBiTree();
printf(\"层次遍历:\");
printf(\"\\n\");
LevelOrder(Ta);
printf(\"\\n\");
printf(\"先序遍历:\");
printf(\"\\n\");
PreOrder(Ta);
}
层次使用非递归的，用到队列
先序是用递归的
创建树使用先序递归建树
输入个例子：
abc**de*f**g***(注意*代表空格，因为空格你看不到就不好表示). |
