前言
大学的东西都忘的差不多了吧?下面我们一起用js简单复习一下大学里《数据结构与算法》中的树。 本文仅使用js实现二叉树,实际工作中可能并用不到(瞎说什么大实话),但是面试挺喜欢问的,毕竟这是计算机相关专业的基础嘛。同时,代码里用了很多递归,这对后期对代码量优化还是很有帮助的。 虚拟dom,使用的就是树结构。 如果你对二叉树很熟悉,那么此文对你可能毫无价值。
参考资料:学习JavaScript数据结构与算法
树数据结构简介
生活中常见树结构有企业的组织架构图、家谱图等。 一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点(除了顶部的第一个节点,称为根结点)以及零个或多个子节点:
二叉树和二叉搜索树
二叉树中的节点最多只能有两个子节点:一个是左侧子节点,另一个是右侧子节点。
二叉搜索树(BST)是二叉树的一种,但是它只允许你在左侧节点存储(比父节点)小的值, 在右侧节点存储(比父节点)大(或者等于)的值。
二叉搜索树将是本文所复习的主要内容。
二叉搜索树的实现
实现二叉搜索树
二话不说,直接上代码,实现一个二叉搜索树的类,复制代码,放到浏览器即可。可以直接看代码,后面再细谈。
function BinarySearchTree() {
// 初始化根结点root为null
let root = null;
// 用于初始化节点,key为值,left right分别为左右子节点
function Node(key) {
this.key = key;
this.left = null;
this.right = null;
};
// 获取树并打出
this.getRoot = function () {
return root
}
// 向树中插入新数据
this.insert = function (key) {
let newNode = new Node(key);
if (root === null) {
root = newNode;
} else {
insertNode(root, newNode);
}
};
// 插值处理递归函数
function insertNode(node, newNode) {
if (newNode.key < node.key) {
if (node.left === null) {
node.left = newNode;
} else {
insertNode(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
insertNode(node.right, newNode);
}
}
};
// 中序遍历
this.inorderTraversal = function (callback) {
inorderTraversalNode(root, callback);
};
// 中序遍历处理递归函数
function inorderTraversalNode(node, callback) {
if (node !== null) {
inorderTraversalNode(node.left, callback);
callback(node.key);
inorderTraversalNode(node.right, callback);
}
};
// 先序遍历
this.preorderTraversal = function (callback) {
preorderTraversalNode(root, callback);
};
// 先序遍历递归函数
function preorderTraversalNode(node, callback) {
if (node !== null) {
callback(node.key);
preorderTraversalNode(node.left, callback);
preorderTraversalNode(node.right, callback);
}
};
// 后序遍历
this.postorderTraversal = function (callback) {
postorderTraversalNode(root, callback);
};
// 后序遍历递归函数
function postorderTraversalNode(node, callback) {
if (node !== null) {
postorderTraversalNode(node.left, callback);
postorderTraversalNode(node.right, callback);
callback(node.key);
}
};
// 查询节点,若存在则返回true 反之 false
this.search = function (key) {
return searchNode(root, key);
};
// 查询节点递归函数
function searchNode(node, key) {
if (node === null) {
return false;
}
if (key < node.key) {
return searchNode(node.left, key);
} else if (key > node.key) {
return searchNode(node.right, key);
} else {
return true;
}
};
// 查询最小值
this.min = function () {
return minNode(root);
};
function minNode(node) {
if (node) {
while (node && node.left !== null) {
node = node.left;
return node.key;
}
return null;
};
}
// 查询最大值
this.max = function () {
return maxNode(root);
};
function maxNode(node) {
if (node) {
while (node && node.right !== null) {
node = node.right;
}
return node.key;
}
return null;
};
// 移除一个节点
this.remove = function (key) {
root = removeNode(root, key);
}
function removeNode(node, key) {
if (node === null) {
return null;
}
if (key < node.key) {
node.left = removeNode(node.left, key);
return node;
} else if (key > node.key) {
node.right = removeNode(node.right, key);
return node;
} else { //键等于node.key
//第一种情况——一个叶节点
if (node.left === null && node.right === null) {
node = null;
return node;
}
//第二种情况——一个只有一个子节点的节点
if (node.left === null) {
node = node.right;
return node;
} else if (node.right === null) {
node = node.left;
return node;
}
//第三种情况——一个有两个子节点的节点
var aux = findMinNode(node.right);
node.key = aux.key;
node.right = removeNode(node.right, aux.key);
return node;
}
};
function findMinNode(node) {
while (node && node.left !== null) {
node = node.left;
}
return node;
};
}
// 上面代码已经实现二叉搜索树,下面开始用起来!
// 先new一个树
let tree = new BinarySearchTree();
console.log('原始树为', tree.getRoot())
// 依次向树中插入数据
tree.insert(10);
tree.insert(2);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(13);
tree.insert(12);
tree.insert(14);
// 获取当前树
console.log('插值后的树为:', tree.getRoot())
// 用于遍历的回调函数
function printNode(value) {
console.log(value);
}
// 先序遍历
console.log('下方为先序遍历结果')
tree.preorderTraversal(printNode);
// 中序遍历
console.log('下方为中序遍历结果')
tree.inorderTraversal(printNode);
// 后序遍历
console.log('下方为后序遍历结果')
tree.postorderTraversal(printNode);
// 查询
console.log('查询10的结果', tree.search(10))
// 最大值最小值
console.log('最大值为:', tree.max())
console.log('最小值为:', tree.min())
// 移除节点
console.log('移除节点 10 之前', tree.getRoot())
tree.remove(10)
console.log('移除节点 10 之后', tree.getRoot())
声明一个Node类表示节点
二叉树需要记录当前节点的值,以及其2个子节点,此处以left right 分别代表左子节点和右子节点。 当创建新当节点时,new 一个Node类即可。
function Node(key) {
this.key = key;
this.left = null;
this.right = null;
};
实现插值函数
插入一个新的值,就是插入一个新节点。这个时候就需要new一个Node类了。如果根结点不存在,即root为null,则表示当前值为第一个节点。否则,则需要一个插值函数用来循环插值。 在二叉树中,基本都是递归,所以这块需要详细思考一下代码的具体运行方式。 代码解释见注释:
// 向树中插入新数据
this.insert = function (key) {
let newNode = new Node(key);
if (root === null) {
root = newNode;
} else { // 如果根结点不为空,则就需要调用插值函数来计算往哪插值了
insertNode(root, newNode);
}
};
// 插值处理递归函数
function insertNode(node, newNode) {
// 如果要插入的值小于当前所在节点的值
if (newNode.key < node.key) {
// 如果新值小于当前节点的值且左侧子节点为空,则当前节点的左子节点就为新插入的值 (1)
if (node.left === null) {
node.left = newNode;
} else {
// 如果当前节点左侧子节点不为空,则把当前节点的左子节点传入insertNode中,开始递归,直到满足上面的 (1)才能顺利插入值
insertNode(node.left, newNode);
}
} else { // 如果要插入的值大于当前所在节点的值,则说明要插的值需要在右侧子节点,递归逻辑同上
if (node.right === null) {
node.right = newNode;
} else {
insertNode(node.right, newNode);
}
}
};
实现先序、中序、后续遍历
这3种遍历没有本质区别,只不过是回调函数的位置不同而已。对比代码一看即懂。
// 中序遍历
this.inorderTraversal = function (callback) {
// 传root,完整的树,作为初始值
inorderTraversalNode(root, callback);
};
// 下面才是遍历的真正方法
function inorderTraversalNode(node, callback) {
// 最开始root为完整的树,当node不为空,就一直递归。为空时,则说明遍历完毕
if (node !== null) {
// node不为空时,继续调用,查看左子节点是否为空。如果左子节点不为空,则还会再次进入方法,直到左子节点为null
inorderTraversalNode(node.left, callback);
// 这个回调函数的调用有点类似koa的洋葱圈模型。当inorderTraversalNode递归到左子节点为空时,才不会继续调用。
// 所以最先最先执行 callback(node.key) 中的节点值是最小的,然后依次越来越大。
callback(node.key);
inorderTraversalNode(node.right, callback);
}
};
节点查询
节点查询就比较简单了,就是循环所有节点,看看是否有相同的值,如果有就返回true,否则false
// 查询节点
this.search = function (key) {
return searchNode(root, key);
};
// 查询节点递归函数
function searchNode(node, key) {
// 此处每次递归时,都会走到。如果所有节点都走完了,也没走到(1) ,那就放弃吧,确实没有
if (node === null) {
return false;
}
if (key < node.key) {
return searchNode(node.left, key);
} else if (key > node.key) {
return searchNode(node.right, key);
} else {
return true; // 相等(1)
}
};
查询最大、最小值
这个也比较简单,在二叉树中,最小值肯定在左侧,最大值肯定在右侧。所以查询最小值,只要循环树左侧的节点,直到节点没了。下图的箭头分别代表寻找最大最小值的访问路径。 这里有个特殊情况需要处理,那就是树本身就为null,直接返回null。最大值同理。
// 查询最小值
this.min = function () {
return minNode(root);
};
function minNode(node) {
if (node) {
// 如果节点存在且左子节点不为空,则一直循环,把node设为node.left
while (node && node.left !== null) {
node = node.left;
return node.key;
}
return null;
};
}
// 查询最大值
this.max = function () {
return maxNode(root);
};
function maxNode(node) {
if (node) {
while (node && node.right !== null) {
node = node.right;
}
return node.key;
}
return null;
};
删除节点
删除节点稍微比较复杂。见注释。 移除含有2个子节点的节点比较复杂,如果所示,需要在他的子树中(注意,是第一层子树),右子树寻找最小的节点,用这个最小的节点替换需要删除的节点。
// 移除一个节点
this.remove = function (key) {
// 删除key后,新的树为removeNode的返回值
root = removeNode(root, key);
}
function removeNode(node, key) {
if (node === null) {
return null;
}
if (key < node.key) {
// 如果要删除的值小于当前节点的值,则说明还没找到那个要删除的节点。
// 递归removeNode时,只有找到了那个节点,即执行了 (1),才会有返回值。并把当前节点的左子节点设为返回值。然后返回node。
// 注意,给node.left赋值时,是递归赋值,node在不同的循环指向不同的节点
node.left = removeNode(node.left, key);
return node;
} else if (key > node.key) {
node.right = removeNode(node.right, key);
return node;
} else { //键等于node.key (1)
/*
* 如果逻辑走到了这边的代码,则说明已经找到了需要删除的节点。
* 但是,该节点有3种情况。
* 1. 该节点没有子节点:则说明该节点为直接设为null即可,也就是说,他的父节点的left设为null, node.left = null;
* 2. 该节点有一个左或者右子节点:若左子节点为null,右子节点直接上移,替换该节点即可node = node.right;,其他类似
* 3. 该节点有2个子节点。这个时候,需要在他的子树中(注意,是第一层子树),右子树寻找最小的节点,用这个最小的节点替换需要删除的节点。
*/
if (node.left === null && node.right === null) {
node = null;
return node;
}
//第二种情况——一个只有一个子节点的节点
if (node.left === null) {
node = node.right;
return node;
} else if (node.right === null) {
node = node.left;
return node;
}
//第三种情况——一个有两个子节点的节点
var aux = findMinNode(node.right);
node.key = aux.key;
node.right = removeNode(node.right, aux.key);
return node;
}
};
// 这个方法用来寻找子树中的最小节点
function findMinNode(node) {
while (node && node.left !== null) {
node = node.left;
}
return node;
};
平衡树 红黑树 堆积树
此类后续再详细讲。