学过数据结构的都知道, 二叉树是一种非常重要的数据结构, 这种树是有两个子节点分别被成为左右子节点, 一般一个用来存储整数的二叉树节点的定义如下:
/**
* @param {number} val
* @return {}
*/
const TreeNode = function (val) {
this.data = val;
this.left = this.right = null;
};
而二叉查找树是一种特殊的二叉树, 它的主要特征就是: 对于一棵没有重复元素的二叉查找树, 任何一个不为空的节点 node
一定满足 node.left.data < node.data < node.right.data
这个不等式.
那么根据这个二叉查找树最基本的特性, 我们很容易写出查找函数 searchNode
:
至于为什么需要在这里返回父节点呢, 看了下面的 insertNode
就能知道了, 代码如下:
/**
* @param {TreeNode} node
* @param {number} val
* @param {TreeNode} parentNode
* @return {TreeNode[]} node, parentNode
*/
const searchNode = (node, val, parentNode) => {
if (!node) return [null, parentNode];
else {
if (node.data === val) return [node, parentNode];
else if (node.data > val) return searchNode(node.left, val, node);
else if (node.data < val) return searchNode(node.right, val, node);
}
};
那么接下来再来实现向二叉查找树中插入元素的 insertNode
方法, 这个方法正好就用到了上面 searchNode
结果中的父节点:
searchNode
找到目标节点和父节点, 如果目标节点为空, 就根据插入元素的大小, 响应创建父节点的左子结点或右子节点.代码如下:
/**
* @param {TreeNode} root
* @param {number} val
* @return {TreeNode} root
*/
const insertNode = (root, val) => {
if (!root) return new TreeNode(val);
const [node, parentNode] = searchNode(root, val, null);
if (!node) {
const temp = new TreeNode(val);
if (val < parentNode.data) parentNode.left = temp;
else if (val > parentNode.data) parentNode.right = temp;
}
return root;
}
接下来就是难度比较大的删除操作, 先描述算法:
算法说起来简单, 但是实现起来就有一定难度了, 我们解释一下代码的逻辑:
代码如下:
/**
* @param {TreeNode} node
* @param {number} val
* @return {}
*/
const deleteNode = (node, val) => {
if (!node) {
return null;
} else if (val < node.data) {
node.left = deleteNode(node.left, val);
return node;
} else if (val > node.data) {
node.right = deleteNode(node.right, val);
return node;
} else {
if (!node.left) {
return node.right;
} else if (!node.right) {
return node.left;
} else {
let next = node.right;
while (next.left) next = next.left;
node.data = next.data;
node.right = deleteNode(node.right, next.data);
return node;
}
}
}
以上就是一个普通二叉查找树 BST 的三个关键算法了, 二叉查找树还有一个性质, 我们知道中序遍历二叉树的时候, 顺序是左子结点 -> 当前节点 -> 右子节点, 那么二叉查找树的中序遍历结果一定是一个从小到大的有序数列. 下面就是实际应用时的代码:
/**
* @param {TreeNode} node
* @return {}
*/
const inorderTraverse = node => {
if (node) {
inorderTraverse(node.left);
console.log(node.data);
inorderTraverse(node.right);
}
};
let root = insertNode(null, 3);
root = insertNode(root, 5);
root = insertNode(root, 4);
root = insertNode(root, 7);
root = insertNode(root, 6);
inorderTraverse(root); // 3 \n 4 \n 5 \n 6 \n 7
deleteNode(root, 5);
console.log(JSON.stringify(root));
/*
* 3
* \
* 6
* / \
* 4 7
*/
inorderTraverse(root); // 3 \n 4 \n 6 \n 7
Copyright © 2018 - xhu - Powered by Gin,jQuery,Animate.css,Semantic UI