V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
matrixage
V2EX  ›  程序员

[付费问答] 在写一个富文本编辑器,其中用到了带父子节点的双向链表,可无限嵌套,写了个递归一直报错,希望大佬指点指点,答案被采纳我 v 信转 120 给您(不在乎钱的也可以试一试,这十分考验算法实战能力)

  •  
  •   matrixage ·
    matrixage · 350 天前 · 1401 次点击
    这是一个创建于 350 天前的主题,其中的信息可能已经有所发展或是发生改变。

    在写一个富文本编辑器,其中用到了带父子节点的双向链表,要把无顺序的节点树根据 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 大顺!

    7 条回复    2023-11-24 20:58:13 +08:00
    sillydaddy
        1
    sillydaddy  
       350 天前
    “工作目录一”的 next_id 不对,指向了父节点“工作”,所以在 sort 的时候死循环了。
    matrixage
        2
    matrixage  
    OP
       350 天前 via Android
    @sillydaddy soga 原来是我 sb 了,insert 函数写的有问题,难怪一直死循环😭
    matrixage
        3
    matrixage  
    OP
       350 天前 via Android
    @sillydaddy 您把微信发我一下 我明天验证了 给您发红包
    matrixage
        4
    matrixage  
    OP
       350 天前
    生成和操作双向链表树的 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)
    }
    }
    matrixage
        5
    matrixage  
    OP
       350 天前
    @sillydaddy 我的 v 信 Mrhehero ,你这个提醒节省了我半天的时间,应得 120
    aguesuka
        6
    aguesuka  
       350 天前
    没测过,不过思路应该没问题

    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)
    }
    matrixage
        7
    matrixage  
    OP
       349 天前
    @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)
    }
    }
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2749 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 12:41 · PVG 20:41 · LAX 04:41 · JFK 07:41
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.