注册 登录
编程论坛 → 数据结构与算法

初学数据结构~来看看栈和递归之间的关系~

九转星河 发布于 2017-03-27 21:12， 2300 次点击
这个是最近敲的一个关于二叉树的代码~感觉创建完全二叉树那部分写得不咋的~可以改进~重点看一下非递归遍历那部分~~看了很多网上参考代码~虽然逻辑上可以理解~但感觉三种非递归遍历代码出入很大啊~这里有一种算法能说明递归和非递归之间的转化是如何实现的~不仅适用于二叉树~感觉一般的递归也能通过这种写法转化为非递归~代码就发在这里了~感觉这代码看得入就没必要写注释了~至于有兴趣的能学到多少就靠自己参详了~虽然感觉比传统的非递归遍历写法要麻烦~但感觉非递归的三种遍历之间的关系一目了然啊~仔细看看应该不多不少也能看出一些什么的~

程序代码：
#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;
}

0 回复
1
©2025, BCCN.NET
电脑版