开发者社区> 问答> 正文

在先序中序非递归算法中为什么使用栈?能不能借助其他数据结构来实现?

在先序中序非递归算法中为什么使用栈?能不能借助其他数据结构来实现?

展开
收起
知与谁同 2018-07-20 14:02:29 2269 0
2 条回答
写回答
取消 提交回答
  • 胜天半子
    二叉树的中序、前序、后序的递归、非递归遍历算法,层次序的非递归遍历算法的实现,应包含建树的实现
    悬赏分:20 | 提问时间:2010-6-14 22:33 | 提问者:zjkgood
    要求:遍历的内容应是千姿百态的。
    树与二叉树的转换的实现。以及树的前序、后序的递归、非递归遍历算法,层次序的非递归遍历算法的实现,应包含建树的实现。
    要求:遍历的内容应是千姿百态的。

    推荐答案

    #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;
    2019-07-17 22:55:22
    赞同 展开评论 打赏
  • #include<iostream>
    using namespace std;
    #include<malloc.h>
    #include<stdio.h>
    #include<math.h>
    #define maxsize 20 //最大结点个数
    //#define N 14 //必须输入结点个数(包含虚结点)
    #define M 10 //最大深度
    typedef struct node{
    char data;
    int m; //结点的深度
    struct node*lchild,*rchild;
    }Bitree;
    Bitree*Q[maxsize];
    Bitree*creatree()
    {
    char ch;
    int front,rear;
    // int i=1;
    Bitree *T,*s;
    T=NULL;
    front=1;
    rear=0;
    cout<<"请输入数据"<<endl;
    cin>>ch;
    while(ch!='#')
    {
    // cin>>ch;
    s=NULL;
    if(ch!='@')
    {
    s=(Bitree*)malloc(sizeof(Bitree));
    s->data =ch;
    s->lchild =s->rchild =NULL;
    }
    rear++;
    Q[rear]=s;
    if(rear==1)
    {
    T=s;
    T->m=1; //父结点深度为一
    }
    else{
    if(s!=NULL&&Q[front]!=NULL)
    if(rear%2==0)
    {
    Q[front]->lchild =s;
    Q[front]->lchild ->m =Q[front]->m+1;
    }
    else
    {
    Q[front]->rchild =s;
    Q[front]->rchild ->m =Q[front]->m+1;
    }

    if(rear%2==1)
    front++;
    }
    //i++;
    cin>>ch;
    }
    return T;
    }
    int countleaf(Bitree* T)
    {
    if(T==NULL)
    return (0);
    else if((T->lchild==NULL)&&(T->rchild==NULL))
    return (1);
    else
    return (countleaf(T->lchild)+countleaf(T->rchild));
    }
    int treedepth(Bitree *T)
    {
    if(T==NULL)
    return (0);
    else
    {
    if(treedepth(T->lchild )>treedepth(T->rchild ))
    return(treedepth(T->lchild )+1);
    else
    return (treedepth(T->rchild )+1);
    }
    }
    void output(Bitree*T) //输出打印二叉数
    {
    int i;
    if(T!=NULL)
    {
    output(T->rchild ); //右根左遍历二叉数,结果从上到下显示
    for(i=1;i<=M;i++)
    {
    if(i!=T->m)
    cout<<" ";
    else
    cout<<T->data ;
    }
    cout<<endl;
    //cout<<T->data ;
    output(T->lchild );
    }
    }

    int menu_select( )
    {
    int sn;
    printf(" 打印二叉树问题\n");
    printf("==================\n");
    printf(" 1 二叉树的建立\n");
    printf(" 2 打印二叉树\n");
    printf(" 3 求二叉树叶子结点个数\n");
    printf(" 4 求二叉树的深度\n");
    printf(" 0 退出系统\n");
    printf("==================\n");
    printf(" 请 选 择0-4:\n");
    for( ; ; )
    {
    scanf( "%d", &sn);
    if( sn <0||sn>4)
    printf("\n\t输入错误,重选0-4:\n");
    else
    break;
    }
    return sn;
    }

    int main( )
    {
    Bitree*T;
    for(; ;)
    {
    switch(menu_select())
    {
    case 1: T=creatree();
    printf("\n");
    break;
    case 2: cout<<"打印结果:"<<endl;
    output(T);
    printf("\n");
    break;
    case 3: int i;
    i=countleaf(T);
    cout<<"所求二叉树叶子结点为"<<i;
    cout<<endl;
    break;
    case 4: int j;
    j=treedepth(T);
    cout<<"所求二叉树深度为"<<j;
    cout<<endl;
    break;
    case 0:printf("再见");
    exit(0);
    break;
    }
    }
    return 0;
    }

    /*void main()
    {
    Bitree*T;
    T=creatree();
    cout<<"打印结果:"<<endl;
    output(T);
    }*/
    2019-07-17 22:55:22
    赞同 展开评论 打赏
问答排行榜
最热
最新

相关电子书

更多
数据+算法定义新世界 立即下载
袋鼠云基于实时计算的反黄牛算法 立即下载
Alink:基于Apache Flink的算法平台 立即下载