知识卡片

普通读书笔记卡 · 5654.d.1.a.1.e

树的数组位置要保留空洞

理解等级:中级

按完全树的位置编号,索引i的左右孩子分别在2i+1和2i+2,非根节点的父位置由(i-1)/2得到。位置映射相当于隐式链接,可免去每节点指针。

任意树若直接省掉中间空位,原索引关系就会失效;应保留位置空洞或采用其他明确序列化规则。完全树的空位置只在末尾,适合紧凑数组;稀疏深树却可能浪费大量槽位。原书parent对根不应直接当合法父节点使用。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      映射公式的角色相当于链表中的指针 。给定数组中的任意一个节点,我们都可以通过映射公式来访问它的左 (右)子节点。 7.3.2 表示任意二叉树 完美二叉树是一个特例,在二叉树的中间层通常存在许多None 。由于层序遍历序列

    参考来源

    - 位置:《Hello 算法--Go版本》第07章《树》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/4.html;spine 3,归一字符[782,892)) - 结论依据:实际数组代码/任意树图及完全树无中间空洞解释,补充根边界。 - 原始内容:映射公式的角色相当于链表中的指针 。给定数组中的任意一个节点,我们都可以通过映射公式来访问它的左 (右)子节点。 7.3.2 表示任意二叉树 完美二叉树是一个特例,在二叉树的中间层通常存在许多None 。由于层序遍历序列