使用javascript实现排序二叉树（2）

susheng 发布于2019-08-23 11:33 / 2421人阅读

摘要：使用实现排序二叉树上一篇文章我们构造了基本的一个排序二叉树的数据结构，但是仅仅是定义了一个方法去创建二叉排序树，今天我们来给我们的数据结构添加一些遍历的功能。

使用javascript实现排序二叉树（2）

上一篇文章我们构造了基本的一个排序二叉树的数据结构，但是仅仅是定义了一个insert方法去创建二叉排序树，今天我们来给我们的数据结构添加一些遍历的功能。

二叉树的三种遍历方式（以根节点为准来定义前、中、后）的介绍及其应用场景：

前序遍历

顺序：根节点 => 左子树 => 右子树

应用：可以用来构建文件的目录结构，输出所有目录并分层

中序遍历

顺序：左子树 => 根节点 => 右子树

应用：可以进行排序，输出的结果是一个递增的序列

后续遍历

顺序：左子树 => 右子树 => 根节点

应用：后续遍历是先遍历子树，最后到根节点，可以实现统计节点数、计算文件夹大小的功能

思考：

遍历的方法是给谁用的，是否需要暴露出去

如果暴露出去，怎样设计才能让调用者能够获取到每一个节点并且进行对应的操作

结论：

肯定是要暴露出去给别人调用的

给别人调用，具体的逻辑是不确定的，所以应该是调用者传入一个函数，我们在遍历的时候把每一次的节点都传给这个函数，并且去调用这个函数，这样我们不用管具体函数的逻辑，反正已经把它想要的节点给他了，具体怎样操作我们不用管。

分析完毕之后，依然是上次的代码，我们给他添加前序中序和后续遍历的方法：

function BinaryTree(){
  var root = null; //根节点默认为null
  //节点类型的构造函数
  function Node(key){
    this.key = key;
    this.left = null;
    this.right = null;
  }
  //插入方法
  this.insert = function(key){     
    var newNode = new Node(key);
    if(root === null){
       root = newNode;
    }else{
       insertNode(root,newNode)
    }
  }
  var insertNode = function(node,newNode){
    if(newNode.key < node.key){
      if(node.left === null){
         node.left = newNode;
      }else{
         insertNode(node.left,newNode)
      }
    }else{
      if(newNode.key > node.key){
        if(node.right === null){
          node.right = newNode;
        }else{
          insertNode(node.right,newNode)
        }
      }
    }
  }
  
  /*--------------------------------------------------------*/
  /*
      前序遍历： 根节点 => 左子树 => 右子树
  */
  this.preTravel = function(callback){
    //和上面插入操作类似，都用一个内部的函数来实现具体的逻辑，因为需要使用root
     preTravelNode(root,callback); 
  }   
  /* 
      逻辑：
          1. 判断传入的节点是否为null，如果为null就直接return
          2. 如果不为null，则继续对该节点下的left和right进行递归调用
          3. 具体的调用顺序根据为 根节点 => 左子树 => 右子树
  */
  function preTravelNode(node,callback){
    if(node !== null){ 
       callback(node.key); 
       preTravelNode(node.left,callback);
       preTravelNode(node.right,callback);
    }
  }
  
  //中序遍历
  this.middleTravel = function(callback){
    middleTravelNode(root,callback);
  }
  function middleTravelNode(node,callback){
    if(node !== null){
       middleTravelNode(node.left,callback);
       callback(node.key);
       middleTravelNode(node.right,callback);
    }
  }
  
  //后续遍历
  this.nextTravel = function(callback){
    nextTravelNode(root,callback);
  }
  function nextTravelNode(node,callback){
    if(node !== null){
       nextTravelNode(node.left,callback);
       nextTravelNode(node.right,callback);
       callback(node.key);
    }
  }
}

var nodes = [8,7,3,4,6,5,2,9,12]
var binaryTree = new BinaryTree();
nodes.forEach((item)=>{
    binaryTree.insert(item)
})
//测试前序遍历
binaryTree.beforeTravel((key)=>{
  console.log(key) // 8,7,3,2,4,6,5,9,10
})
console.log("--------------------")
//中序遍历
binaryTree.middleTravel((key)=>{
  console.log(key) // 2,3,4,5,6,7,8,9,10
})
console.log("--------------------")
//后续遍历
binaryTree.nextTravel((key)=>{
  console.log(key) // 2,5,6,4,3,7,10,9,8
})

具体的逻辑 ：

判断传入的节点是否为null，如果为null就直接return

如果不为null，则继续对该节点下的left和right进行递归调用

具体的调用顺序根据前序、中序、后序、的访问节点顺序去修改调用的顺序

还是放上这个二叉树的图，根据图去对比测试的遍历结果更直观：

重点：

怎样设计遍历方法，调用者传什么东西进来，我们要暴露什么东西出去，这个地方得想明白

下期内容 ：

实现二叉树的节点查找功能

实现二叉树中节点的删除功能

实现一个二叉树的一个小游戏

上期内容 ：

使用javascript定义一个排序二叉树

GPU云服务器云服务器二叉树排序树规则实现二叉树二叉树 python二叉树

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

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

使用javascript实现排序二叉树（1）

摘要：使用实现排序二叉树排序二叉树的定义二叉树的基础上，左节点比父节点要小，右节点比父节点要大的二叉树，叫排序二叉树。下期内容实现排序二叉树的中序前序后续遍历实现二叉树的节点查找功能实现排序二叉树的删除节点功能应用排序二叉树实现一个小游戏使用javascript实现排序二叉树（1）排序二叉树的定义：二叉树的基础上，左节点比父节点要小，右节点比父节点要大的二叉树，叫排序二叉树。 show...

Caicloud 2019-08-23 11:29 评论0 收藏0
JavaScript 数据结构与算法之美 - 非线性表中的树、堆是干嘛用的？其数据结构是怎样的？

摘要：笔者写的数据结构与算法之美系列用的语言是，旨在入门数据结构与算法和方便以后复习。非线性表中的树堆是干嘛用的其数据结构是怎样的希望大家带着这两个问题阅读下文。其中，前中后序，表示的是节点与它的左右子树节点遍历访问的先后顺序。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言想学好前端，先练好内功，内功不行，...

singerye 2019-08-26 10:09 评论0 收藏0
学习javascript数据结构(四)——树

摘要：原文博客地址学习数据结构四树知乎专栏简书专题前端进击者知乎前端进击者简书博主博客地址的个人博客人之所能，不能兼备，弃其所短，取其所长。通常子树被称作左子树和右子树。敬请期待数据结构篇最后一篇文章学习数据结构五图参考文章树数据结构二叉树前言总括：本文讲解了数据结构中的[树]的概念，尽可能通俗易懂的解释树这种数据结构的概念，使用javascript实现了树，如有纰漏，欢迎批评指正。 ...

Dean 2019-08-20 13:47 评论0 收藏0
数据结构与算法:二叉树算法

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

Little_XM 2019-08-22 11:09 评论0 收藏0
JavaScript实现简单二叉查找树

摘要：二叉查找树二叉查找树也叫二叉搜索树它只允许我们在左节点存储比父节点更小的值，右节点存储比父节点更大的值，上图展示的就是一颗二叉查找树。前两天接到了蚂蚁金服的面试电话，面试官很直接，上来就抛出了三道算法题。。。其中有一道关于二叉树实现中序遍历的，当时没回答好，所以特意学习了一把二叉树的知识，行文记录总结。二叉树&二叉查找树 showImg(https://segmentfault....

frank_fun 2019-08-23 10:38 评论0 收藏0