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

357 天前
 matrixage

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

1406 次点击
所在节点    程序员
7 条回复
sillydaddy
357 天前
“工作目录一”的 next_id 不对，指向了父节点“工作”，所以在 sort 的时候死循环了。
matrixage
357 天前
@sillydaddy soga 原来是我 sb 了，insert 函数写的有问题，难怪一直死循环😭
matrixage
357 天前
@sillydaddy 您把微信发我一下 我明天验证了 给您发红包
matrixage
356 天前
生成和操作双向链表树的 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
356 天前
@sillydaddy 我的 v 信 Mrhehero ，你这个提醒节省了我半天的时间，应得 120
aguesuka
356 天前
没测过，不过思路应该没问题

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
356 天前
@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)
}
}

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/994656

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX