脚本宝典收集整理的这篇文章主要介绍了

使用javascript实现排序二叉树(1)

脚本宝典小编觉得挺不错的,现在分享给大家,也给大家做个参考,希望能帮助你少写一行代码,多一份安全和惬意。

使用javascript实现排序二叉树(1)

排序二叉树的定义: 二叉树的基础上,左节点比父节点要小,右节点比父节点要大的二叉树,叫排序二叉树。

二叉排序树示例

下面直接进入到我们的javascript代码 定义 排序二叉树的过程

/*
    分析二叉树的结构得出,二叉树由节点构成,每个节点又有自己的左右子树。
    并且有一个根节点
*/
function BinaryTree(){
  var root = null; //根节点默认为null
  /*
    1.节点类型的构造函数,默认左右子树都为空
  */
  function Node(key){
    this.key = key;
    this.left = null;
    this.right = null;
  }
  /*
      2.根据排序二叉树的规律,我们定义一个插入节点的方法,去填充排序二叉树。该方法是BinaryTree的一个方法,需要绑定在this上让其他调用者能调用。而不是作为内部方法。
  */
  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)
        }
      }
    }
  }
}

/*
    测试:查看是否报错,具体的流程逻辑可以通过打断点来判断是否与自己设想的一样。
                      8
                   7     9
                 3         12
               2   4
                     6
                   5
*/
var nodes = [8,7,3,4,6,5,2,9,12]
var binaryTree = new BinaryTree();
nodes.forEach((item)=>{
    binaryTree.insert(item)
})

测试得到的一个二叉排序树

通过断点调试,最后得到的一个二叉树应该是这样的。也是符合二叉排序树的定义的。

重点

  1. 分析数据结构的一个规律,从而能够定义出节点类型中有哪些属性
  2. 方法不要都绑定在 this 上面,因为有些函数是不需要暴露出去的,而是内部使用的。
  3. 我觉得让我收获比较大的是这里的 insert 这个函数中又调用一个 insertNode 的函数,因为事实上真正的插入节点是需要两个参数的,一个父节点,一个要插入的节点。所以会需要递归调用,如果不依靠 insertNode 直接用 insert方法 去递归是没法递归的。因为外部压根获取不到 root 。之前还想着 只用 一个方法就实现插入递归 ,但是确实不行。

下期内容

  1. 实现排序二叉树的 中序 前序 后续 遍历
  2. 实现二叉树的节点查找功能
  3. 实现排序二叉树的 删除节点功能
  4. 应用排序二叉树实现一个小游戏

总结

以上是脚本宝典为你收集整理的

使用javascript实现排序二叉树(1)

全部内容,希望文章能够帮你解决

使用javascript实现排序二叉树(1)

所遇到的程序开发问题,欢迎加入QQ群277859234一起讨论学习。如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典网站推荐给程序员好友。 本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。

80%的人都看过