知识卡片
儿子兄弟表示法
多叉树除了“父节点加儿子列表”,还可以用“第一个儿子加下一个兄弟”两个指针表示,把任意多叉树变成类似二叉的链式结构。书中主体用前一种存储,但模拟了后一种的查询属性,并演示其遍历:先找儿子,没有就找兄弟,再没有就沿祖先回溯找其右兄弟,直到根。换一种表示,遍历成本和实现复杂度随之改变。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《TypeScript图形渲染实战:2D架构设计与实现》第9章《优美典雅的树结构》(源文件:_epub-src/OEBPS/Text/000244.xhtml)
- 结论依据:原文说明本书树结构使用“父节点+儿子列表”存储,但为说明“父节点+儿子兄弟”方式的遍历流程,在TreeNode中模拟了相关只读属性,并给出沿儿子、兄弟和祖先右兄弟回溯的遍历规则。
- 原始内容:本书仅使用父亲节点+儿子列表的存储方式(TreeNode<T>类),但是为了让大家了解父亲节点+儿子兄弟存储方式的遍历流程,在TreeNode<T>类中模拟实现了如下四个只读查询属性