返回主题:内置数据结构的底层实现

知识卡片

普通读书笔记卡 · 2615

树避免环引用

理解等级:未标注

给树节点添加子节点时,若把它的祖先挂到它下面,树就变成了环,遍历会陷入死循环甚至让程序崩溃。所以添加前必须检查:要加入的节点是否已是当前节点的祖先,书中为此专门实现了判断方法。层级模型要在写入关系时就守住不变量,等遍历、删除或序列化时才发现环,修复代价高得多。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:《TypeScript图形渲染实战:2D架构设计与实现》第9章《优美典雅的树结构》(源文件:_epub-src/OEBPS/Text/000233.xhtml) - 结论依据:原文说明若把已是祖先的节点再添加为子节点会导致循环引用、程序崩溃,因此添加子节点时必须检查其是否为当前节点的祖先,为此实现isDescendantOf方法。 - 原始内容:因此在为某个节点添加子节点时,必须检查要添加的子节点是否是当前节点的祖先节点。