javascript算法之二叉搜索树的示例代码

什么是二叉树

二叉树就是树的每个节点最多只能有两个子节点

什么是二叉搜索树

二叉搜索树在二叉树的基础上，多了一个条件，就是二叉树在插入值时，若插入值比当前节点小，就插入到左节点，否则插入到右节点；若插入过程中，左节点或右节点已经存在，那么继续按如上规则比较，直到遇到一个新的节点。

二叉搜索树的特性

二叉搜索树由于其独特的数据结构，使得其无论在增删，还是查找，时间复杂度都是O(h)，h为二叉树的高度。因此二叉树应该尽量的矮，即左右节点尽量平衡。

二叉搜索树的构造

要构造二叉搜索树，首先要构造二叉树的节点类。由二叉树的特点可知，每个节点类都有一个左节点，右节点以及值本身，因此节点类如下：

接着构造二叉搜索树

这里this.root就是当前对象的树。

二叉搜索树的新增

由二叉搜索树左子树比节点小，右子树别节点大的特点，可以很简单的写出二叉搜索树新增的算法，如下：

如上代码先判断新增的key与当前节点的key大小，如果小，就递归遍历左子节点，直到找到一个为null的左子节点；如果比当前节点大同理。如上代码{1}{2}{3}{4}之所以能改变this.root的值，是由于JavaScript函数是按值传递，而当参数是非基本类型时，例如这里的对象，其对象的值为内存，因此每次都会直接改变this.root的内容。

二叉搜索树的遍历

二叉搜索树分为先序、中序、后序三种遍历方式。

如上是中序遍历。

这里需要理解的一点是递归。要知道，函数的执行可以抽象为一种数据结构——栈。针对函数的执行，会维护一个栈，来存储函数的执行。函数在每一次递归时，都会将当前的执行环境入栈并记录执行的位置。以上述代码为例，有如下一个数据

其会从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

不难发现，无论前中后序，永远都是先递归左节点，当左节点遍历完毕时再弹出栈，遍历有节点。他们唯一不同的点在与访问该节点本身的时机。

二叉搜索树的查找

查找很简单，根据左子节点比该节点小，右子节点比该节点大的原则进行循环判断即可。

二叉搜索树的删除

删除较为复杂，需要根据不同情况判断

首先判断该节点是否有左子树，如果没有左子节树，则直接将右子树的根节点替换被删除节点；

如果有，则将右子树的最小节点替换被删除节点；

总结

总的来说，通过这次简单的二叉搜索树的学习，让我重新认识了递归，以前对于递归的理解只是一些简单的理论概念，这次深入实践让我对递归的理解又加深了许多。

这让我想到了数学的学习，数学的理论公式是很容易记住掌握的，如果说对一个知识点的掌握满分是十分，那么直到真正去实践它之前，只看公式的掌握只能是2分，因为公式很简单，就几句话几个原则，但是遇到的问题是千变万化的，只有真正将理论付诸实践，经过各种实践的打磨蹂躏，才能真正理解它其中的奥秘。

相关推荐：

三种JavaScript模拟实现封装的方式及写法区别分享

详解JavaScript自执行函数和jQuery扩展方法

JavaScript中Require调用js实例讲解

以上就是javascript算法之二叉搜索树的示例代码的详细内容，更多请关注Gxl网其它相关文章！