资讯专栏INFORMATION COLUMN

数据结构与算法(树) --javascript语言描述

henry14 / 978人阅读

摘要:重建二叉树输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。所以先通过前序遍历找出根节点,然后将中序遍历分为左右子树两组,最后对于每个子树依次递归调用。

重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

思路:二叉树前序遍历第一个点为根节点,中序遍历顺序为先左子树然后根节点最后右子树。所以先通过前序遍历找出根节点,然后将中序遍历分为左右子树两组,最后对于每个子树依次递归调用。

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
//pre为前序遍历序列数组 vin为中序遍历序列数组
function reConstructBinaryTree(pre, vin){
  if(pre.length == 0 || vin.length == 0) {
    return null;
  }
  let root = new TreeNode(pre[0]);
  //根节点在中序遍历中的位置
  let index = vin.indexOf(pre[0]);
  let leftPre = pre.slice(1,index+1);//前序左子树
  let rightPre = pre.slice(index+1);//前序右子属
  let leftVin = vin.slice(0,index);//中序左子树
  let rightVin = vin.slice(index+1);//中序右子树
  //开始递归
  root.left = reConstructBinaryTree(leftPre,leftVin);
  root.right = reConstructBinaryTree(rightPre,rightVin);
  return root;
}

console.log(reConstructBinaryTree([1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]));
二叉树的下一个节点

给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

思路:根据中序遍历的特点,要找到一个节点的下一个节点无非就是三种情况:1、有右子树,这时只需要把其右孩子作为下一个遍历的(并不是要找的)节点,然后沿着该节点的左子树(如果有的话)出发,直到遇到叶子节点,那么该叶子节点就是其下一个要找的节点;2、没有右子树,则判断该节点是否是其父节点的左孩子,如果是则其下一个要找的节点是其父节点;3、如果不是其父节点的左孩子,则把其父节点作为下一个遍历的节点,向上回溯,直到找到父节点没有父节点并且父节点是父节点的父节点的左孩子为止。综合这三种情况就可以找到二叉树中任意一个节点的下一个节点。

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
    this.parent = null;
}
function getNext(node) {
  let curNode = null;
  //第一、判断是否有右孩子
  if(node.right != null) {
    curNode = node.right;
    while(curNode.left !=null) {
      curNode = curNode.left;
    }
    return curNode;
  }
  //第二、判断是否是其父节点的左孩子
  if(node.parent == null) {
    return null;
  }
  if(node.parent.left == node) {
    return node.parent;
  }
  //第三、向上找其父节点,直到父节点是其父节点的父节点的左孩子
  curNode = node.parent;
  while(curNode.parent != null) {
    if(curNode == curNode.parent.left) {
      return curNode.parent;
    }
    curNode = curNode.parent;
  }
  return null;
}

//构建二叉树
let parentNode = createTree(
  ["a","b","d","e","h","i","c","f","g"],
  ["d","b","h","e","i","a","f","c","g"]);

let i = parentNode.left.right.right;//i节点
let b = parentNode.left;//b节点
let f = parentNode.right.left;//f节点
console.log(getNext(i).val);//a
console.log(getNext(b).val);//h
console.log(getNext(f).val);//c

//根据前序遍历和中序遍历构建一颗二叉树
function createTree(pre,vin){
  function TreeNode(x) {
      this.val = x;
      this.left = null;
      this.right = null;
      this.parent = null;
  }
  //pre为前序遍历序列数组 vin为中序遍历序列数组
  function reConstructBinaryTree(pre, vin,parent){
    if(pre.length == 0 || vin.length == 0) {
      return null;
    }
    let root = new TreeNode(pre[0]);
    //根节点在中序遍历中的位置
    let index = vin.indexOf(pre[0]);
    let leftPre = pre.slice(1,index+1);//前序左子树
    let rightPre = pre.slice(index+1);//前序右子属
    let leftVin = vin.slice(0,index);//中序左子树
    let rightVin = vin.slice(index+1);//中序右子树
    //开始递归
    root.parent = parent;
    root.left = reConstructBinaryTree(leftPre,leftVin,root);
    root.right = reConstructBinaryTree(rightPre,rightVin,root);
    return root;
  }

  return reConstructBinaryTree(pre,vin,null);
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/107472.html

相关文章

  • 数据结构算法:二叉算法

    摘要:因此,根据题目给出的先序遍历和中序遍历,可以画出二叉树选参考数据结构与算法描述实现二叉树算法浅谈数据结构二叉树慕课网实现二叉树算法前端树控件腾讯软件开发面试题 内容衔接上一章 数据结构与算法:常见排序算法 内容提要 什么是树   - 为什么使用树 二叉树 二叉查找树 红黑树 B、B+树 堆 伸展树 树 可以点击链接感受下笔者用d3.js画的tree https://codepen...

    Little_XM 评论0 收藏0
  • 分类算法之决策(理论篇)

    摘要:后剪枝先创建完整的决策树,然后再尝试消除多余的节点,也就是采用减枝的方法。 起步 决策树(decision tree)是一个树结构,可以是二叉树或非二叉树,也可以把他看作是 if-else 规则的集合,也可以认为是在特征空间上的条件概率分布。 决策树的结构 以一个简单的用于是否买电脑预测的决策树为例子: showImg(https://segmentfault.com/img/remo...

    jzzlee 评论0 收藏0
  • Java数据结构算法——(基本概念,很重要)

    摘要:有网友私信我,期待我的下一篇数据结构。前言数据结构与算法专题会不定时更新,欢迎各位读者监督。本文介绍数据结构里一些复杂的数据结构树,相应的会补充一些算法。除根节点外,每个节点又可以分为多个不相交的子树。 声明:码字不易,转载请注明出处,欢迎文章下方讨论交流。有网友私信我,期待我的下一篇数据结构。非常荣幸文章被认可,也非常感谢你们的监督。 前言:Java数据结构与算法专题会不定时更新,欢...

    MangoGoing 评论0 收藏0
  • 机器学习实战_集成学习(一)

    摘要:集成学习集成学习通过构建并结合多个学习器来完成学习任务,比单一学习器获得显著优越的泛化性能。在此情形下,初始设置的学习轮数也许还远未达到,可能导致最终集成中只包含很少的基学习器而性能不佳。 集成学习 集成学习(ensemble learning)通过构建并结合多个学习器来完成学习任务,比单一学习器获得显著优越的泛化性能。想要获得好的集成,个体学习器应好而不同,要保证准确性和多样性。要产...

    MingjunYang 评论0 收藏0
  • 机器学习实战_决策

    摘要:基尼指数决策树选择划分属性。又由于设置为,决策树在那里停了下来。这里熵的概念是源于热力学中分子混乱程度的概念,当分子井然有序的时候,熵值接近于那么我们到底应该使用指数还是熵决策树呢事实上大部分情况都没有多大的差别他们会生成类似的决策树。 信息熵 信息熵是衡量样本纯度的一种指标,嘉定当前样本集合D中第k类样本所占的比例为pk(k=1,2,...,|y|),则D的信息熵定义为 showIm...

    hedge_hog 评论0 收藏0
  • SegmentFault 技术周刊 Vol.31 - 码农也要学算法

    摘要:记作称为算法的渐进时间复杂度,简称时间复杂度。学习数据结构与算法之链表链表一种常见的数据结构,可以存储有序的元素集合。首先在大的分类上,它们都是散列算法。 showImg(https://segmentfault.com/img/bVSDvj?w=900&h=385); 当人工智能、AlphaGo、无人驾驶、智能投顾等词语不断在人们视野中出现的时候,意味着我们正步入一个算法的时代。计算...

    cgspine 评论0 收藏0

发表评论

0条评论

henry14

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<