在写一个富文本编辑器,其中用到了带父子节点的双向链表,要把无顺序的节点树根据 prev_id ,next_id 处理成顺序的,而且有些节点是带 children 的,children 中的节点同其他节点,可无限嵌套,写了个递归一直报错,希望大佬指点指点,答案被采纳我 v 信转 120 给您(不在乎钱的也可以试一试,这十分考验算法实战能力)
raw_nodes 数据:
const raw_nodes = [
{
"type": "file",
"name": "工作目录二",
"icon": "",
"id": "dgacbecjhzbcufq13_rvmr_gjz98xo",
"module": "todo",
"pid": "kzoxuadlnqrtxeg43xugw2s0voutnj",
"prev_id": "pcwsejrnwzuwjpyve64ww68hxxt74r"
},
{
"type": "file",
"name": "日常",
"icon": "",
"id": "gpvwcojxffgijtw14xat7-ealc7w8l",
"module": "todo",
"pid": "",
"prev_id": "kzoxuadlnqrtxeg43xugw2s0voutnj"
},
{
"type": "dir",
"name": "工作",
"icon": "",
"id": "kzoxuadlnqrtxeg43xugw2s0voutnj",
"module": "todo",
"pid": "",
"next_id": "gpvwcojxffgijtw14xat7-ealc7w8l"
},
{
"type": "file",
"name": "工作目录一",
"icon": "",
"id": "pcwsejrnwzuwjpyve64ww68hxxt74r",
"module": "todo",
"pid": "kzoxuadlnqrtxeg43xugw2s0voutnj",
"next_id": "kzoxuadlnqrtxeg43xugw2s0voutnj"
}
]
tree 数据和 tree_map 由下面 class 中的函数可计算出来:
class 的一部分:
import { get, flatMap, last, initial, cloneDeep, find } from 'lodash-es'
type RawNode = {
id: string
pid?: string
prev_id?: string
next_id?: string
[key: string]: any
}
type RawNodes = Array<RawNode>
type TreeItem = RawNode & { children?: Tree }
type Tree = Array<TreeItem>
type TreeMap = Record<string, TreeItem>
export default class Index {
tree = [] as Tree
public init(raw_nodes: RawNodes) {
const raw_tree_map = this.setRawMap(raw_nodes)
const { tree, tree_map } = this.getTree(raw_nodes, raw_tree_map)
console.log(tree)
this.tree = this.sortTree(tree, tree_map)
}
private setRawMap(raw_nodes: RawNodes) {
const tree_map = {} as TreeMap
raw_nodes.map((item) => {
tree_map[item.id] = item
})
return tree_map
}
private getTree(raw_nodes: RawNodes, tree_map: TreeMap) {
const tree = [] as Tree
raw_nodes.forEach((item) => {
if (item.pid) {
if (!tree_map[item.pid].children) {
tree_map[item.pid].children = []
}
if (!tree_map[item.pid]?.children?.length) {
tree_map[item.pid].children = [item]
} else {
tree_map[item.pid].children.push(item)
}
} else {
tree.push(item)
}
})
return { tree, tree_map }
}
private sortTree(tree: Tree, tree_map: TreeMap) {
const target_tree = [] as Tree
const start_node = find(tree, (item) => !item.prev_id)
if (!start_node) return []
let current = start_node.id
while (current) {
const item = tree_map[current]
if (item?.children?.length) {
// 这里报错( RangeError: Maximum call stack size exceeded )
// item.children = this.sortTree(item.children, tree_map)
}
target_tree.push(item)
current = item.next_id
}
return target_tree
}
}
正确的情况应输出数据为:
const tree = [
{
"type": "dir",
"name": "工作",
"icon": "",
"id": "kzoxuadlnqrtxeg43xugw2s0voutnj",
"module": "todo",
"pid": "",
"next_id": "gpvwcojxffgijtw14xat7-ealc7w8l",
"children": [
{
"type": "file",
"name": "工作目录一",
"icon": "",
"id": "pcwsejrnwzuwjpyve64ww68hxxt74r",
"module": "todo",
"pid": "kzoxuadlnqrtxeg43xugw2s0voutnj",
"next_id": "kzoxuadlnqrtxeg43xugw2s0voutnj"
},
{
"type": "file",
"name": "工作目录二",
"icon": "",
"id": "dgacbecjhzbcufq13_rvmr_gjz98xo",
"module": "todo",
"pid": "kzoxuadlnqrtxeg43xugw2s0voutnj",
"prev_id": "pcwsejrnwzuwjpyve64ww68hxxt74r"
},
]
},
{
"type": "file",
"name": "日常",
"icon": "",
"id": "gpvwcojxffgijtw14xat7-ealc7w8l",
"module": "todo",
"pid": "",
"prev_id": "kzoxuadlnqrtxeg43xugw2s0voutnj"
},
]
哪位大佬指点迷津,小弟 v 您 60+60 ,祝您 66 大顺!
1
sillydaddy 2023-11-23 23:10:04 +08:00
“工作目录一”的 next_id 不对,指向了父节点“工作”,所以在 sort 的时候死循环了。
|
2
matrixage OP @sillydaddy soga 原来是我 sb 了,insert 函数写的有问题,难怪一直死循环😭
|
3
matrixage OP @sillydaddy 您把微信发我一下 我明天验证了 给您发红包
|
4
matrixage OP 生成和操作双向链表树的 class 贴在下面,有类似场景的兄弟可以看看,还有很多优化空间(生成树时的时间复杂度比较高,getTree 和 sortTree 应该可以合并,无奈我太菜了)
import { get, flatMap, last, initial, cloneDeep, find } from 'lodash-es' import { makeAutoObservable, toJS } from 'mobx' type RawNode = { id: string pid?: string prev_id?: string next_id?: string [key: string]: any } type RawNodes = Array<RawNode> type TreeItem = RawNode & { children?: Tree } type Tree = Array<TreeItem> type TreeMap = Record<string, TreeItem> type ArgsMove = { active_parent_index: Array<number> over_parent_index: Array<number> droppable: boolean } type ArgsPlace = { type: 'push' | 'insert' active_item: RawNode over_item?: RawNode target_level: RawNodes over_index?: number } export default class Index { tree = [] as Tree constructor() { makeAutoObservable(this, null, { autoBind: true }) } public init(raw_nodes: RawNodes) { const raw_tree_map = this.setRawMap(raw_nodes) const { tree, tree_map } = this.getTree(raw_nodes, raw_tree_map) this.tree = this.sortTree(tree, tree_map) } public insert(item: RawNode, focusing_index?: Array<number>) { const { target_droppale, target_item: over_item } = this.getDroppableItem(focusing_index) const { active_item, effect_items } = this.place({ type: 'push', active_item: item, over_item, target_level: target_droppale }) return { item: active_item, effect_items } } public remove(focusing_index: Array<number>) { const { cloned_item, effect_items } = this.take(focusing_index) let remove_items = [] as Tree if (cloned_item?.children?.length) { remove_items = this.getherItems(cloned_item.children) } return { id: cloned_item.id, remove_items, effect_items } } public update(focusing_index: Array<number>, data: Omit<RawNode, 'id'>) { const { item, target_level, target_index } = this.getItem(focusing_index) const target = { ...item, ...data } target_level[target_index] = target return target } public move(args: ArgsMove) { const { active_parent_index, over_parent_index, droppable } = args const effect_items = [] as RawNodes const { cloned_item: active_item, effect_items: take_effect_items } = this.take(active_parent_index) const { cloned_item: over_item, target_level } = this.getItem(over_parent_index) effect_items.push(...take_effect_items) const { effect_items: place_effect_items } = this.place({ type: droppable ? 'push' : 'insert', active_item, over_item, target_level, over_index: last(over_parent_index) }) effect_items.push(...place_effect_items) return { effect_items } } public getItem(indexes: Array<number>) { let target_level = [] as Array<TreeItem> let target_index = 0 let target_item = null as TreeItem const target_indexes = this.getIndexes(indexes) const level_indexes = initial(target_indexes) target_index = last(indexes) target_item = get(this.tree, target_indexes) if (!level_indexes.length) { target_level = this.tree } else { target_level = get(this.tree, level_indexes) } return { item: target_item, cloned_item: toJS(target_item), target_level, target_index } } private getDroppableItem(indexes: Array<number>) { if (!indexes.length) return { target_droppale: this.tree, target_item: null } let target_item = null as TreeItem let target_indexes = [] as Array<number | string> if (indexes.length === 1) { target_indexes = indexes } else { target_indexes = this.getIndexes(indexes) } target_item = get(this.tree, target_indexes) if (!target_item.children) { target_item.children = [] } return { target_droppale: target_item.children, target_item } } private setRawMap(raw_nodes: RawNodes) { const tree_map = {} as TreeMap raw_nodes.map((item) => { tree_map[item.id] = item }) return tree_map } private getTree(raw_nodes: RawNodes, tree_map: TreeMap) { const tree = [] as Tree raw_nodes.forEach((item) => { if (item.pid) { if (!tree_map[item.pid].children) { tree_map[item.pid].children = [] } if (!tree_map[item.pid]?.children?.length) { tree_map[item.pid].children = [item] } else { tree_map[item.pid].children.push(item) } } else { tree.push(item) } }) return { tree, tree_map } } private sortTree(tree: Tree, tree_map: TreeMap) { const target_tree = [] as Tree const start_node = find(tree, (item) => !item.prev_id) if (!start_node) return [] let current = start_node.id while (current) { const item = tree_map[current] if (item?.children?.length) { item.children = this.sortTree(item.children, tree_map) } target_tree.push(item) current = item.next_id } return target_tree } private take(indexes: Array<number>) { const { cloned_item, target_level, target_index } = this.getItem(indexes) const effect_items = [] as Array<TreeItem> if (cloned_item.prev_id) { const prev_item = target_level[target_index - 1] prev_item.next_id = cloned_item.next_id ?? '' effect_items.push(prev_item) } if (cloned_item.next_id) { const next_item = target_level[target_index + 1] next_item.prev_id = cloned_item.prev_id ?? '' effect_items.push(next_item) } target_level.splice(target_index, 1) return { cloned_item, effect_items } } private place(args: ArgsPlace) { const { type, active_item, over_item, target_level, over_index } = args const effect_items = [] as RawNodes if (type === 'push') { active_item.pid = over_item ? over_item.id : '' if (target_level.length) { const last_item = last(target_level) last_item.next_id = active_item.id active_item.prev_id = last_item.id effect_items.push(last_item) } effect_items.push(active_item) target_level.push(active_item) } else { active_item.pid = over_item.pid if (over_item.next_id) { const next_item = target_level[over_index + 1] active_item.next_id = next_item.id next_item.prev_id = active_item.id effect_items.push(next_item) } active_item.prev_id = over_item.id over_item.next_id = active_item.id effect_items.push(active_item) target_level.splice(over_index, 0, active_item) } return { active_item, effect_items } } private getIndexes(indexes: Array<number>) { return flatMap(indexes, (value, index) => { return index < indexes.length - 1 ? [value, 'children'] : [value] }) } private getherItems(tree: Tree) { return tree.reduce((total, item) => { total.push(item) if (item?.children?.length) { total.push(...this.getherItems(item.children)) } return total }, [] as Tree) } } |
5
matrixage OP @sillydaddy 我的 v 信 Mrhehero ,你这个提醒节省了我半天的时间,应得 120
|
6
aguesuka 2023-11-24 13:51:46 +08:00
没测过,不过思路应该没问题
type Tree = Array<TreeItem> type RawNode = { id: string pid?: string prev_id?: string next_id?: string [key: string]: any } interface LinkedNode<E> { node: E, firstChild?: LinkedNode<E> nextNode?: LinkedNode<E> } function toTree<E, K, T>(elements: E[], getId: (element: E) => K, getParentId: (element: E) => K | undefined, getPrevId: (element: E) => K | undefined, createTreeNode: (element: E) => T, appendChild: (parent: T, child: T) => void): T[] { const linkedNodes: Map<K, LinkedNode<T>> = new Map(); elements.forEach(element => linkedNodes.set(getId(element), {node: createTreeNode(element)})); const rootLinkedNode: LinkedNode<T>[] = [] for (let element of elements) { const parentId = getParentId(element); const id = getId(element) const linkedNode = linkedNodes.get(id)! if (parentId) { const prevId = getPrevId(element) if (prevId) { const pervLinkedNode = linkedNodes.get(prevId); console.assert(!!pervLinkedNode, `${prevId} is not found`) pervLinkedNode!.nextNode = linkedNode } else { const parentLinkedNode = linkedNodes.get(parentId); console.assert(!!parentLinkedNode, `${parentId} is not found`) parentLinkedNode!.firstChild = linkedNode } } else { rootLinkedNode.push(linkedNode) } } for (let linkedNode of linkedNodes.values()) { for (let child = linkedNode.firstChild; child; child = child.nextNode) { appendChild(linkedNode.node, child.node) } } return rootLinkedNode.map(linkedNode => linkedNode.node) } function test(){ const raw_nodes = [/**/] const rootNodes :Tree = toTree<RawNode, string, RawNode>(raw_nodes, node => node.id, node => node.pid, node => node.prev_id, node => { node.children = []; return node; }, (parent, child) => parent.children.push(child) ) console.info(rootNodes) } |
7
matrixage OP @aguesuka 👌 我明天测试一下
下面是我整了一周的带父子节点的双向链表的 class NodeTree ,这种数据结构和数据处理方法在现实很多场景中都有用,比如 Tree ,就是典型双向链表场景,但由于考虑到存储问题,又不能直接存储 Tree 的树形数据(富文本、流程图、等包含图计算的场景)都需要 NodeTree 提供支持,下面是通过了测试的完整实现(上面我发的有 bug ): import { get, flatMap, last, initial, find, reduceRight, flatten } from 'lodash-es' import { makeAutoObservable, toJS } from 'mobx' type RawNode = { id: string pid?: string prev_id?: string next_id?: string [key: string]: any } type RawNodes = Array<RawNode> type TreeItem = RawNode & { children?: Tree } type Tree = Array<TreeItem> type TreeMap = Record<string, TreeItem> type ArgsMove = { active_parent_index: Array<number> over_parent_index: Array<number> droppable: boolean } type ArgsPlace = { type: 'push' | 'insert' active_item: RawNode over_item?: RawNode target_level: RawNodes over_index?: number } export default class Index { tree = [] as Tree constructor() { makeAutoObservable(this, null, { autoBind: true }) } public init(raw_nodes: RawNodes) { const raw_tree_map = this.setRawMap(raw_nodes) const { tree, tree_map } = this.getTree(raw_nodes, raw_tree_map) this.tree = this.sortTree(tree, tree_map) } public insert(item: RawNode, focusing_index?: Array<number>) { const { target_level, cloned_item: over_item } = this.getDroppableItem(focusing_index) const { active_item, effect_items } = this.place({ type: 'push', active_item: item, over_item, target_level }) return { item: active_item, effect_items } } public remove(focusing_index: Array<number>) { const { cloned_item, effect_items } = this.take(focusing_index) let remove_items = [] as Tree if (cloned_item?.children?.length) { remove_items = this.getherItems(cloned_item.children) } return { id: cloned_item.id, remove_items, effect_items } } public update(focusing_index: Array<number>, data: Omit<RawNode, 'id'>) { const { item, target_level, target_index } = this.getItem(focusing_index) const target = { ...item, ...data } target_level[target_index] = target return target } public move(args: ArgsMove) { const { active_parent_index, over_parent_index, droppable } = args const effect_items = [] as RawNodes const { cloned_item: active_item } = this.getItem(active_parent_index) const { cloned_item: over_item, target_level } = droppable ? this.getDroppableItem(over_parent_index) : this.getItem(over_parent_index) if (over_item.next_id === active_item.id && !droppable) { return { effect_items } } const swap = active_item.next_id === over_item.id && !droppable let execs = [] const place = () => { const { effect_items } = this.place({ type: droppable ? 'push' : 'insert', active_item, over_item, target_level, over_index: last(over_parent_index) }) return effect_items } const take = () => { const { effect_items } = this.take(active_parent_index, swap) return effect_items } if (active_item.pid === over_item.pid) { if (last(active_parent_index) < last(over_parent_index)) { execs = [place, take] } else { execs = [take, place] } } else { if (active_parent_index.length > over_parent_index.length) { execs = [take, place] } else { execs = [place, take] } } const all_effect_items = flatten(execs.map((func) => func())) return { effect_items: this.getUniqEffectItems(all_effect_items) } } public getItem(indexes: Array<number>) { let target_level = [] as Array<TreeItem> let target_index = 0 let target_item = null as TreeItem const target_indexes = this.getIndexes(indexes) const level_indexes = initial(target_indexes) target_index = last(indexes) target_item = get(this.tree, target_indexes) if (!level_indexes.length) { target_level = this.tree } else { target_level = get(this.tree, level_indexes) } return { item: target_item, cloned_item: toJS(target_item), target_level, target_index } } private getDroppableItem(indexes: Array<number>) { if (!indexes.length) return { target_level: this.tree, cloned_item: null } let target_item = null as TreeItem let target_indexes = [] as Array<number | string> if (indexes.length === 1) { target_indexes = indexes } else { target_indexes = this.getIndexes(indexes) } target_item = get(this.tree, target_indexes) if (!target_item.children) { target_item.children = [] } return { target_level: target_item.children, cloned_item: toJS(target_item) } } private setRawMap(raw_nodes: RawNodes) { const tree_map = {} as TreeMap raw_nodes.map((item) => { tree_map[item.id] = item }) return tree_map } private getTree(raw_nodes: RawNodes, tree_map: TreeMap) { const tree = [] as Tree raw_nodes.forEach((item) => { if (item.pid) { if (!tree_map[item.pid].children) { tree_map[item.pid].children = [] } if (!tree_map[item.pid]?.children?.length) { tree_map[item.pid].children = [item] } else { tree_map[item.pid].children.push(item) } } else { tree.push(item) } }) return { tree, tree_map } } private sortTree(tree: Tree, tree_map: TreeMap) { const target_tree = [] as Tree const start_node = find(tree, (item) => !item.prev_id) if (!start_node) return [] let current = start_node.id while (current) { const item = tree_map[current] if (item?.children?.length) { item.children = this.sortTree(item.children, tree_map) } target_tree.push(item) current = item.next_id } return target_tree } private take(indexes: Array<number>, swap?: boolean) { const { cloned_item, target_level, target_index } = this.getItem(indexes) const effect_items = [] as Array<TreeItem> if (cloned_item.prev_id) { const prev_item = target_level[target_index - 1] prev_item.next_id = cloned_item.next_id ?? '' effect_items.push(toJS(prev_item)) } if (cloned_item.next_id) { const next_item = target_level[target_index + 1] next_item.prev_id = cloned_item.prev_id ?? '' if (swap) next_item.next_id = cloned_item.id effect_items.push(toJS(next_item)) } target_level.splice(target_index, 1) return { cloned_item, effect_items } } private place(args: ArgsPlace) { const { type, active_item, over_item, target_level, over_index } = args const effect_items = [] as RawNodes if (type === 'push') { active_item.pid = over_item ? over_item.id : '' if (target_level.length) { const last_item = last(target_level) last_item.next_id = active_item.id active_item.prev_id = last_item.id effect_items.push(toJS(last_item)) } else { active_item.prev_id = undefined } active_item.next_id = undefined effect_items.push(toJS(active_item)) target_level.push(active_item) } else { active_item.pid = over_item.pid active_item.prev_id = over_item.id active_item.next_id = over_item.next_id if (over_item.next_id) { const next_item = target_level[over_index + 1] next_item.prev_id = active_item.id effect_items.push(toJS(next_item)) } else { active_item.next_id = undefined } if (active_item.next_id === over_item.id) { over_item.next_id = active_item.next_id } else { over_item.next_id = active_item.id } effect_items.push(toJS(active_item)) effect_items.push(toJS(over_item)) target_level.splice(over_index + 1, 0, active_item) } return { active_item, effect_items } } private getUniqEffectItems(effect_items: Tree) { return reduceRight( effect_items, (acc, curr) => { if (!acc.some((item) => item['id'] === curr['id'])) { acc.unshift(curr) } return acc }, [] as Tree ) } private getIndexes(indexes: Array<number>) { return flatMap(indexes, (value, index) => { return index < indexes.length - 1 ? [value, 'children'] : [value] }) } private getherItems(tree: Tree) { return tree.reduce((total, item) => { total.push(item) if (item?.children?.length) { total.push(...this.getherItems(item.children)) } return total }, [] as Tree) } } |