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

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


   2021考研计算机复习备考:依据先序后序生成二叉树  对于考研专业而言,计算机一定算的上是…

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

   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考研计算机复习备考:依据先序后序生成二叉树

    关于作者: admin

    这里可以再内容模板定义一些文字和说明,也可以调用对应作者的简介!或者做一些网站的描述之类的文字活着HTML!

    为您推荐

    发表评论

    电子邮件地址不会被公开。 必填项已用*标注

    评论列表 人参与

    联系我们

    联系我们

    8888-88888888

    在线咨询: QQ交谈

    邮箱: email@admin.com

    工作时间:周一至周五,9:00-17:30,节假日休息

    关注微信
    微信扫一扫关注我们

    微信扫一扫关注我们

    关注微博
    返回顶部