首页 26考研 在职考研 学霸资料 25复试

新东方在线 > 考研 > 计算机 > 考研计算机复习指导 > 正文

扫码加入训练营

牢记核心词

学习得礼盒

2021考研计算机复习备考：依据先序后序生成二叉树

2020-08-27 10:15:00来源：​网络

　　 2021考研计算机复习备考：依据先序后序生成二叉树

　　对于考研专业而言，计算机一定算的上是热门专业之一，也就表示计算机专业考研竞争是非常激烈的，想要更好的复习准备计算机，对于知识点的练习是日常复习必不可少的。小编整理“2021考研计算机复习备考：依据先序后序生成二叉树”内容，希望可以给备战2021考研考生提供参考~~

　　题目：已知二叉树的先序遍历序列和后序遍历序列，试编写生成该二叉树的算法。

　　思路：先序 pre = DLR，后序 post = LRD，D表示根结点，L表示左子树，R为右子树。

　　从先序出发：取先序的第一个元素pre[0]做根，第二个元素pre[1]做左子树的根(不确定也可能是右子树的根，但是先序是根左右，先认为它是左子树的根)，然后去后序序列找pre[1]这个元素的下标位置i，在后序序列里，下标i到最后一个元素间没有元素，说明这个树只有一个子树(可以是左子树或右子树);有元素，那这段序列是右子树，下标i往前到post[0]是左子树。对左子树和右子树分别再这样分出根、左子树和右子树。

　　算法：

　　def func(pre[],post[]) {

　　int index = 0;

　　if(length(pre) == 0) return NULL;

　　node = BinTnode(pre[0]);

　　if(length(pre) == 1) return node;

　　while (pre[1] != post[index]){

　　index=index+1;

　　}

　　node->left = func(pre[1:index+1],post[0:index]);

　　node->right = func(pre[index+2:n],post[index+1:n-1]);

　　return node;

　　}

　　思考：或者从后序出发：取后序最后一个元素做根，倒数第二个元素是右子树的根A，去先序序列里找这个A的下标，这个下标往后的先序序列是右子树，往前到pre[1]是左子树，其他思路同上。

　　以上就是小编整理的“2021考研计算机复习备考：依据先序后序生成二叉树”相关内容，希望对大家有所帮助，预祝大家能考上理想的院校。


本文关键字: 2021 考研计算机 依据先序后序生成二叉树

声明：如本网转载稿涉及版权等问题，请作者致信lulei@xdfzx.com，我们将及时处理。

限时免费
资料推荐

添加班主任领资料

添加考研班主任
免费领取考研历年真题等复习干货资料

  • 1.打开手机微信【扫一扫】，识别上方二维码；
  • 2.添加班主任，可领取学习资料。
更多>>
更多内容
报班学 MBA 优惠券 0元学 院校库

关注新东方在线考研服务号

获得21考研真题及答案解析

1. 打开手机微信【扫一扫】，识别上方二维码；
2.点击【关注公众号】，获取资料大礼包。

考研资料大礼包

历年考研真题及答案解析下载

英语一 英语二 政治 数学一 数学二 数学三 西医综合 教育综合 心理学综合
立即下载
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料
我要
反馈 返回
首页
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
获取验证码
收不到短信？点此接收语音验证码
电话拨打中...请留意来自125909888237的来电
60秒后可重新获取
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
账号密码登录 找回密码
国际手机登录
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
手机快速登录 找回密码
获取验证码
收不到短信？点此接收语音验证码
电话拨打中...请留意来自125909888237的来电
60秒后可重新获取
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
账号密码登录 找回密码
国际手机登录
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
手机快速登录 找回密码
前去听课
获取验证码
收不到短信？点此接收语音验证码
电话拨打中...请留意来自125909888237的来电
60秒后可重新获取
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
账号密码登录 找回密码
国际手机登录
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
手机快速登录 找回密码