JavaScript中怎么定义二叉查找树

JavaScript中怎么定义二叉查找树

这篇“JavaScript中怎么定义二叉查找树”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“JavaScript中怎么定义二叉查找树”文章吧。

树是一种非线性的数据结构，以分层的方式存储数据。树被用来存储具有层级关系的数据，比如文件系统中的文件；树还被用来存储有序列表。这里将研究一种特殊的树：二叉树。选择树而不是那些基本的数据结构，是因为在二叉树上进行查找非常快（而在链表上查找则不是这样），为二叉树添加或删除元素也非常快（而对数组执行添加或删除操作则不是这样）。

树是n个结点的有限集。最上面的为根，下面为根的子树。树的节点包含一个数据元素及若干指向其子树的分支。结点拥有的子树称为结点的度。度为0的结点称为叶子或终端结点。度不为0的结点称为非终端结点或分支结点。树的度是树内各结点的度的最大值。结点的层次从根开始定义，根为第0层。树中结点的最大层次称为树的深度或高度。

二叉树是一种特殊的树，它的子节点个数不超过两个。二叉树具有一些特殊的计算性质，使得在它们之上的一些操作异常高效。通过将子节点的个数限定为 2，可以写出高效的程序在树中插入、查找和删除数据。

在使用 JavaScript 构建二叉树之前，需要给我们关于树的词典里再加两个新名词。一个父节点的两个子节点分别称为左节点和右节点。在一些二叉树的实现中，左节点包含一组特定的值，右节点包含另一组特定的值。二叉查找树是一种特殊的二叉树，相对较小的值保存在左节点中，较大的值保存在右节点中。这一特性使得查找的效率很高，对于数值型和非数值型的数据，比如单词和字符串，都是如此。

二叉查找树由节点组成，所以我们要定义一个Node对象，代码如下：

function Node(data,left,right){//结点类      this.data=data;      this.left=left;      this.right=right;      this.show=show;  }  function show(){//显示节点中数据      return this.data;  }

其中left和right分别用来指向左右子结点。

接下来需要创建二叉查找树的类，代码如下：

function BST(){//树类      this.root=null;      this.insert=insert;      this.inOrder=inOrder;      this.preOrder=preOrder;      this.postOrder=postOrder;  }

接下来是插入节点的代码。遍历小的插左边，大的插右边。代码如下：

function insert(data){//插入操作      var n=new Node(data,null,null);      if(this.root==null){//第一个元素        this.root=n;      }else{        var current=this.root;//永远指向根节点        var parent;        while(true){//一直运行直到找到左结点或右结点为止          parent=current;          if(data<current.data){            current=current.left;            if(current==null){//如果没有左节点              parent.left=n;              break;            }          }else{            current=current.right;            if(current==null){//如果没有右节点              parent.right=n;              break;            }//如果有右节点，则跳到while重新执行，将该节点作为parent重新开始判断          }        }      }  }

以上就是关于“JavaScript中怎么定义二叉查找树”这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注高防服务器网行业资讯频道。

[微信提示：高防服务器能助您降低 IT 成本，提升运维效率，使您更专注于核心业务创新。

[图文来源于网络，不代表本站立场，如有侵权，请联系高防服务器网删除]
[