用JS实现数据结构----排序二叉树

2018-08-13 admin

排序二叉树

图片描述

如上图为典型的排序二叉树,左孩子的值比节点的值小,右孩子的值比节点的值大,关于具体的树的定义及二叉树的定义可以百度或查阅相关资料。


排序二叉树的创建

  1. 创建原理 排序二叉树的创建原理与排序二叉树的定义一致,即左孩子的值比当前节点的值小,右孩子的值比当前节点的值大。
  2. 代码实现
<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <title>binary-tree</title>
    <link rel="stylesheet" href="">
</head>
<body>

    <script  type="text/javascript" charset="utf-8">

        //创建一个排序二叉树
        //
        function BinaryTree() {
            //节点类
            var Node = function(key) {
                this.key = key
                this.left = null
                this.right = null
            }

            // 根节点
            var root = null

            // 1
            var insertNode = function(node, newNode) {
                if(node !== null) {
                    if(newNode.key < node.key) {
                        insertNode(node.left, newNode)
                        if(node.left == null) {
                            node.left = newNode
                        }
                    }else{
                        insertNode(node.right, newNode)
                        if(node.right == null) {
                            node.right = newNode
                        }
                    }
                }

                return null
            }

            //插入节点
            this.insert = function(key) {
                var newNode = new Node(key)
                if(root === null) {
                    root = newNode
                }else {
                    insertNode(root, newNode)
                }
            }

            this.getTree = function() {
                return root
            }
        }

        var tree = new BinaryTree()
        var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 11, 15]
        nodes.forEach(function(item) {
            tree.insert(item)
        })

        console.log(tree.getTree())

    </script>
</body>
</html>

以上便是创建排序二叉树的实现方式: 重点在于插入节点的具体实现,即注释1的代码片段。 其中比较难理解的点在于递归是如何执行, 取当前的节点为{key: 1, left:null, right:null},则当前树如下图:

图片描述

对该树进行插入

           var insertNode = function(node, newNode) {
                if(node !== null) {
                    if(newNode.key < node.key) {
                        insertNode(node.left, newNode)
                        if(node.left == null) {
                            node.left = newNode
                        }
                    }else{
                        insertNode(node.right, newNode)
                        if(node.right == null) {
                            node.right = newNode
                        }
                    }
                }

                return null
            }

首先由根节点8出发,进入node的key为8的栈内1比根节点8要小,进入递归,即进入到了node的key为3的栈内,如下所示:

        3
   -----------------
        8
  --------------------------

当前的值比3小再进入3的左孩子null的栈内


        null
    ------------
        3
   -----------------
        8
  --------------------------

由于null的栈内,node为null,立即退出当前栈,返回至node的key为3的栈,发现左孩子为null,则将key为1的node变成key为3的node的左孩子,同时退出3的栈,返回至8的栈,8的栈左孩子不null,不做任何操作,知道当前方法执行完毕,跳出8的栈,返回至方法所在的执行环境的栈,节点插入完毕,再进行下一个节点的插入,操作则同上。以上的解释,如果配合上浏览器的断点调试,食用更佳,更好理解程序的整个执行过程。

当所有节点插入完毕之后,该排序二叉树也创建完毕。

二叉树创建完毕之后则可对二叉树进行相关的操作(遍历,查找,节点删除等)【待续】

原文链接:https://segmentfault.com/a/1190000015980006

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处。

转载请注明:文章转载自 JavaScript中文网 [https://www.javascriptcn.com]

本文地址:https://www.javascriptcn.com/read-37831.html

文章标题:用JS实现数据结构----排序二叉树

相关文章
Node.js 2014这一年发生了什么
Node.js 的 2014 年充满了不幸和争议. 这一年 Noder 们经历了太多的伤心事, 经历了漫长的等待, 经历了沉重的分裂之痛. 也许 Noder 们不想回忆14年 Node.js land 发生的事情, 但正因为痛才更有铭记的价...
2015-11-12
JavaScript实现PC手机端和嵌入式滑动拼图验证码三种效果
PC和手机端网站滑动拼图验证码效果源码,同时包涵了弹出式Demo,使用ajax形式提交二次验证码所需的验证结果值,嵌入式Demo,使用表单形式提交二次验证所需的验证结果值,移动端手动实现弹出式Demo三种效果 首先要确认前端使用页面,比如...
2017-03-17
Angular2-primeNG文件上传模块FileUpload使用详解
近期在学习使用Angular2做小项目,期间用到很多primeNG的模块。 本系列将结合实战总结angular2-primeNG各个模块的使用经验。 文件上传模块FileUploadModule 首先要在使用该组件的模块内导入文件上传模块 ...
2017-03-09
React.js编程思想
JavaScript框架层出不穷,在很多程序员看来,React.js是创建大型、快速的Web应用的最好方式。这一款由Facebook出品的JS框架,无论是在Facebook还是在Instagram中,它的表现都非常出色。 使用React.j...
2015-11-12
YouTube正式默认使用HTML5视频播放器
YouTube视频网站现在默认使用HTML5播放器,这意味着更好的性能、 稳定性、 电池寿命和甚至是更好的安全性。现在用户通过Chrome、IE 11、Safari 8和Beta版本的Firefox进行浏览的时候都默认使用HTML5视频播放...
2015-11-12
JavaScript常用特效chm下载
下载地址:JavaScript常用特效chm下载 对了,如果打开空白,在手册上右键属性解除锁定即可。 ...
2015-11-12
从2014年的发展来展望JS的未来将会如何
&lt;font face=&quot;寰�杞�闆呴粦, Arial, sans-serif &quot;&gt;2014骞达紝杞�浠惰�屼笟鍙戝睍杩呴€燂紝鍚勭�嶈��瑷€灞傚嚭涓嶇┓锛屼互婊¤冻鐢ㄦ埛涓嶆柇鍙樺寲鐨勯渶姹傘€傝繖浜涜��...
2015-11-12
Vue.js组件tab实现选项卡切换
本文实例为大家分享了vue插件tab选项卡的具体代码,供大家参考,具体内容如下 效果图: 代码如下: &lt;!DOCTYPE html&gt; &lt;html lang=&quot;en&quot;&gt; &lt;head&gt; ...
2017-03-13
JavaScript教程:JS中的原型
Keith Peters 几年前发表的一篇博文,关于学习没有“new”的世界,其中解释了使用原型继承代替构造函数。两者都是纯粹的原型编码。 标准方法(The Standard Way) 一直以来,我们学习的在 JavaScript 里创建对...
2015-11-12
three.js实现围绕某物体旋转
话不多说,请看代码: 可以拖动右上角观察变化 &lt;!DOCTYPE html&gt; &lt;html lang=&quot;en&quot; style=&quot;width: 100%; height:100%;&quot;&gt...
2017-02-17
回到顶部