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

知识卡片

普通读书笔记卡 · 2615.c

儿子兄弟表示法

理解等级:未标注

多叉树除了“父节点加儿子列表”,还可以用“第一个儿子加下一个兄弟”两个指针表示,把任意多叉树变成类似二叉的链式结构。书中主体用前一种存储,但模拟了后一种的查询属性,并演示其遍历:先找儿子,没有就找兄弟,再没有就沿祖先回溯找其右兄弟,直到根。换一种表示,遍历成本和实现复杂度随之改变。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:《TypeScript图形渲染实战:2D架构设计与实现》第9章《优美典雅的树结构》(源文件:_epub-src/OEBPS/Text/000244.xhtml) - 结论依据:原文说明本书树结构使用“父节点+儿子列表”存储,但为说明“父节点+儿子兄弟”方式的遍历流程,在TreeNode中模拟了相关只读属性,并给出沿儿子、兄弟和祖先右兄弟回溯的遍历规则。 - 原始内容:本书仅使用父亲节点+儿子列表的存储方式(TreeNode<T>类),但是为了让大家了解父亲节点+儿子兄弟存储方式的遍历流程,在TreeNode<T>类中模拟实现了如下四个只读查询属性