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]是左子树,其他思路同上。
(注:本文来自网络,如有侵权,请联系删除)
2022考研初复试已经接近尾声,考研学子全面进入2023届备考,跨考为23考研的考生准备了10大课包全程准备、全年复习备考计划、目标院校专业辅导、全真复试模拟练习和全程针对性指导;2023考研的小伙伴针也已经开始择校和复习了,跨考考研畅学5.0版本全新升级,无论你在校在家都可以更自如的完成你的考研复习,暑假集训营带来了院校专业初步选择,明确方向;考研备考全年规划,核心知识点入门;个性化制定备考方案,助你赢在起跑线,早出发一点离成功就更近一点!
考研院校专业选择和考研复习计划 | |||
2023备考学习 | 2023线上线下随时学习 | 34所自划线院校考研复试分数线汇总 | |
2022考研复试最全信息整理 | 全国各招生院校考研复试分数线汇总 | ||
2023全日制封闭训练 | 全国各招生院校考研调剂信息汇总 | ||
2023考研先知 | 考研考试科目有哪些? | 如何正确看待考研分数线? | |
不同院校相同专业如何选择更适合自己的 | 从就业说考研如何择专业? | ||
手把手教你如何选专业? | 高校研究生教育各学科门类排行榜 |
相关推荐
跨考考研课程
班型 | 定向班型 | 开班时间 | 高定班 | 标准班 | 课程介绍 | 咨询 |
秋季集训 | 冲刺班 | 9.10-12.20 | 168000 | 24800起 | 小班面授+专业课1对1+专业课定向辅导+协议加强课程(高定班)+专属规划答疑(高定班)+精细化答疑+复试资源(高定班)+复试课包(高定班)+复试指导(高定班)+复试班主任1v1服务(高定班)+复试面授密训(高定班)+复试1v1(高定班) | |
2023集训畅学 | 非定向(政英班/数政英班) | 每月20日 | 22800起(协议班) | 13800起 | 先行阶在线课程+基础阶在线课程+强化阶在线课程+真题阶在线课程+冲刺阶在线课程+专业课针对性一对一课程+班主任全程督学服务+全程规划体系+全程测试体系+全程精细化答疑+择校择专业能力定位体系+全年关键环节指导体系+初试加强课+初试专属服务+复试全科标准班服务 |