资讯专栏INFORMATION COLUMN

JavaScript的数据结构与算法(五) —— 二叉搜索树

Anshiii / 3480人阅读

摘要:简介二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。二叉搜索树是二叉树的一种,但是它只允许你在左侧节点存储比父节点小的值,在右侧节点存储比父节点大或者等于的值。树的高度,树的高度体现为节点深度的最大值。

简介

二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。

对于二叉树,有深度遍历和广度遍历,深度遍历有前序、中序以及后序三种遍历方法,广度遍历即我们平常所说的层次遍历。因为树的定义本身就是递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁,而对于广度遍历来说,需要其他数据结构的支撑,比如堆了。

二叉树中的节点最多只能有两个节点:一个是左侧子节点,另一个是右侧子节点
二叉搜索树(BST)是二叉树的一种,但是它只允许你在左侧节点存储(比父节点)小的值,在右侧节点存储(比父节点)大(或者等于)的值。

节点简介

树中的每个元素,都叫做节点。从节点延伸而下的,叫子节点
树顶部的节点叫根节点。每棵树只有一个根节点。
在节点中,有子节点的节点也称为内部节点,没有的话则被称为外部节点或者叶节点
同时在节点中是有祖先和后代关系的,比如节点9的祖先就有13,7,6,15四个。

节点属性

深度: 节点的深度取决于其祖先的数量,节点9的深度就是4。
树的高度,树的高度体现为节点深度的最大值。
比如上图,节点深度最大值为4,则树的高度为4。

代码实现 简单的二叉搜索树

下面我们先来简单实现一个二叉搜索树类,并包含以下的方法:

insert(key): 向树中插入一个新的键

min(): 返回树中最小的值

max(): 返回树中最大的值

search(key): 搜索某个值,在树中则返回true

remove(key): 从树中移除某个键

代码如下:

function BinarySearchTree() {
    var Node = function(key){ //数据结构类
        this.key = key;
        this.left = null;
        this.right = null;
    };
    var root = null; //根节点
    this.insert = function(key){ //插入新的键
        var newNode = new Node(key);
        //special case - first element
        if (root === null){ //根节点为空,作为根节点
            root = newNode;
        } else {
            insertNode(root,newNode); //插入节点操作
        }
    };
    var insertNode = function(node, newNode){
        if (newNode.key < node.key){
            if (node.left === null){ //如果没有左侧节点就插入新的节点
                node.left = newNode;
            } else { //有的话递归
                insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null){  //如果没有右侧节点就插入新的节点
                node.right = newNode;
            } else { //有的话递归
                insertNode(node.right, newNode);
            }
        }
    };
    this.getRoot = function(){
        return root;
    };
    this.search = function(key){  //搜索键
        return searchNode(root, key); //搜索操作
    };
    var searchNode = function(node, key){
        if (node === null){
            return false;
        }
        if (key < node.key){ //如果小于继续从左边搜索
            return searchNode(node.left, key);
        } else if (key > node.key){ //如果大于继续从右边搜索
            return searchNode(node.right, key);
        } else { //命中
            return true;
        }
    };
    this.min = function() { //找最小键
        return minNode(root);
    };
    var minNode = function (node) {
        if (node){
            while (node && node.left !== null) {
                node = node.left;
            }
            return node.key;
        }
        return null;
    };
    this.max = function() { //找最大键
        return maxNode(root);
    };
    var maxNode = function (node) {
        if (node){
            while (node && node.right !== null) {
                node = node.right;
            }
            return node.key;
        }
        return null;
    };
    this.remove = function(element){
        root = removeNode(root, element);
    };
    var findMinNode = function(node){ //返回节点
        while (node && node.left !== null) {
            node = node.left;
        }
        return node;
    };
    var removeNode = function(node, element){ //移除一个节点
        if (node === null){
            return null;
        }
        if (element < node.key){
            node.left = removeNode(node.left, element);
            return node;
        } else if (element > node.key){
            node.right = removeNode(node.right, element);
            return node;
        } else { //命中后分三种情况         
            //移除叶子节点,即该节点没有左侧或者右侧子节点的叶结点
            if (node.left === null && node.right === null){
                node = null;
                return node;
            }
            //移除有一个左侧或者右侧子节点的节点
            if (node.left === null){
                node = node.right; //把引用改为子节点的引用,下同
                return node;
            } else if (node.right === null){
                node = node.left;
                return node;
            }
            //移除有两个子节点的节点
            var aux = findMinNode(node.right); //找到右边子树的最小节点
            node.key = aux.key; //改变节点的键,更新节点的值
            node.right = removeNode(node.right, aux.key); //移除有相同键的节点
            return node; //返回更新后节点的引用
        }
    };
}

二叉树的遍历

前序遍历:根结点 ---> 左子树 ---> 右子树
中序遍历:左子树---> 根结点 ---> 右子树
后序遍历:左子树 ---> 右子树 ---> 根结点
层次遍历:只需按层次遍历即可

例如,求下面二叉树的各种遍历

前序遍历:1 2 4 5 7 8 3 6
中序遍历:4 2 7 5 8 1 3 6
后序遍历:4 7 8 5 2 6 3 1
层次遍历:1 2 3 4 5 6 7 8

前序遍历

代码实现如下:

/**
 * 先序遍历
 * @param {any} callback 回调函数
 */
this.preOrderTranverse = function (callback) {
    preOrderTranverseNode(root, callback)
}
var preOrderTranverseNode = function (node, callback) {
    if (node !== null) {
        callback && callback(node.key);
        preOrderTranverseNode(node.left, callback);
        preOrderTranverseNode(node.right, callback);
    }
}

中序遍历

代码实现如下:
/**

中序遍历

@param {any} callback 回调函数
*/

this.inOrderTraverse = function (callback) {

inOrderTraverseNode(root, callback)

}
var inOrderTraverseNode = function (node, callback) {

if (node !== null) {
    inOrderTraverseNode(node.left, callback);
    callback && callback(node.key)
    inOrderTraverseNode(node.right, callback);
}

}

后序遍历

代码实现如下:

 /**
  * 后序遍历
  * @param {any} callback 回调函数
  */
 this.postOrderTranverse = function (callback) {
     postOrderTranverseNode(root, callback);
 }
 var postOrderTranverseNode = function (node, callback) {
     if (node !== null) {
         postOrderTranverseNode(node.left, callback);
         postOrderTranverseNode(node.right, callback);
         callback(node.key);
     }
 }

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

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

相关文章

  • 学习数据结构算法二叉搜索

    摘要:二叉搜索树是二叉树的一种,其特征是左侧子节点存储比父节点小的值,右侧子节点存储比父节点大或等于父节点的值。实现和这个两个方法其实挺简单的,最小的节点就在二叉搜索树的最左反之,最大的就在最右。 本系列所有文章:第一篇文章:学习数据结构与算法之栈与队列第二篇文章:学习数据结构与算法之链表第三篇文章:学习数据结构与算法之集合第四篇文章:学习数据结构与算法之字典和散列表第五篇文章:学习数据结构...

    denson 评论0 收藏0
  • 学习JavaScript数据结构算法(四):二叉搜索

    摘要:像刚才的这幅图,就是二叉搜索树。而我们本文要学习的内容,就是如何写一个二叉搜索树。但在二叉搜索树中,我们把节点成为键,这是术语。前端路漫漫,且行且歌的前端乐园原文链接寒假前端学习学习数据结构与算法四二叉搜索树 本系列的第一篇文章: 学习JavaScript数据结构与算法(一),栈与队列第二篇文章:学习JavaScript数据结构与算法(二):链表第三篇文章:学习JavaScript数据...

    ingood 评论0 收藏0
  • 学习javascript数据结构(四)——

    摘要:原文博客地址学习数据结构四树知乎专栏简书专题前端进击者知乎前端进击者简书博主博客地址的个人博客人之所能,不能兼备,弃其所短,取其所长。通常子树被称作左子树和右子树。敬请期待数据结构篇最后一篇文章学习数据结构五图参考文章树数据结构二叉树 前言 总括: 本文讲解了数据结构中的[树]的概念,尽可能通俗易懂的解释树这种数据结构的概念,使用javascript实现了树,如有纰漏,欢迎批评指正。 ...

    Dean 评论0 收藏0
  • CSS技巧 - 收藏集 - 掘金

    摘要:笔者作为一位,将工作以来用到的各种优秀资料神器及框架整理在此,毕竟好记性不如烂键盘,此前端知识点大百科全书前端掘金,,不定期更新技巧前端掘金技巧,偶尔更新。计算数组的极值技巧使你的更加专业前端掘金一个帮你提升技巧的收藏集。 CSS 样式画各种图形 - 前端 - 掘金下面是一些我在 CSS 中经常用到的图案,还有一些是在css-tricks看到的。记录一下,以后会用到。会持续更新… 一、...

    Jonathan Shieber 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<