递归表达式
n! = n*(n-1)! (0!=1)
fn = {
1, n=1,
2, n=2,
f(n-1)+f(n-2), n>2
}
递归经常需要初始条件以及递归表达式。
// 错误写法：
function fibonacci(n) {
return n == 1 || n == 2 ? 1 : fibonacci(n - 1) + fibonacci(n - 2);
}
// 对性能的思考：转换成树
// f(5)f(4)执行了1次
// f(3)执行了2次
// f(2)执行了3次
// f(1)执行了2次
// 递归次数：N>=1+2+4+8+...+2^(n-2)=(1- 2^(n-1))/(2^(n-1) -1)
// 2^10=1024
// 2^20= 1048576
从低端构造递归，斐波拉契数列， reduce和for循环两种写法，本质一样。
1.
function fibonacci(n) {
let [a, b] = [0, 1];
for (let i = 0; i < n; i++) {
[a, b] = [b, a + b];
}
return b;
}
2.
function fibonacci(n) {
return Array(n)
.fill()
.reduce(
([a, b], _) => {
return [b, a + b];
},
[0, 1]
)[1];
}
深度拷贝
function clone(obj) {
if (obj == null || typeof obj !== "object") return obj;
const newObj = new obj.constructor();
for (let key in Object.getOwnPropertyDescriptors(obj)) {
newObj[key] = clone(obj[key]);
}
return newObj;
}
深度比较
function deepCompare(a, b) {
if (
a === null ||
typeof a !== "object" ||
b === null ||
typeof b !== "object"
) {
return a === b;
}
const propsA = Object.getOwnPropertyDescriptors(a);
const propsB = Object.getOwnPropertyDescriptors(b);
if (Object.keys(propsA).length !== Object.keys(propsB).length) {
return false;
}
return Object.keys(propsA).every((key) => deepCompare(a[key], b[key]));
}
树的算法和前端
- DOM
- 选择器
- JSON
- 虚拟DOM
- 文本查找和输入提示
树的递归表示
T: v, [T1,...Tk] 数含有值V和一个子树的列表
class Tree {
constructor(v, children) {
this.v = v;
this.children = children || null;
}
}
const tree = new Tree(10, [
new Tree(5),
new Tree(3, [new Tree(7), new Tree(11)]),
new Tree(2),
]);
树的遍历（先序）
function tree_transverse(tree){
console.log(tree.v)
tree.children && tree.children.forEach(tree_transverse)
} // => 10, 5, 3, 7, 11, 2
树的遍历（后序）
function tree_transverse(tree){
tree.children && tree.children.forEach(tree_transverse)
console.log(tree.v)
} // => 5 7 11 3 2 10
树的遍历（中序）
/**
* ord：根节点打印的位置
**/
function tree_transverse_m(tree, ord = 0) {
let trans = false;
if (!tree.children) {
console.log(tree.v);
return;
}
tree.children.forEach((child, i) => {
if (i === ord) {
trans = true;
console.log(tree.v);
}
tree_transverse_m(child, ord);
});
!trans && console.log(tree.v);
}
tree_transverse_m(tree, 0) //=> 10 5 3 7 11 2
tree_transverse_m(tree, 3) //=> 5 7 11 3 2 10（后序）
tree_transverse_m(tree, 1) //=> 5 10 7 3 11 2
树的查找
function find(tree, prediction) {
return [...tree_transverse(tree).find(prediction)];
}
function find(tree, prediction) {
for (let node of tree_transverse(tree)) {
if (prediction(node)) return node;
}
}
find(tree, (node) => node.v === 2);
树方法：
/**
* 映射树状结构数据(类似数组的map方法)
* @param {object[]} tree - 树状结构的数据
* @param {function} iteratee - 映射单个节点的方法
* @param {object} param2
* @param {string} param2.childrenName - 挂载子节点的字段名
* @param {object[]} acc - 当前节点的所有父节点集合
* @returns {object[]}
*/
export function mapTree(tree, iteratee, { childrenName = 'children' } = {}, acc = []) {
return tree.map((node) => {
const children = node[childrenName];
if (children && children.length) {
return iteratee.call(null, {
node,
acc,
hasChildren: true,
children: mapTree(children, iteratee, { childrenName }, acc.concat(node)),
});
}
return iteratee.call(null, {
node,
acc,
hasChildren: false,
});
});
}
/**
* 遍历树状结构数据(类似数组的forEach方法)
* @param {object[]} tree - 树状结构的数据
* @param {function} iteratee - 处理单个节点的方法
* @param {object} param2
* @param {string} param2.childrenName - 挂载子节点的字段名
* @param {object[]} acc - 当前节点的所有父节点集合
* @returns {object[]}
* @example
* forEachTree((arr, ({ node, acc })) => console.log(node, acc))
*/
export function forEachTree(tree, iteratee, { childrenName = 'children' } = {}, acc = []) {
tree.forEach((node) => {
iteratee.call(null, { node, acc });
const children = node[childrenName];
if (children && children.length) {
forEachTree(children, iteratee, { childrenName }, acc.concat(node));
}
});
}
/**
* 过滤树状结构数据(类似数组的filter方法)
* @param {*} tree - 树状结构的数据
* @param {*} iteratee - 匹配目标节点的方法
* @param {object} param2
* @param {string} param2.childrenName - 挂载子节点的字段名
* @returns {object[]}
*/
export function filterTree(tree, iteratee, { childrenName = 'children' } = {}) {
function filter(list, acc) {
const res = [];
list.forEach((one) => {
const children = one[childrenName];
const _children = children && children.length ? filter(children, acc.concat(one)) : [];
let tmp;
if (_children && children && _children.length === children.length) {
tmp = one;
} else {
tmp = {
...one,
[childrenName]: _children,
};
}
if (iteratee.call(null, one, acc) || _children.length) {
res.push(tmp);
}
});
return res;
}
return filter(tree, []);
}
/**
* 将树状结构数据转化成数组
* @param {*} tree - 树状结构的数据
* @param {*} iteratee - 转化单个节点的数据
* @param {object} param2
* @param {string} param2.childrenName - 挂载子节点的字段名
* @returns {object[]}
* @example
* // returns [1,2,3,4,5]
* treeToList(arr, node => node.id)
*/
export function treeToList(tree, iteratee, { childrenName = 'children' } = {}) {
const acc = [];
forEachTree(
tree,
({ node }) => {
if (isFunction(iteratee)) node = iteratee.call(null, node);
acc.push(node);
},
{ childrenName },
);
return acc;
}
/**
* 查找节点(类似数组的find方法)
* @param {*} tree - 树状结构的数据
* @param {*} iteratee - 匹配目标节点的方法
* @param {object} param2
* @param {string} param2.childrenName - 挂载子节点的字段名
* @returns {{ node, acc }}
* @example
* // returns { node, acc }
* findTree(arr, node => node.id == '1')
*/
export function findTree(tree, iteratee, { childrenName = 'children' } = {}) {
let _node = null;
let _acc = [];
try {
forEachTree(
tree,
({ node, acc }) => {
if (iteratee.call(null, node, acc)) {
_node = node;
_acc = acc.concat(node);
throw new Error();
}
},
{ childrenName },
);
} catch (e) {
// do nothing
}
if (!_node) return { node: null, acc: [] };
return { node: _node, acc: _acc };
}
/**
* 数组转换成树状结构(已废弃)
* @param {object[]} list - 数组
* @param {function} isTopNode - 返回是否为顶层节点
* @param {object} param2
* @param {string} param2.childrenName - 挂载子节点的字段名
* @param {function} param2.sortRule - 同级元素的排序规则
* @returns {object[]}
*/
export function listToTree2(
list,
isTopNode,
{ childrenName = 'children', sortRule, id = 'id', parentId = 'parentId' } = {},
) {
if (!isArray(list)) return [];
// 获取所有id
const idSet = new Set();
list.forEach((one) => one[id] && idSet.add(one[id]));
const _isTopNode = (node) => {
if (isFunction(isTopNode)) return isTopNode(node);
return (
isNullOrUndefined(node[parentId]) ||
!idSet.has(node[parentId]) ||
node[parentId] === -1 ||
node[parentId] === '-1'
);
};
const firstLevelNodes = list.filter(_isTopNode);
function findChildren(node) {
const children = list.filter((one) => one[parentId] === node[id]);
return transform(children);
}
function transform(list) {
const _list = list.map((one) => ({
...one,
children: findChildren(one),
}));
if (isFunction(sortRule)) return _list.sort(sortRule);
return _list;
}
return transform(firstLevelNodes);
}
/**
* 数组转换成树状结构
* @param {object[]} list - 数组
* @param {function} isTopNode - 返回是否为顶层节点
* @param {object} param2
* @param {string} param2.childrenName - 挂载子节点的字段名
* @param {function} param2.sortRule - 同级元素的排序规则
* @returns {object[]}
*/
export function listToTree(
list,
isTopNode,
{ childrenName = 'children', sortRule, id = 'id', parentId = 'parentId' } = {},
) {
if (!isArray(list)) return [];
const _isTopNode = (node) => {
if (isFunction(isTopNode)) return isTopNode(node);
return node[parentId] === -1 || node[parentId] === '-1' || isNullOrUndefined(node[parentId]);
};
const idMapping = list.reduce((acc, current) => {
acc[current[id]] = current;
return acc;
}, {});
const firstLevelNodes = [];
list.forEach((one) => {
if (_isTopNode(one)) {
firstLevelNodes.push(one);
}
const parentEl = idMapping[one[parentId]];
if (parentEl) {
parentEl[childrenName] = [...(parentEl[childrenName] || []), one];
}
});
function sort(list) {
if (!isArray(list)) return [];
const _list = list.map((one) => ({
...one,
[childrenName]: sort(one[childrenName]),
}));
return _list.sort(sortRule);
}
if (isFunction(sortRule)) return sort(firstLevelNodes);
return firstLevelNodes;
}
/**
* 查找目标节点的上一节点
* @param {*} tree - 树状结构的数据
* @param {*} iteratee - 匹配目标节点的方法
* @param {object} param2
* @param {string} param2.childrenName - 挂载子节点的字段名
* @returns {null|object}
*/
export function findPrevNode(tree, iteratee, { childrenName = 'children' } = {}) {
if (!isArray(tree)) return null;
function _findPrevNode(data) {
let prevNode = null;
const res = data.some((one) => {
if (iteratee.call(null, one)) {
return true;
}
const children = one[childrenName];
if (children && children.length) {
const [success, _prevNode] = _findPrevNode(children);
if (success) {
// 从当前节点的子节点中找到目标节点，则返回目标节点前一个
// 若目标节点为子节点中的第一个，则返回当前节点
prevNode = _prevNode || one;
return true;
}
// 如果子节点中未找到目标节点，将子节点中的最后一个节点设置为上一节点
prevNode = _prevNode;
return false;
}
// 不匹配目标节点，且没有子节点，将当前节点设置为上一节点
prevNode = one;
return false;
});
return [res, prevNode];
}
return _findPrevNode(tree)[1];
}
/**
* 查找目标节点的下一节点
* @param {*} tree - 树状结构的数据
* @param {*} iteratee - 匹配目标节点的方法
* @param {object} param2
* @param {string} param2.childrenName - 挂载子节点的字段名
* @returns {null|object}
*/
export function findNextNode(tree, iteratee, { childrenName = 'children' } = {}) {
if (!isArray(tree)) return null;
function _findNextNode(data) {
let nextNode = null;
const res = data.some((one, index) => {
const children = one[childrenName];
if (iteratee.call(null, one)) {
// 匹配到目标节点
if (children && children.length) {
// 有子节点，取子节点中的第一个
nextNode = children[0];
} else {
// 无子节点，取下一个同级节点
nextNode = data[index + 1];
}
return true;
}
if (children && children.length) {
const [success, _nextNode] = _findNextNode(children);
if (success) {
// 从当前节点的子节点中找到目标节点
// 如果子节点中的目标节点存在下一节点，则取下一节点
// 如果子节点中的目标节点为最后一个节点，则取当前节点的下一同级节点
nextNode = _nextNode || data[index + 1];
return true;
}
}
return false;
});
return [res, nextNode];
}
return _findNextNode(tree)[1];
}
/**
* 查找目标节点的所有兄弟节点（包括自身）
* @param {*} tree - 树状结构的数据
* @param {*} iteratee - 匹配目标节点的方法
* @param {object} param2
* @param {string} param2.childrenName - 挂载子节点的字段名
* @returns {object[]}
*/
export function findSiblings(tree, iteratee, { childrenName = 'children' } = {}) {
if (!isArray(tree)) return [];
function _findSiblings(data) {
let res = null;
data.some((one) => {
if (iteratee.call(null, one)) {
res = data;
return true;
}
const children = one[childrenName];
if (children && children.length) {
res = _findSiblings(children);
return Boolean(res);
}
return false;
});
return res;
}
return _findSiblings(tree);
}
/**
* 查找目标节点的所有父级节点（包括自身）
* @param {*} tree - 树状结构的数据
* @param {*} iteratee - 匹配目标节点的方法
* @returns {object[]}
*/
export function treeFindPath(
tree,
id,
{ idName = 'id', parentId = 'parentId', childrenName = 'children' } = {},
) {
if (tree && id) {
let parentItems = [];
let forFn = function (arr, id) {
for (let i = 0; i < arr.length; i++) {
let item = arr[i];
if (item[idName] === id) {
parentItems.push(item);
forFn(tree, item[parentId]);
break;
} else {
if (item[childrenName]) {
forFn(item[childrenName], id);
}
}
}
};
forFn(tree, id);
return parentItems;
}
return [];
}
网友评论