内容简介:二分搜索树也是二叉树,和二叉树长的一样,就是有个特点,每个节点的值比他的左子树的值大,比他的右子树的值小。如下图所示:运行结果如下:左节点值是8 右节点值12 中间节点值是10。
对于我这样一个毕业了一年半左右的前端来说,很摸着良心的讲,平时工作中,没有遇到过写什么树。但是有大块时间的时候,觉得这些还是得好好复习一下,或者说预习。今天的主角是二分搜索树。
二分搜索树
二分搜索树也是二叉树,和二叉树长的一样,就是有个特点,每个节点的值比他的左子树的值大,比他的右子树的值小。如下图所示:
那么接下来就来实现一下这个树:// 声明节点构造函数 当前节点的值,左节点,右节点 class Node { constructor(value) { this.value = value this.left = null this.right = null } } // 二分搜索树构造函数 class BST { constructor() { this.root = null this.size = 0 } getSize() { return this.size } isEmpty() { return this.size === 0 } addNode(v) { // 每次添加子节点后,更新树 this.root = this._addChild(this.root, v) } _addChild(node, v) { if (!node) { this.size++ return new Node(v) } if (node.value > v) { console.log(`在${node.value}节点,添加左节点${v}`) node.left = this._addChild(node.left, v) } else if (node.value < v) { console.log(`在${node.value}节点,添加右节点${v}`) node.right = this._addChild(node.right, v) } return node } } let bst = new BST() // 第一个节点 bst.addNode(10) // 后续节点 bst.addNode(8) bst.addNode(6) bst.addNode(3) bst.addNode(7) bst.addNode(9) bst.addNode(12) bst.addNode(11) bst.addNode(15) bst.addNode(14) console.log(bst) 复制代码
运行结果如下:
左节点值是8 右节点值12 中间节点值是10。
再展开左节点看一下
右边就不再展开赘述了
二分搜索树--遍历
二叉树遍历 分为深度遍历(先序遍历、中序遍历、后序遍历,三种遍历的区别在于何时访问节点), 广度遍历(一层层地遍历)
先序遍历
绕不开的递归又出现了,想起有一天右边同事妹子很开心的和我说她知道了递归的终极奥义: “递归的终极奥义就是:不要想递归是怎么具体一步步实现的”
那我先来实现一下先序遍历
class BST { ... // 添加先序遍历实现,其实就是很简单的几行代码 preTraversal() { this._pre(this.root) } _pre(node) { if (node) { // 访问节点的值 console.log(node.value) // 递归左右子树 this._pre(node.left) this._pre(node.right) } } } // 用上面生成的bst实例执行一下,结果如下图 bst.preTraversal() 复制代码
那么这个结果是如何生成的呢?
- 先是打印10,这个毫无争议 然后 this._pre(node.left),this._pre(node.right)这两个方法看似两行,其实左子树没有遍历完结的话是不会去遍历右子树的
- 此时this._pre(node.left)中参数是如下图部分,同样,会对这部分执行那3行代码,首先会打印8 , 然后以8那个节点作为根节点,去遍历左右子树
- 上面第三步骤时候,打印6之后,先遍历左子树,后遍历右子树。而此时的遍历左子树只是打印3。于是要去遍历6的右子树,也就是打印7。
- 打印7之后,本例中,作为节点8的左节点已经遍历完毕。遍历8的右节点,也就是打印9,之后8的右节点也遍历完毕。
- 再往回退,打印9之后,也就是10节点的左节点已经全部遍历完毕。 所以打印的结果是 10 8 6 3 7 9
- 同样的逻辑此时该去遍历10节点的右节点了。依次打印12 11 15 14 ,所以最终结果就是 10 8 6 3 7 9 12 11 15 14
一步步的推导递归的具体实现后,还真的觉的上面所说递归的奥义那句话总结的是很有意思的。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 数据结构之二分查找
- 数据结构与算法:二分查找
- 数据结构与算法:二分查找
- 数据结构 -二分搜索树 -BinarySearchTree
- 数据结构和算法面试题系列—二分查找算法详解
- LeetCode 81,在不满足二分的数组内使用二分法 II
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。