在先序、中序非递归算法中为什么使用栈?能不能借助其它数据结构来实现?vc++-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

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

2018-07-17 15:15:10 1576 2
这是一个简答题,回答一下就行了,别弄太多字
取消 提交回答
全部回答(2)
  • 聚小编
    2019-07-17 22:55:11

    #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);
    }*/
    0 0
  • 寒凝雪
    2019-07-17 22:55:11
    因为先序和中序遍历需要多次经过结点,但不会访问,用非递归算法需要记录所经过的路径,这样便于返回.用什么结构倒不是关键的,主要的是你要保证存储它的数据结构的存取顺序,先进的后出。
    0 0
添加回答
相关问答

1

回答

如何构建机器学习算法?

问问小秘 2020-04-15 14:07:23 35602浏览量 回答数 1

25

回答

云服务器网站没有被百度和google收录或者收录少怎么办?

qilu 2014-05-20 18:13:19 30162浏览量 回答数 25

38

回答

干货分享:DBA专家门诊一期:索引与sql优化问题汇总

xiaofanqie 2014-12-25 15:13:38 92068浏览量 回答数 38

9

回答

换个角度理解正则表达式

jagen 2014-07-23 14:00:21 25231浏览量 回答数 9

37

回答

阿里官方Java代码规范标准《阿里巴巴Java开发手册》下载

管理贝贝 2017-02-10 15:14:36 77688浏览量 回答数 37

13

回答

【阿里云产品公测】开放搜索服务之 智能聊天实现

啊里新人 2014-10-21 10:41:20 33667浏览量 回答数 13

6

回答

弹性计算。。

d1004 2011-11-23 14:35:13 24686浏览量 回答数 6

26

回答

云数据库OceanBase的架构演进【精品问答集锦】

管理贝贝 2016-09-02 16:57:42 44273浏览量 回答数 26

24

回答

比赛_快速入门_4_19_update_仅供参考,思维不要受局限

小斯never 2015-03-22 18:22:43 33227浏览量 回答数 24

5

回答

C语言算法 【精品问答合集】

我是管理员 2018-07-13 15:51:28 27063浏览量 回答数 5
+关注
10077
文章
2994
问答
问答排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载