JavaScript 二叉查找树
2021-03-05 17:26
标签：amp 出栈 javascrip binary dir ack replace bfs api 树是一种分层数据的抽象模型。是一种非顺序数据结构，对于存储需要快速查找的数据非常有效 二叉查找树 每个节点都可以拥有一颗左子树 left 与右子树 right,它们默认为空,同时节点值用 val 表示 二叉查找树节点间存在大小比较关系，因此这里定义一个默认的比较函数方便我们在增删节点的时候进行操作 给予一棵树唯一根节点和比较函数 如果根节点为空，那么将插入节点作为根节点 二叉查找树插入操作的时间复杂度和树的高度成正比，因此时间复杂度是 O(h) 以根、左、右的顺序访问节点 借助while循环和栈实现 以左右根的顺序访问节点 基本问题: 以左右根的顺序访问节点 这里直接实现起来有点困难，不过可以先以‘根右左‘的方式记录下来，最后遍历记录的反转即可 使用队列实现，先访问根节点，再出队根节点并入队其左右子树，根据队列先进先出特性，我们将沿着二叉树从上到下，从左到右的顺序层层访问。 比起深度优先的先序遍历，二者都是先访问根节点，但区别在于深度优先在访问左子树之后依然向左继续纵深查找，而BFS会在访问左子树之后会访问同层的右子树 这里使用循环实现，递归存在一种缺陷就是，当树的高度过于大，递归函数执行栈过多时，会抛出栈溢出异常，使用循环来避免这种问题 这个操作比较复杂的地方在于当删除节点的左右孩子都存在的时候，要考虑删除节点之后如何平衡节点间的大小关系，这是一个从子树上寻找替换节点的过程 这个替换节点需要满足两个条件 替换完成之后，裁去该右子树的最小节点，即可完成删除操作 当根节点存在时，最小深度是1 JavaScript 二叉查找树 标签：amp 出栈 javascrip binary dir ack replace bfs api 原文地址：https://www.cnblogs.com/ltfxy/p/14321810.htmlJavaScript 二叉查找树
关于树
树的结构特点:
每个父节点都有 0 个或多个子节点。
除了根节点外，每个子节点都有且仅有一个父节点
树的深度：取决于父节点的数量
叶子节点：没有子节点的节点
每个根节点最多有两个子节点
根节点大于左子树的任意一个节点，小于右子树的任意一个节点API
定义节点类
class Node {
constructor(val){
this.left = null
this.right = null
this.val = val
}
}
定义比较函数
const Compare = {
LESS_THAN: ‘less‘,
BIGGER_THAN: ‘bigger_than‘,
EQUAL: ‘equal‘
}
function fnCompare(key, nodeKey) {
return key == nodeKey
? Compare.EQUAL
: key > nodeKey
? Compare.BIGGER_THAN
: Compare.LESS_THAN
}
初始化二叉查找树
class BinarySearchTree {
constructor(compareFn = fnCompare) {
this.root = null
this.compareFn = compareFn
}
}
插入节点
如果根节点不为空，那么比较当前节点和待插入节点的大小
如果待插入节点小于当前节点且当前节点的左孩子为 null,则插入左孩子，否则向左子树继续查找
如果不小于且右孩子为 null，则插入右孩子，否则向右子树继续查找
由于二叉查找树的根节点和左右子树存在严格的大小关系，因此每一次插入操作，都会把结点建立在一个空叶子节点上
平均时间复杂度:O(h)
最坏情况: 退化成链表，O(n)
最优情况: 满二叉树，O(logn) // 插入节点
insert(val) {
this.root == null ? (this.root = new Node(val)) : this.insertNode(this.root,val)
}
insertNode(node,val){
this.compareFn(val,node.val) === Compare.LESS_THAN ?
node.left == null ? node.left = new Node(val) : this.insertNode(node.left,val)
:
node.right == null ? node.right = new Node(val) : this.insertNode(node.right,val)
}
先序遍历二叉查找树
先序遍历 递归方式
preOrderTraverse(){
this.root != null && this. preOrderTraverseNode(this.root)
}
preOrderTraverseNode(node,callback=printNode){
node != null && function(){
callback(node)
this.preOrderTraverseNode(node.left)
this.preOrderTraverseNode(node.right)
}.bind(this)()
}
先序遍历 非递归方式
preOrderTraverseByLoop(callback = printNode){
const stack = [],root = this.root
root != null && stack.push(root)
while(stack.length !== 0){
let temp = stack.pop()
callback(temp)
// 后进先出，输出先左后右
temp.right != null && stack.push(temp.right)
temp.left != null && stack.push(temp.left)
}
}
中序遍历 递归方式
中序遍历会按照节点从小到大访问，可以实现顺序排序
以根右右的顺序可实现倒序排序 inOrderTraverse(){
this.root != null && this.inOrderTraverseNode(this.root)
}
inOrderTraverseNode(node,callback = printNode){
node != null && function(){
this.inOrderTraverseNode(node.left)
callback(node)
this.inOrderTraverseNode(node.right)
}.bind(this)()
}
中序遍历 非递归方式
先入栈根节点与左孩子节点，然后出栈左孩子节点并访问，接着出栈根节点并访问，最后访问根节点的右孩子节点 inOrderTraverseByLoop(callback = printNode){
let stack = [], root = this.root
while(1){
while(root != null){
stack.push(root)
root = root.left
}
// 流程完结
if(stack.length === 0) break
let temp = stack.pop()
callback(temp)
root = temp.right
}
}
后序遍历 递归方式
// 后序遍历，递归方式
postOrderTraverse(){
this.root != null && this.postOrderTraverseNode(this.root)
}
postOrderTraverseNode(node, callback = printNode){
node != null && function(){
this.postOrderTraverseNode(node.left)
this.postOrderTraverseNode(node.right)
callback(node)
}.bind(this)()
}
后序遍历 非递归方式
// 后续遍历，非递归实现
postOrderTraverseByLoop(callback = printNode) {
let stack = [], record = [], root = this.root
root != null && stack.push(root)
while(stack.length !== 0){
let temp = stack.pop()
record.push(temp)
temp.left != null && stack.push(temp.left)
temp.right != null && stack.push(temp.right)
}
record.reverse().forEach(node=>callback(node))
}
广度优先遍历 BFS levelOrderTraverse
levelOrderTraverse(callback = printNode){
let queue = [], root = this.root
root != null && queue.push(root)
while(queue.length !== 0){
let cur = queue.shift()
callback(cur)
cur.left != null && queue.push(cur.left)
cur.right != null && queue.push(cur.right)
}
}
查找节点是否存在
// 查找节点
search(val){
return this.searchNode(this.root,val)
}
searchNode(node,val){
if(node == null) return false
const compResult = this.compareFn(val,node.val)
if(compResult === Compare.LESS_THAN){
return this.searchNode(node.left,val)
}else if(compResult === Compare.BIGGER_THAN){
return this.searchNode(node.right,val)
}else{
return true
}
}
最大值和最小值
// 最大值和最小值
max(){
return this.maxOrMin(‘max‘)
}
min(){
return this.maxOrMin(‘min‘)
}
maxOrMin(direction,root = null){
direction = direction === ‘max‘ ? ‘right‘ : ‘left‘
let cur = this.root && root // 提供以任意节点为根节点查找最值的能力
while(cur[direction] != null){
cur = cur[direction]
}
return cur
}
删除节点
// 删除节点
remove(val){
this.root = this.removeNode(this.root,val)
//函数形参只是变量的一份拷贝，拷贝可以通过寻址来改变地址内部的属性(如obj.a = 1），但对于复杂类型如对象，改变拷贝的地址并不会改变对象本身(let a = {};b = a; b = null时对a无影响)，因此要赋值回来
}
removeNode(node,val){
if(node == null){
return null
}
const compResult = this.compareFn(val,node.val)
// 查找
if(compResult === Compare.LESS_THAN){
node.left = this.removeNode(node.left,val)
return node
}else if(compResult === Compare.BIGGER_THAN){
node.right = this.removeNode(node.right,val)
return node
}
// 找到
else{
// 如果是叶子节点，那么直接删除
if(node.left == null && node.right == null){
node = null
return node
}
// 如果只有一个子节点，那么用唯一子节点作为替换
if(node.left == null || node.right == null){
node = node.left == null ? node.right : node.left
return node
}
// 如果左右孩子都存在，为了满足大小比较关系，取右子树中的最小节点替换掉该节点，同时裁去右子树的最小节点
let replaceNode = this.maxOrMin(‘min‘,node.right)
// 替换
node.val = replaceNode.val
// 裁剪
node.right = this.removeNode(node.right,replaceNode.val)
return node
}
}
求树的深度
depth(root = this.root){
if(root == null) return 0
let leftDepth,rightDepth,depth
leftDepth = this.depth(root.left)
rightDepth = this.depth(root.right)
depth = leftDepth > rightDepth ? leftDepth : rightDepth
return depth + 1
}