初学数据结构~来看看栈和递归之间的关系~
这个是最近敲的一个关于二叉树的代码~感觉创建完全二叉树那部分写得不咋的~可以改进~重点看一下非递归遍历那部分~~看了很多网上参考代码~虽然逻辑上可以理解~但感觉三种非递归遍历代码出入很大啊~这里有一种算法能说明递归和非递归之间的转化是如何实现的~不仅适用于二叉树~感觉一般的递归也能通过这种写法转化为非递归~代码就发在这里了~感觉这代码看得入就没必要写注释了~至于有兴趣的能学到多少就靠自己参详了~虽然感觉比传统的非递归遍历写法要麻烦~但感觉非递归的三种遍历之间的关系一目了然啊~仔细看看应该不多不少也能看出一些什么的~
程序代码：#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN sizeof (BiTree)
#define LEN_Qnode sizeof (Qnode)
#define LEN_Stack sizeof (Stack)
typedef struct BiTree
{
int data; //存放数据
struct BiTree* left; //左孩子
struct BiTree* right; //右孩子
}BiTree,*PBiTree;
typedef struct Stack
{
PBiTree p;
int flag;
struct Stack* next;
}Stack,*PStack;
typedef struct LinkStack
{
PStack base;
PStack top;
}LinkStack,*PLinkStack;
typedef struct Queue
{
PBiTree p;
struct Queue* next;
}Qnode,*PQnode;
typedef struct LinkQnode
{
PQnode front;
PQnode rear;
}LinkQnode,*PLinkQnode;
void Creat_Stack(PLinkStack s); //创建一个栈
void Push_Stack(PBiTree p,PLinkStack s); //入栈
void Pop_Stack(PLinkStack s); //出栈
void Del_Stack(PLinkStack s); //清空栈
int Empty_Stack(PLinkStack s); //判断是否栈空
void Creat_Qnode(PLinkQnode q); //创建一个队列
void Push_Qnode(PBiTree p,PLinkQnode q); //入队
void Out_Qnode(PLinkQnode q); //出队
void Del_Qnode(PLinkQnode q); //释放队列
int Empty_Qnode(PLinkQnode q); //判断队列是否为空
void Creat_Tree(PBiTree* p); //创建二叉树
int Add_Tree(PBiTree* p,int data,int n,int m); //输入数据
int Get_Height(PBiTree p); //获取深度
void Visit(PBiTree p);
void Pre_Order(PBiTree p); //前序遍历
void In_Order(PBiTree p); //中序遍历
void Post_Order(PBiTree p); //后序遍历
void Laver_Order(PBiTree p); //按层遍历
void NRPre_Order(PBiTree p); //非递归前序遍历
void NRIn_Order(PBiTree p); //非递归中序遍历
void NRPost_Order(PBiTree p); //非递归后序遍历
void Visit(PBiTree p); //访问节点数据
void Visit_Layer(int a);
void Get_Date(PBiTree p,PQnode qnode); //获取数据
void Del_Tree(PBiTree* p); //释放树
int main()
{
PBiTree p=NULL;
int n=0;
int i=0;
int data=0;
printf("请输入节点个数:");
scanf("%d",&n);
for (i=0;i!=n;++i)
{
printf("请输入第%d个节点的数据:",i+1);
scanf("%d",&data);
Add_Tree(&p,data,1,1);
}
printf("二叉树深度为%d:\n",Get_Height(p));
puts("前序遍历结果为:");
Pre_Order(p);
puts("");
puts("中序遍历结果为:");
In_Order(p);
puts("");
puts("后序遍历结果为:");
Post_Order(p);
puts("");
puts("按层遍历的结果为:");
Laver_Order(p);
puts("");
puts("非递归前序遍历结果为:");
NRPre_Order(p);
puts("");
puts("非递归中序遍历结果为:");
NRIn_Order(p);
puts("");
puts("非递归后序遍历结果为:");
NRPost_Order(p);
puts("");
Del_Tree(&p);
return 0;
}
void Creat_Stack(PLinkStack s) //创建一个栈
{
s->base=s->top=(PStack)malloc(LEN_Stack);
if (s->base==NULL)
{
puts("申请空间失败!");
exit(0);
}
memset(s->base,0,LEN_Stack);
}
void Push_Stack(PBiTree p,PLinkStack s) //入栈
{
PStack t=(PStack)malloc(LEN_Stack);
t->next=s->top;
t->p=p;
t->flag=0;
s->top=t;
}
void Pop_Stack(PLinkStack s) //出栈
{
PStack t=s->top;
if (Empty_Stack(s))
return ;
s->top=s->top->next;
free(t);
}
void Del_Stack(PLinkStack s) //清空栈
{
while (!Empty_Stack(s))
Pop_Stack(s);
}
int Empty_Stack(PLinkStack s) //判断是否栈空
{
return s->top==s->base;
}
void Creat_Qnode(PLinkQnode q)
{
q->front=q->rear=(PQnode)malloc(LEN_Qnode);
if (q->front==NULL)
{
puts("申请空间失败!");
exit(0);
}
memset(q->front,0,LEN_Qnode);
}
void Push_Qnode(PBiTree p,PLinkQnode q) //入队
{
q->rear=q->rear->next=(PQnode)malloc(LEN_Qnode);
q->rear->next=NULL;
q->rear->p=p;
}
void Out_Qnode(PLinkQnode q) //出队
{
PQnode tem=q->front->next;
if (Empty_Qnode(q))
return ;
free(q->front);
q->front=tem;
tem=tem->next;
memset(q->front,0,LEN_Qnode);
q->front->next=tem;
}
void Del_Qnode(PLinkQnode q) //释放队列
{
while (!Empty_Qnode(q))
Out_Qnode(q);
}
int Empty_Qnode(PLinkQnode q) //判断队列是否为空
{
return q->front==q->rear;
}
void Creat_Tree(PBiTree* p)
{
if ((*p=(PBiTree)malloc(LEN))==NULL)
{
puts("创建失败!");
return ;
}
memset(*p,0,LEN);
}
int Add_Tree(PBiTree* p,int data,int n,int m) //输入数据
{
int k=0;
if (n>m)
return 0;
if (*p==NULL)
{
Creat_Tree(p);
(*p)->data=data;
return 1;
}
if (!k)
k=Add_Tree((&(*p)->left),data,n+1,m);
if (!k)
k=Add_Tree((&(*p)->right),data,n+1,m);
while (!k&&n==1)
{
++m;
k=Add_Tree(p,data,n+1,m);
}
return k;
}
void Visit(PBiTree p) //访问节点数据
{
printf("%4d",p->data);
}
void Visit_Layer(int a)
{
printf("%4d",a);
}
void Pre_Order(PBiTree p) //前序遍历
{
if (p==NULL)
return ;
Visit(p);
Pre_Order(p->left);
Pre_Order(p->right);
}
void In_Order(PBiTree p) //中序遍历
{
if (p==NULL)
return ;
In_Order(p->left);
Visit(p);
In_Order(p->right);
}
void Post_Order(PBiTree p) //后序遍历
{
if (p==NULL)
return ;
Post_Order(p->left);
Post_Order(p->right);
Visit(p);
}
int Get_Height(PBiTree p) //获取深度
{
int l=0;
int r=0;
if (p==NULL)
return 0;
l=Get_Height(p->left)+1;
r=Get_Height(p->right)+1;
return l>r?l:r;
}
void Del_Tree(PBiTree* p) //释放树
{
if (*p==NULL)
return ;
Del_Tree(&((*p)->left));
Del_Tree(&((*p)->right));
free(*p);
*p=NULL;
}
void Laver_Order(PBiTree p) //按层遍历
{
LinkQnode q={0};
Creat_Qnode(&q);
Push_Qnode(p,&q);
while (!Empty_Qnode(&q))
{
if (q.front->next->p->left!=NULL)
Push_Qnode(q.front->next->p->left,&q);
if (q.front->next->p->right!=NULL)
Push_Qnode(q.front->next->p->right,&q);
Visit(q.front->next->p);
Out_Qnode(&q);
}
free(q.front);
q.rear->next=q.front->next=NULL;
}
void NRPre_Order(PBiTree p) //非递归前序遍历
{
LinkStack s={0};
Creat_Stack(&s);
Push_Stack(p,&s);
while (!Empty_Stack(&s))
{
if (s.top->p==NULL)
{
Pop_Stack(&s);
continue;
}
if (s.top->flag==0)
{
++s.top->flag;
Visit(s.top->p);
Push_Stack(s.top->p->left,&s);
continue;
}
if (s.top->flag==1)
{
++s.top->flag;
Push_Stack(s.top->p->right,&s);
continue;
}
Pop_Stack(&s);
}
free(s.top);
s.top=s.base=NULL;
}
void NRIn_Order(PBiTree p) //非递归中序遍历
{
LinkStack s={0};
Creat_Stack(&s);
Push_Stack(p,&s);
while (!Empty_Stack(&s))
{
if (s.top->p==NULL)
{
Pop_Stack(&s);
continue;
}
if (s.top->flag==0)
{
++s.top->flag;
Push_Stack(s.top->p->left,&s);
continue;
}
if (s.top->flag==1)
{
++s.top->flag;
Visit(s.top->p);
Push_Stack(s.top->p->right,&s);
continue;
}
Pop_Stack(&s);
}
free(s.top);
s.top=s.base=NULL;
}
void NRPost_Order(PBiTree p) //非递归后序遍历
{
LinkStack s={0};
Creat_Stack(&s);
Push_Stack(p,&s);
while (!Empty_Stack(&s))
{
if (s.top->p==NULL)
{
Pop_Stack(&s);
continue;
}
if (s.top->flag==0)
{
++s.top->flag;
Push_Stack(s.top->p->left,&s);
continue;
}
if (s.top->flag==1)
{
++s.top->flag;
Push_Stack(s.top->p->right,&s);
continue;
}
Visit(s.top->p);
Pop_Stack(&s);
}
free(s.top);
s.top=s.base=NULL;
}
