JavaScript实现简单二叉查找树

frank_fun 发布于2019-08-23 10:38 / 1669人阅读

摘要：二叉查找树二叉查找树也叫二叉搜索树它只允许我们在左节点存储比父节点更小的值，右节点存储比父节点更大的值，上图展示的就是一颗二叉查找树。

前两天接到了蚂蚁金服的面试电话，面试官很直接，上来就抛出了三道算法题。。。

其中有一道关于二叉树实现中序遍历的，当时没回答好，所以特意学习了一把二叉树的知识，行文记录总结。

二叉树&二叉查找树

树相关术语：

节点：树中的每个元素称为一个节点，

根节点：位于整棵树顶点的节点，它没有父节点，如上图 5

子节点：其他节点的后代

叶子节点: 没有子节点的元素称为叶子节点，如上图 3 8 24

二叉树：二叉树就是一种数据结构，它的组织关系就像是自然界中的树一样。官方语言的定义是：是一个有限元素的集合,该集合或者为空、或者由一个称为根的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。

二叉查找树：
二叉查找树也叫二叉搜索树（BST）,它只允许我们在左节点存储比父节点更小的值，右节点存储比父节点更大的值，上图展示的就是一颗二叉查找树。

代码实现

首先创建一个类来表示二叉查找树，它的内部应该有一个Node类，用来创建节点

    function BinarySearchTree () {
        var Node = function(key) {
            this.key = key,
            this.left = null,
            this.right = null
        }
        var root = null
    }

它还应该有一些方法：

insert(key) 插入一个新的键

inOrderTraverse() 对树进行中序遍历，并打印结果

preOrderTraverse() 对树进行先序遍历，并打印结果

postOrderTraverse() 对树进行后序遍历，并打印结果

search(key) 查找树中的键，如果存在返回true,不存在返回fasle

findMin() 返回树中的最小值

findMax() 返回树中的最大值

remove(key) 删除树中的某个键

向树中插入一个键

向树中插入一个新的键，首页应该创建一个用来表示新节点的Node类实例，因此需要new一下Node类并传入需要插入的key值，它会自动初始化为左右节点为null的一个新节点

然后，需要做一些判断，先判断树是否为空，若为空，新插入的节点就作为根节点，如不为空，调用一个辅助方法insertNode()方法，将根节点和新节点传入

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

定义一下insertNode() 方法，这个方法会通过递归得调用自身，来找到新添加节点的合适位置

    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)
            }
        }
    }

完成中序遍历方法

要实现中序遍历，我们需要一个inOrderTraverseNode(node)方法，它可以递归调用自身来遍历每个节点

    this.inOrderTraverse = function() {
        inOrderTraverseNode(root)
    }

这个方法会打印每个节点的key值，它需要一个递归终止条件————检查传入的node是否为null，如果不为空，就继续递归调用自身检查node的left、right节点
实现起来也很简单:

    var inOrderTraverseNode = function(node) {
        if (node !== null) {
            inOrderTraverseNode(node.left)
            console.log(node.key)
            inOrderTraverseNode(node.right)
        }
    }

先序遍历、后序遍历

有了中序遍历的方法，只需要稍作改动，就可以实现先序遍历和后序遍历了
上代码：

这样就可以对整棵树进行中序遍历了

    // 实现先序遍历
    this.preOrderTraverse = function() {
        preOrderTraverseNode(root)
    }
    var preOrderTraverseNode = function(node) {
        if (node !== null) {
            console.log(node.key)
            preOrderTraverseNode(node.left)
            preOrderTraverseNode(node.right)
        }
    }

    // 实现后序遍历
    this.postOrderTraverse = function() {
        postOrderTraverseNode(root)
    }
    var postOrderTraverseNode = function(node) {
        if (node !== null) {
            postOrderTraverseNode(node.left)
            postOrderTraverseNode(node.right)
            console.log(node.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)
            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.inOrderTraverse = function() {
            inOrderTraverseNode(root)
        }
        var inOrderTraverseNode = function(node) {
            if (node !== null) {
                inOrderTraverseNode(node.left)
                console.log(node.key)
                inOrderTraverseNode(node.right)
            }
        }
        // 实现先序遍历
        this.preOrderTraverse = function() {
            preOrderTraverseNode(root)
        }
        var preOrderTraverseNode = function(node) {
            if (node !== null) {
                console.log(node.key)
                preOrderTraverseNode(node.left)
                preOrderTraverseNode(node.right)
            }
        }

        // 实现后序遍历
        this.postOrderTraverse = function() {
            postOrderTraverseNode(root)
        }
        var postOrderTraverseNode = function(node) {
            if (node !== null) {
                postOrderTraverseNode(node.left)
                postOrderTraverseNode(node.right)
                console.log(node.key)
            }
        }
    }

竟然已经完成了添加新节点和遍历的方式，我们来测试一下吧：

定义一个数组，里面有一些元素

var arr = [9,6,3,8,12,15]

我们将arr中的每个元素依此插入到二叉搜索树中，然后打印结果

    var tree = new BinarySearchTree()
    arr.map(item => {
        tree.insert(item)
    })
    tree.inOrderTraverse()
    tree.preOrderTraverse()
    tree.postOrderTraverse()

运行代码后，我们先来看看插入节点后整颗树的情况：

输出结果

中序遍历：

3
6
8
9
12
15

先序遍历：

9
6
3
8
12
15

后序遍历：

3
8
6
15
12
9

很明显，结果是符合预期的，所以，我们用上面的JavaScript代码，实现了对树的节点插入，和三种遍历方法，同时，很明显可以看到，在二叉查找树树种，最左侧的节点的值是最小的，而最右侧的节点的值是最大的，所以二叉查找树可以很方便的拿到其中的最大值和最小值

查找最小、最大值

怎么做呢？其实只需要将根节点传入minNode/或maxNode方法，然后通过循环判断node为左侧(minNode)/右侧(maxNode)的节点为null

实现代码：

    // 查找最小值
    this.findMin = function() {
        return minNode(root)
    }
    var minNode = function(node) {
        if (node) {
            while (node && node.left !== null) {
                node = node.left
            }
            return node.key
        }
        return null
    }
    
    // 查找最大值
    this.findMax = function() {
        return maxNode(root)
    }
    var maxNode = function (node) {
        if(node) {
            while (node && node.right !== null) {
                node =node.right
            }
            return node.key
        }
        return null
    }

所搜特定值

this.search = function(key) {
    return searchNode(root, key)
}

同样，实现它需要定义一个辅助方法,这个方法首先会检验node的合法性，如果为null，直接退出，并返回fasle。如果传入的key比当前传入node的key值小，它会继续递归查找node的左侧节点，反之，查找右侧节点。如果找到相等节点，直接退出，并返回true

    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.remove = function(key) {
        removeNode(root,key)
    }
    var removeNode = function(node, key) {
        if (node === null) {
            return null
        }
        if (key < node.key) {
            node.left = removeNode(node.left, key)
            return node
        }else if(key > node.key) {
            node.right = removeNode(node.right,key)
            return node
        }else{
            //需要移除的节点是一个叶子节点
            if (node.left === null && node.right === null) {
                node = null
                return node
            }
            //需要移除的节点包含一个子节点
            if (node.letf === 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, axu.key)
            return node
        }
    }
    var findMinNode = function(node) {
        if (node) {
            while (node && node.left !== null) {
                node = node.left
            }
            return node
        }
        return null
    }

其中，移除包含两个子节点的节点是最复杂的情况，它包含左侧节点和右侧节点，对它进行移除主要需要三个步骤：

需要找到它右侧子树中的最小节点来代替它的位置

将它右侧子树中的最小节点移除

将更新后的节点的引用指向原节点的父节点

有点绕儿，但必须这样，因为删除元素后的二叉搜索树必须保持它的排序性质

测试删除节点

tree.remove(8)
tree.inOrderTraverse()

打印结果：

3
6
9
12
15

8 这个节点被成功删除了，但是对二叉查找树进行中序遍历依然是保持排序性质的

到这里，一个简单的二叉查找树就基本上完成了，我们为它实现了，添加、查找、删除以及先中后三种遍历方法

存在的问题

但是实际上这样的二叉查找树是存在一些问题的，当我们不断的添加更大/更小的元素的时候，会出现如下情况：

tree.insert(16)
tree.insert(17)
tree.insert(18)

来看看现在整颗树的情况：

很容易发现，它是不平衡的，这又会引出平衡树的概念，要解决这个问题，还需要更复杂的实现，例如：AVL树，红黑树哎，之后再慢慢去学习吧

关于实现二叉排序树，我也找到慕课网的一系列的视频：Javascript实现二叉树算法,
内容和上述实现基本一致

原文链接：行无忌的成长小屋：JavaScript实现简单二叉查找树

GPU云服务器云服务器二叉查找树二叉查找树删除结点二叉树排序树规则二叉排序树

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

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

学习javascript数据结构(四)——树

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

Dean 2019-08-20 13:47 评论0 收藏0
JavaScript 数据结构与算法之美 - 非线性表中的树、堆是干嘛用的？其数据结构是怎样的？

摘要：笔者写的数据结构与算法之美系列用的语言是，旨在入门数据结构与算法和方便以后复习。非线性表中的树堆是干嘛用的其数据结构是怎样的希望大家带着这两个问题阅读下文。其中，前中后序，表示的是节点与它的左右子树节点遍历访问的先后顺序。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言想学好前端，先练好内功，内功不行，...

singerye 2019-08-26 10:09 评论0 收藏0
数据结构与算法:二叉树算法

摘要：因此，根据题目给出的先序遍历和中序遍历，可以画出二叉树选参考数据结构与算法描述实现二叉树算法浅谈数据结构二叉树慕课网实现二叉树算法前端树控件腾讯软件开发面试题内容衔接上一章数据结构与算法:常见排序算法内容提要什么是树　　- 为什么使用树二叉树二叉查找树红黑树Ｂ、Ｂ＋树堆伸展树树可以点击链接感受下笔者用d3.js画的tree https://codepen...

Little_XM 2019-08-22 11:09 评论0 收藏0
JavaScript算法之二叉搜索树

摘要：二叉搜索树的特性二叉搜索树由于其独特的数据结构，使得其无论在增删，还是查找，时间复杂度都是，为二叉树的高度。二叉搜索树的查找查找很简单，根据左子节点比该节点小，右子节点比该节点大的原则进行循环判断即可。什么是二叉树二叉树就是树的每个节点最多只能有两个子节点什么是二叉搜索树二叉搜索树在二叉树的基础上，多了一个条件，就是二叉树在插入值时，若插入值比当前节点小，就插入到左节点，否则插...

khlbat 2019-08-21 16:26 评论0 收藏0
数据结构与算法对的javaScript描述-二叉搜索树

摘要：定义树以及相关概念二叉搜索树的定义首先是二叉树最多有两个节点，分别是左右节点子节点的位置是确定的，变现为左子节点的值小于其父节点右子节点的值大于其父节点在中的描述描述的完整代码传送门可视化传送门节点类树是由节点组成的，要实现树那么先要实现节定义树以及相关概念 showImg(https://segmentfault.com/img/remote/1460000012578627?w...

forrest23 2019-08-21 18:24 评论0 收藏0