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

ispring 发布于2019-08-23 11:00 / 1815人阅读

摘要：代码实现创建一个排序二叉树节点类根节点插入节点以上便是创建排序二叉树的实现方式重点在于插入节点的具体实现，即注释的代码片段。

排序二叉树

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

排序二叉树的创建

创建原理
排序二叉树的创建原理与排序二叉树的定义一致，即左孩子的值比当前节点的值小，右孩子的值比当前节点的值大。

代码实现




    
    
    binary-tree

以上便是创建排序二叉树的实现方式：
重点在于插入节点的具体实现，即注释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的栈，返回至方法所在的执行环境的栈，节点插入完毕，再进行下一个节点的插入，操作则同上。以上的解释，如果配合上浏览器的断点调试，食用更佳，更好理解程序的整个执行过程。

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

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

服务器托管私有云二叉树排序树规则实现二叉树 JS二叉树遍历 js怎么建二叉树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/96893.html

数据结构以及相关排序

摘要：桶排序与计数排序的区别桶排序中一个桶可以放一个范围内的多个数据，在各个桶中又可以用其他方法排序，其快速之处在于只用对比同一个桶内的数字而无需与其他桶的数字作对比。与计数排序相比，桶排序需要作二次对比，但可省略桶的个数。哈希表（Hash Table）所有符合键值对即key-value的结构就是哈希。数组其实也是一种哈希。计数排序（复杂度(n+max)）无法统计负数和小数，需要一个...

Brenner 2019-08-23 12:20 评论0 收藏0
使用javascript实现排序二叉树（1）

摘要：使用实现排序二叉树排序二叉树的定义二叉树的基础上，左节点比父节点要小，右节点比父节点要大的二叉树，叫排序二叉树。下期内容实现排序二叉树的中序前序后续遍历实现二叉树的节点查找功能实现排序二叉树的删除节点功能应用排序二叉树实现一个小游戏使用javascript实现排序二叉树（1）排序二叉树的定义：二叉树的基础上，左节点比父节点要小，右节点比父节点要大的二叉树，叫排序二叉树。 show...

Caicloud 2019-08-23 11:29 评论0 收藏0
js数据结构-二叉树（二叉堆）

摘要：二叉树二叉树是一种树形结构，它的特点是每个节点最多只有两个分支节点，一棵二叉树通常由根节点，分支节点，叶子节点组成。二叉树二叉树(Binary Tree)是一种树形结构，它的特点是每个节点最多只有两个分支节点，一棵二叉树通常由根节点，分支节点，叶子节点组成。而每个分支节点也常常被称作为一棵子树。 showImg(https://segmentfault.com/img/bVbmEd...

ningwang 2019-08-23 14:29 评论0 收藏0
js数据结构-二叉树（二叉搜索树）

摘要：前言可能有一部分人没有读过我上一篇写的二叉堆，所以这里把二叉树的基本概念复制过来了，如果读过的人可以忽略前面针对二叉树基本概念的介绍，另外如果对链表数据结构不清楚的最好先看一下本人之前写的数据结构链表二叉树二叉树是一种树形结构，它的特点是前言可能有一部分人没有读过我上一篇写的二叉堆，所以这里把二叉树的基本概念复制过来了，如果读过的人可以忽略前面针对二叉树基本概念的介绍，另外如果对链...

codeKK 2019-08-23 14:34 评论0 收藏0