本文实例讲述了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相关内容感兴趣的读者可查看本站专题:《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》
希望本文所述对大家JavaScript程序设计有所帮助。
P70系列延期,华为新旗舰将在下月发布
3月20日消息,近期博主@数码闲聊站 透露,原定三月份发布的华为新旗舰P70系列延期发布,预计4月份上市。
而博主@定焦数码 爆料,华为的P70系列在定位上已经超过了Mate60,成为了重要的旗舰系列之一。它肩负着重返影像领域顶尖的使命。那么这次P70会带来哪些令人惊艳的创新呢?
根据目前爆料的消息来看,华为P70系列将推出三个版本,其中P70和P70 Pro采用了三角形的摄像头模组设计,而P70 Art则采用了与上一代P60 Art相似的不规则形状设计。这样的外观是否好看见仁见智,但辨识度绝对拉满。
更新动态
- 欢乐钓鱼大师最稀有的鱼是什么 欢乐钓鱼大师最稀有的鱼攻略
- ABC唱片-《蔡琴.三十周年纪念版》6N纯银镀膜[WAV+CUE]
- ABC唱片-《汉斯.德斯辛克.心中布鲁斯》6N纯银镀膜[WAV+CUE]
- 群星《DJ·夜色魅影HQ》头版限量[低速原抓WAV+CUE]
- 《如龙》桐生声优被警察拦下盘问:你有犯罪记录吗?
- 游族2023年净利润0.91亿元 《少年西游记2》即将公测
- 曝快手北京游戏事业部全数被裁 项目测试数据未达标
- 李雨寰.2012-我可是天使【有凰音乐】【WAV+CUE】
- 刘美君.1991-听我细诉【BMG】【WAV+CUE】
- 群星.2016-滚石爱情故事3CD【滚石】【WAV+CUE】
- 欢乐钓鱼大师怎么解锁全地图 欢乐钓鱼大师全地图解锁方法
- 欢乐钓鱼大师锦标赛在哪里进 欢乐钓鱼大师锦标赛入口位置介绍
- 欢乐钓鱼大师ios兑换码在哪 欢乐钓鱼大师ios兑换码介绍
- 蒋小雨《夜空的风HQ》头版限量编号[低速原抓WAV+CUE]
- [ABC]邓丽君-初恋的地方[6N纯银镀膜][正版CD低速原抓WAV+CUE]