搜索

二叉树重建递归程序详解

gecimao 发表于 2019-06-06 09:04 | 查看: | 回复:

  希望高手告诉小弟这个递归程序到底是怎么找出来他的后序便利的,题目为:输入一棵二叉树的先序和中序遍历,输出后序遍历。

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  首先说一下程序里变量:n是节点数,s是记录后序遍历的数组,s1是先序序列,s2

  后序序列里0至m-1个节点是树的左子树节点,m至倒数第二个点是树的右子树节

  程序应当是每次把s1中第一个点当做根节点(注意s1递归时候是在变化的),查到

  这个根节点在s2中的位置,因为中根遍历是左子树-根-右子树,而后根是左子树

  组是从0开始计算,所以要多-1。s1+p+1, s2+p+1指针右移到指定位置。s+p存入

  后序 deb fgc a 左子树-右子树-根追问大哥,那个是怎么将元素存在s 中的,我看不懂啊,我只知道那个p每次是S1第一个元素在S2中的下标,但是没有存入s啊.

  还有那个有两个递归啊,第一个我看不出有递归结束条件啊,还有第二个递归语句执行时候,是不是每一次还要将第一个递归语句在执行一次,这样不就是死循环了么.大哥,希望您再解答详细点,把元素是怎么存入s中的告诉我啊,还有就是上面的两个关于递归运行的问题,小弟先谢谢了,分数不是问题的,大哥,加油追答第一个递归结束条件:build(p, s1+1, s2, s);这个递归里p相当于n,当p=0时候结束。也就是s2中找不到*s1这个元素时候结束。

  元素怎么存入s:s[n-1] = s1[0];这一句就是元素存入s。此时s1[0]就是当前找到的那个元素

  s[n-1] = s1[0];//输出根节点(叶子节点当成有n==0的左右子树的根节点)

  日啊,我都看不懂了,希望你可以吧。更多追问追答追问大哥,我不太清楚元素是怎么存入s中的,还有两个递归语句,第一个执行完遇到了结束标志,执行第二个时候,因为第一个在前面,是不是还要再把第一个执行一次啊,还有第二个的递归调用的i是几?

  大哥,加油,小弟谢谢啦追答额,这个需要几个知识点,数据的作用域,函数传值调用,二叉树的遍历。那个打字真的太烦了啊。如果可以画图,可以讲话,那是非常短的。但是这个,我也木有信心了。

  大哥,我不太清楚元素是怎么存入s中的。:有个赋值语句,s[n-1]=s1[0];这里的s和s1都是有函数的参数决定的。记住了,是有传入参数决定的。所以,具体的s[n-1]是第几个,s1又是第几个,自己画图去,我上面的可以做参考的,每一步的递归都写了,想起来好痛苦啊,我很无聊的说。

  还有两个递归语句,第一个执行完遇到了结束标志,执行第二个时候,因为第一个在前面,是不是还要再把第一个执行一次啊,:这里啊,不是哦。会直接往下执行的。相当于函数调用,调用结束后,返回当前调用位置,然后就会往下了,不是吗,只是递归调用是在调用中还有调用而已(而且,调用的函数名还一样,让人晕头就是了)。

本文链接:http://windsorflowers.net/diguilicheng/258.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部