JavaScript实现排序二叉树的基本操作-阿里云开发者社区

开发者社区> 我是小助手> 正文

JavaScript实现排序二叉树的基本操作

简介:
+关注继续查看

记得一开始学习数据结构用的是c语言实现,学了这么久前端就想用JavaScript来实现一下,顺便复习下数据结构。

先来了解下什么是排序二叉树,排序二叉树是具有以下特点的二叉树

  1. 若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值,
  2. 若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值,
  3.  左、右子树也分别为二叉排序树
比如下面这图,左边的值永远小于右边的值

5802796326eaa5f049ddbe1f2c51fd22380425e1

下面我们用代码实现一波

首先是树的结构和根节点


var Node = function(key){//节点结构        this.left = null         this.right = null        this.key = key    }
     var root = null //根节点

二叉树的插入,基本过程是比较要插入的数和当前节点的值大小,按照排序二叉树的特点,左边的值永远小于右边


var insertNode = function(node,newNode){        if(node.key > newNode.key){//要插入的值小于当前节点,左子树遍历            if(node.left === null){                node.left = newNode                return             }else{                insertNode(node.left,newNode)            }        }else if(node.key <= newNode.key){//要插入的值小于当前节点,右子树遍历            if(node.right === null){                node.right = newNode            }else{                insertNode(node.right,newNode)            }        }    }

插入成功后我们分别来实现排序二叉树的前序,中序和后序遍历

前序遍历是先访问根节点,而后是左右节点

中序遍历先访问左节点,而后是根节点和右节点

后序遍历则先访问左右节点,最后是根节点

代码如下


 var inOrderTraverseNode = function(node,callback){//中序遍历        if(node !== null){            inOrderTraverseNode(node.left)            console.log(node.key)            inOrderTraverseNode(node.right)        }    }
   
    var preOrderTraverseNode = function(node,callback){//前序遍历        if(node !== null){            console.log(node.key)            preOrderTraverseNode(node.left)            preOrderTraverseNode(node.right)        }    }
   
    var afterOrderTraversNode = function(node,callback){//后序遍历        if(node !== null){            afterOrderTraversNode(node.left)            afterOrderTraversNode(node.right)            console.log(node.key)        }    }


寻找二叉树的最大值和最小值,这一部分根据排序二叉树的特点很快就能知道,最大值在最右边的叶子节点,最小值处于最左边的叶子节点

var Max = function(node){//最大值        if(node.right !== null){            maxNum = Max(node.right)        }else{            return node.key        }        return maxNum    }
    var Min = function(node){//最小值        if(node.left !== null){            minNum = Min(node.left)        }else{            return node.key        }        return minNum    }

寻找排序二叉树中的指定值,也很简单,以根节点为界,比左边小到左边找,比右边小去右边



var Search = function(node,key){//寻找指定值                    if(node.key === key){                return true            }else{                if(key < node.key && node.left !=null){                    return Search(node.left,key)                }else if(key > node.key && node.left !=null){                    return Search(node.right,key)                }else{                    return false                }            }        }

最麻烦的是删除节点的操作,这里需要分三种情况,删除节点无子树,删除节点为单子树,删除节点有两个子树,

无子树最简单,直接删


 if(node.left === null && node.right === null){                node = null                return node            }

有单子树的:比如下图(画的有点丑。。。),现在我要删掉3,

e81fb51197b811c407957123fedb926020752792



代码实现如下


else if(node.left !== null && node.right === null){                node = node.left                return node            }else if(node.left === null && node.right !== null){                node = node.right                return node            }

最后是删除有两个子树的节点,为了维持我们排序二叉树的性质,首先我们找到要删除节点的右字树的最小值,根据排序二叉树的特点,找到的最小值必定大于要删除节点的左子树的所有值,因为找到的值为右节点的最小值,所以小于要删除节点的右子树的所有值,我们将找到的最小值代替要删除的值,最后删掉一开始找到的最小值的节点,基本过程就相当于替换了要删除节点的值。

下图,我要删掉3


e07b3683ba00ffd0216c7d0cec4007859c55b00c

按照上面的思想,找到4代替3,然后删掉一开始找到的4所在的节点

d8eaedbe5a1a9f4bffc4e19992002d45c1bdeebd


依旧满足排序二叉树的特点

else if(node.left !== null && node.right !== null){                var minNode = finMinNode(node.right)                node.key = minNode.key                node.right = Remove(node.right,minNode.key)                return node            }

到这里排序二叉树的基本功能都实现了

完整代码在GitHub(求GitHub小星星)上,我把双向链表也用JavaScript实现了下,需要的也可以看看


原文发布时间为:2018年06月23日
原文作者:笑佛弥勒

本文来源: 掘金 如需转载请联系原作者



版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
关于 TypeScript 内 constructor signature 的一些失败尝试
关于 TypeScript 内 constructor signature 的一些失败尝试
3 0
如何理解 new (...args: any[]) => any
如何理解 new (...args: any[]) => any
3 0
JavaScript 里三个点 ... 的用法
JavaScript 里三个点 ... 的用法
3 0
TypeScript constructor signature 类型的变量赋值方式
TypeScript constructor signature 类型的变量赋值方式
4 0
Angular 页面元素的DOM级别的删除过程
Angular 页面元素的DOM级别的删除过程
3 0
Angular Shadow Root DOM的一些API
Angular Shadow Root DOM的一些API
4 0
Angular自定义structural指令的实例化过程以及set方法的调用
Angular自定义structural指令的实例化过程以及set方法的调用
4 0
Angular Component TypeScript代码和最后转换生成的JavaScript代码比较
Angular Component TypeScript代码和最后转换生成的JavaScript代码比较
1 0
TypeScript 编译生成的 JavaScript 源代码里的 ɵcmp 属性
TypeScript 编译生成的 JavaScript 源代码里的 ɵcmp 属性
4 0
Angular input控件的click事件表达式如何被转换成JavaScript函数
Angular input控件的click事件表达式如何被转换成JavaScript函数
3 0
+关注
我是小助手
云栖直播
262
文章
6
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载