欢迎您来到懒之才-站长的分享平台!   学会偷懒,并懒出境界是提高工作效率最有效的方法!
首页 >建站经验 >Js&Ajax > JavaScript 实现简单二叉查找树

JavaScript 实现简单二叉查找树

2018-08-18 222 收藏 0 赞一个 0 真差劲 0 去评论

二叉树 & 二叉查找树

1.png

树相关术语:

节点:树中的每个元素称为一个节点。

根节点:位于整棵树顶点的节点,它没有父节点, 如上图 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()

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

2.png

输出结果。

中序遍历:

3
6
8
9
12
15

先序遍历:

9
6
3
8
12
15

后序遍历:

3
8
6
15
12
9

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

查找最小、最大值

怎么做呢?其实只需要将根节点传入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)

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

3.png

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

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

一、推荐使用迅雷或快车等多线程下载软件下载本站资源。

二、未登录会员无法下载,登录后可获得更多便利功能,若未注册,请先注册。

三、如果服务器暂不能下载请稍后重试!总是不能下载,请点我报错 ,谢谢合作!

四、本站所有资源(包括模板、素材、软件、字体等)仅供学习与参考,请勿用于商业用途,否则产生的一切后果将由您自己承担!

五、如有其他问题,请加网站设计交流群(点击这里查看交流群 )进行交流。

六、如需转载本站资源,请注明转载来自并附带链接

七、本站部分资源为加密压缩文件,统一解压密码为:www.aizhanzhe.com

大家评论
分享是个好习惯