资讯专栏INFORMATION COLUMN

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

henry14 / 1238人阅读

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

</>复制代码

  1. 重建二叉树

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

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

</>复制代码

  1. function TreeNode(x) {
  2.     this.val = x;
  3.     this.left = null;
  4.     this.right = null;
  5. }
  6. //pre为前序遍历序列数组 vin为中序遍历序列数组
  7. function reConstructBinaryTree(pre, vin){
  8. if(pre.length == 0 || vin.length == 0) {
  9. return null;
  10. }
  11. let root = new TreeNode(pre[0]);
  12. //根节点在中序遍历中的位置
  13. let index = vin.indexOf(pre[0]);
  14. let leftPre = pre.slice(1,index+1);//前序左子树
  15. let rightPre = pre.slice(index+1);//前序右子属
  16. let leftVin = vin.slice(0,index);//中序左子树
  17. let rightVin = vin.slice(index+1);//中序右子树
  18. //开始递归
  19. root.left = reConstructBinaryTree(leftPre,leftVin);
  20. root.right = reConstructBinaryTree(rightPre,rightVin);
  21. return root;
  22. }
  23. console.log(reConstructBinaryTree([1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]));

</>复制代码

  1. 二叉树的下一个节点

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

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

</>复制代码

  1. function TreeNode(x) {
  2.     this.val = x;
  3.     this.left = null;
  4.     this.right = null;
  5. this.parent = null;
  6. }
  7. function getNext(node) {
  8. let curNode = null;
  9. //第一、判断是否有右孩子
  10. if(node.right != null) {
  11. curNode = node.right;
  12. while(curNode.left !=null) {
  13. curNode = curNode.left;
  14. }
  15. return curNode;
  16. }
  17. //第二、判断是否是其父节点的左孩子
  18. if(node.parent == null) {
  19. return null;
  20. }
  21. if(node.parent.left == node) {
  22. return node.parent;
  23. }
  24. //第三、向上找其父节点,直到父节点是其父节点的父节点的左孩子
  25. curNode = node.parent;
  26. while(curNode.parent != null) {
  27. if(curNode == curNode.parent.left) {
  28. return curNode.parent;
  29. }
  30. curNode = curNode.parent;
  31. }
  32. return null;
  33. }
  34. //构建二叉树
  35. let parentNode = createTree(
  36. ["a","b","d","e","h","i","c","f","g"],
  37. ["d","b","h","e","i","a","f","c","g"]);
  38. let i = parentNode.left.right.right;//i节点
  39. let b = parentNode.left;//b节点
  40. let f = parentNode.right.left;//f节点
  41. console.log(getNext(i).val);//a
  42. console.log(getNext(b).val);//h
  43. console.log(getNext(f).val);//c
  44. //根据前序遍历和中序遍历构建一颗二叉树
  45. function createTree(pre,vin){
  46. function TreeNode(x) {
  47.     this.val = x;
  48.     this.left = null;
  49.     this.right = null;
  50. this.parent = null;
  51. }
  52. //pre为前序遍历序列数组 vin为中序遍历序列数组
  53. function reConstructBinaryTree(pre, vin,parent){
  54. if(pre.length == 0 || vin.length == 0) {
  55. return null;
  56. }
  57. let root = new TreeNode(pre[0]);
  58. //根节点在中序遍历中的位置
  59. let index = vin.indexOf(pre[0]);
  60. let leftPre = pre.slice(1,index+1);//前序左子树
  61. let rightPre = pre.slice(index+1);//前序右子属
  62. let leftVin = vin.slice(0,index);//中序左子树
  63. let rightVin = vin.slice(index+1);//中序右子树
  64. //开始递归
  65. root.parent = parent;
  66. root.left = reConstructBinaryTree(leftPre,leftVin,root);
  67. root.right = reConstructBinaryTree(rightPre,rightVin,root);
  68. return root;
  69. }
  70. return reConstructBinaryTree(pre,vin,null);
  71. }

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

转载请注明本文地址: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

发表评论

0条评论

henry14

|高级讲师

TA的文章

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