javascript算法之二叉搜索树的示例代码
什么是二叉树
二叉树就是树的每个节点最多只能有两个子节点
什么是二叉搜索树
二叉搜索树在二叉树的基础上,多了一个条件,就是二叉树在插入值时,若插入值比当前节点小,就插入到左节点,否则插入到右节点;若插入过程中,左节点或右节点已经存在,那么继续按如上规则比较,直到遇到一个新的节点。
二叉搜索树的特性
二叉搜索树由于其独特的数据结构,使得其无论在增删,还是查找,时间复杂度都是O(h),h为二叉树的高度。因此二叉树应该尽量的矮,即左右节点尽量平衡。
二叉搜索树的构造
要构造二叉搜索树,首先要构造二叉树的节点类。由二叉树的特点可知,每个节点类都有一个左节点,右节点以及值本身,因此节点类如下:
class Node { constructor(key) { this.key = key; this.left = null; this.right = null; } }
接着构造二叉搜索树
class Tree{ constructor(param = null) { if (param) { this.root = new Node(param); } else { this.root = null; } } }
这里this.root就是当前对象的树。
二叉搜索树的新增
由二叉搜索树左子树比节点小,右子树别节点大的特点,可以很简单的写出二叉搜索树新增的算法,如下:
insert(key) { if (this.root === null) { this.root = new Node(key); } else { this._insertNode(this.root, key); } } _insertNode(node, key) { if (key < node.key) { if (node.left === null) { node.left = new Node(key);{1} } else { this._insertNode(node.left, key);{2} } } else if (key > node.key) { if (node.right === null) { node.right = new Node(key);{3} } else { this._insertNode(node.right, key);{4} } } }
如上代码先判断新增的key与当前节点的key大小,如果小,就递归遍历左子节点,直到找到一个为null的左子节点;如果比当前节点大同理。如上代码{1}{2}{3}{4}之所以能改变this.root的值,是由于JavaScript函数是按值传递,而当参数是非基本类型时,例如这里的对象,其对象的值为内存,因此每次都会直接改变this.root的内容。
二叉搜索树的遍历
二叉搜索树分为先序、中序、后序三种遍历方式。
inOrderTraverse(callback) { this._inOrderTraverse(this.root, callback); } _inOrderTraverse(node, callback) { if (node) { this._inOrderTraverse(node.left, callback); callback(node.key); this._inOrderTraverse(node.right, callback); } }
如上是中序遍历。
这里需要理解的一点是递归。要知道,函数的执行可以抽象为一种数据结构——栈。针对函数的执行,会维护一个栈,来存储函数的执行。函数在每一次递归时,都会将当前的执行环境入栈并记录执行的位置。以上述代码为例,有如下一个数据
其会从11开始,执行{1}入栈,然后进入7,接着执行{1}入栈,然后到5,执行{1}入栈,再到3,执行{1}入栈,此时发现节点3的左子节点为null,因此开始出栈,此时弹出节点3的执行环境,执行{2},{3},发现3的右侧子节点也为null,{3}的递归执行完毕,接着弹出节点5,执行{2}{3},接着弹出7,执行{2}{3}入栈,执行{3}时,发现节点7有右节点,因此继续执行{1},到节点8,再执行{1},8没有左子节点,{1}执行完毕,执行{2}{3},以此类推。
而前序与中序的不同点在于其先访问节点本身,也就是代码的执行顺序为 2 1 3。
后序同理,执行顺序为1 3 2
不难发现,无论前中后序,永远都是先递归左节点,当左节点遍历完毕时再弹出栈,遍历有节点。他们唯一不同的点在与访问该节点本身的时机。
二叉搜索树的查找
查找很简单,根据左子节点比该节点小,右子节点比该节点大的原则进行循环判断即可。
search(value) { if (this.root) { if (value === this.root.key) { return true; } else { return this._searchNode(value, this.root); } } throw new Error('this.root 不存在'); } _searchNode(value, node) { if (!node) { return false; } if (value === node.key) { return true; } if (value > node.key) { return this._searchNode(value, node.right); } else if (value < node.key) { return this._searchNode(value, node.left); } }
二叉搜索树的删除
删除较为复杂,需要根据不同情况判断
首先判断该节点是否有左子树,如果没有左子节树,则直接将右子树的根节点替换被删除节点;
如果有,则将右子树的最小节点替换被删除节点;
remove(key) { this._removeNode(this.root, key); } _removeNode(node, value) { if (!node) { return null; } if (value > node.key) { node.right = this._removeNode(node.right, value); } else if (value < node.key) { node.left = this._removeNode(node.left, value); } else { // 如果没有左子树,那么将右子树根节点作为替换节点 if (!node.left) { return node.right; // 如果存在左子树,那么取右子树最小节点作为替换节点 } else if (node.left) { return this._minNode(node.right); } } }
总结
总的来说,通过这次简单的二叉搜索树的学习,让我重新认识了递归,以前对于递归的理解只是一些简单的理论概念,这次深入实践让我对递归的理解又加深了许多。
这让我想到了数学的学习,数学的理论公式是很容易记住掌握的,如果说对一个知识点的掌握满分是十分,那么直到真正去实践它之前,只看公式的掌握只能是2分,因为公式很简单,就几句话几个原则,但是遇到的问题是千变万化的,只有真正将理论付诸实践,经过各种实践的打磨蹂躏,才能真正理解它其中的奥秘。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。