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

类目：三人行考研网>计算机>正文

时间：2020-04-1216:52:22

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

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

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

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

算法：

deffunc(pre[],post[]){

intindex=0;

if(length(pre)==0)returnNULL;

node=BinTnode(pre[0]);

if(length(pre)==1)returnnode;

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]);

returnnode;

}

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

以上就是三人行考研网小编整理的“2021考研计算机复习：依据先序后序生成二叉树 ”相关内容 ，希望对大家有所帮助
，预祝大家能考上理想的院校。更多计算机考研信息尽在三人行考研网计算机频道！

相关推荐：

2021考研：计算机考研难度排行榜

2021考研：计算机专业考研方向有哪些？

2021考研计算机复习备考：PPP协议备考小知识点