JavaScript数据结构之二叉树的查找算法示例

本文实例讲述了JavaScript数据结构之二叉树的查找算法。分享给大家供大家参考，具体如下：

前面文章介绍了二叉树的遍历，现在谈谈在二叉树中进行查找。对二叉查找树来说，一般有以下三类查找：最大值，最小值和给定值。

查找最小值就是遍历左子树，直到找到最后一个结点，这是因为在二叉查找树中较小的值总是在左子节点上的。

代码如下：

function getMin(){//查找最小值
    var current=this.root;//指向根节点
    while(current.left!=null){
      current=current.left;
    }
    return current.data;
}

同理可得查找最大值的代码如下：

function getMax(){//查找最大值
  var current=this.root;
  while(current.right!=null){//如果未找到右结点则一直找
    current=current.right;
  }
  return current.data;
}

而在二叉查找树中查找指定值也不难，就是依次判断节点值的查找值的大小，如果节点值小，则继续往右查找，如果节点值大，则继续往左查找，代码如下：

function find(data){//查找某个值
    var current=this.root;
    while(current!=null){
      if(current.data==data){
        return current;
      }else if(current.data>data){//如果节点值比寻找值大，则往左找
        current=current.left;
      }else{//如果节点值比寻找值小，则往右找
        current=current.right;
      }
    }//如果没找到则返回null
    return null;
}

更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

希望本文所述对大家JavaScript程序设计有所帮助。

赞 (0)

相关推荐

  • javascript先序遍历DOM树的方法

    DOM树由文档中的所有节点(元素节点.文本节点.注释节点等)所构成的一个树结构,DOM树的解析和构建是浏览器要实现的关键功能.既然DOM树是一个树结构,那么我们就可以使用遍历树结构的相关方法来对DOM树进行遍历,同时DOM2中的"Traversal"模块又提供了两种新的类型,从而可以很方便地实现DOM树的先序遍历. 注:本文中的5种方法都是对DOM的先序遍历方法(深度优先遍历),并且只关注Element类型. 1. 使用DOM1中的基础接口,递归遍历DOM树 DOM1中为基础类型Nod

  • JavaScript实现树的遍历算法示例【广度优先与深度优先】

    JavaScript实现树的遍历算法示例【广度优先与深度优先】

    本文实例讲述了JavaScript实现树的遍历算法.分享给大家供大家参考,具体如下: <script type="text/javascript"> var t = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]; //下面这段深度优先搜索方法出自Aimingoo的[JavaScript语言精髓与编程实践] var deepView = function(aTree,iNode) { (iNode in aTree)

  • JavaScript实现二叉树的先序、中序及后序遍历方法详解

    本文实例讲述了JavaScript实现二叉树的先序.中序及后序遍历方法.分享给大家供大家参考,具体如下: 之前学数据结构的时候,学了二叉树的先序.中序.后序遍历的方法,并用C语言实现了,下文是用js实现二叉树的3种遍历,并以动画的形式展现出遍历的过程. 整个遍历过程还是采用递归的思想,原理很粗暴也很简单 先序遍历的函数: function preOrder(node){ if(!(node==null)){ divList.push(node); preOrder(node.firstEleme

  • JS二叉树的简单实现方法示例

    本文实例讲述了JS二叉树的简单实现方法.分享给大家供大家参考,具体如下: 今天学习了一下 二叉树的实现,在此记录一下 简单的二叉树实现,并且实现升序和降序排序输出 function Node(data , left,right){ this.data = data; this.left = left; this.right = right; this.show = show; function show(){ return this.data; } }; function Bst(){ this

  • javascript实现二叉树的代码

    javascript实现二叉树的代码

    前言: 二叉树的特点(例图只是二叉树的一种情况,不要尝试用例图推理以下结论) 除了最下面一层,每个节点都是父节点,每个节点都有且最多有两个子节点: 除了嘴上面一层,每个节点是子节点,每个节点都会有一个父节点: 最上面一层的节点(即例图中的节点50)为根节点: 最下面一层的节点称为叶子节点,他们没有子节点: 左子节点的值 < 父节点的值 <= 右节点的值 1 节点的javascript实现 // 节点对象 function Node(data, left, right) { this.data

  • JavaScript数据结构和算法之二叉树详解

    JavaScript数据结构和算法之二叉树详解

    二叉树的概念 二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两棵互不相交的.分别称为根结点的左子树和右子树的二叉树组成. 二叉树的特点 每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点.二叉树中每一个节点都是一个对象,每一个数据节点都有三个指针,分别是指向父母.左孩子和右孩子的指针.每一个节点都是通过指针相互连接的.相连指针的关系都是父子关系. 二叉树节点的定义 二叉树节点定义如下: 复制代码 代码如下: struct

  • JS中的二叉树遍历详解

    二叉树是由根节点,左子树,右子树组成,左子树和友子树分别是一个二叉树. 这篇文章主要在JS中实现二叉树的遍历. 一个二叉树的例子 var tree = { value: 1, left: { value: 2, left: { value: 4 } }, right: { value: 3, left: { value: 5, left: { value: 7 }, right: { value: 8 } }, right: { value: 6 } } } 广度优先遍历 广度优先遍历是从二叉树

  • JavaScript数据结构之二叉树的遍历算法示例

    本文实例讲述了JavaScript数据结构之二叉树的遍历算法.分享给大家供大家参考,具体如下: 三种遍历的代码: function inOrder(node){//中序遍历 if(node!=null){ inOrder(node.left); document.write(node.show()+" "); inOrder(node.right); } } function preOrder(node){//先序遍历 if(node!=null){ document.write(no

  • JS实现的二叉树算法完整实例

    本文实例讲述了JS实现的二叉树算法.分享给大家供大家参考,具体如下: <!DOCTYPE HTML> <head> <title>20130328BinaryTree</title> <metahttp-equiv="Content-Type" content="text/html; charset=utf-8" /> </head> <html> <body> <

  • JavaScript数据结构之二叉树的删除算法示例

    本文实例讲述了JavaScript数据结构之二叉树的删除算法.分享给大家供大家参考,具体如下: 从二叉查找树上删除节点的操作复杂程度取决于删除哪个节点.如果删除没有子节点的节点就非常简单,如果节点只有一个子节点,不管是左子节点还是右子节点,就变得稍微有点复杂,如果节点包含两个子节点就最复杂. 如果待删除节点是叶子节点,那么只需要将从父节点指向它的链接指向null. 如果待删除节点只包含一个子节点,那么原本指向它的节点就得使其指向它的子节点. 如果待删除节点包含两个子节点,那么我们可以采用两种方式

  • javascript实现二叉树遍历的代码

    javascript实现二叉树遍历的代码

    前言: 紧接着上篇 二叉树的javascript实现 ,来说一下二叉树的遍历. 本次一本正经的胡说八道,以以下这个二叉树为例子进行遍历: 接着是要引入二叉树实现的代码: function Node(data, left, right) { this.data = data; this.left = left; this.right = right; this.show = show; } function show() { return this.data; } function BST() {

  • JavaScript数据结构之二叉树的计数算法示例

    本文实例讲述了JavaScript数据结构之二叉树的计数算法.分享给大家供大家参考,具体如下: 二叉查找树的一个用途就是记录一组数据集中数据出现的次数.比如记录成绩的分布,给定一组考试成绩,如果未出现则加入树,如果已经出现则数量加一. 所以要修改Node对象,添加记录成绩出现次数加一,代码如下: function Node(data,left,right){ this.data=data; this.left=left; this.right=right; this.show=show; thi

随机推荐