知识卡片

操作参考卡 · 5654.d.1.e.4.g · 生成模型:未记录

删除子树要先清理孩子

理解等级:中级

bitree_rem_left(BiTree,BiTreeNode)意图移除指定节点的整棵左子树,右侧版本对应右子树;node=NULL按接口表示从根移除全部。它们不是只删一个节点并自动把其孩子提升。

正确后序清理应先递归删除左右孩子,再按非空destroy清理当前数据、free当前节点、把父方链接置NULL并减size。先释放父节点会丢掉通往孩子的链接或使后续读取失效。固定回调成本下移除k节点为O(k),递归栈还受子树高度影响。

这是设计意图;本书实际代码的NULL分支漏else会破坏这一接口,另见[[空根分支不能覆盖定位结果]],不能将原源码直接当已正确实现。

153及02858在有效position路径中先rem_left/rem_right清孩子,再destroy(data)、free(*position)、置NULL、size–。意图与实际NULL错误须并列解释,不能以后序步骤正确掩盖前置定位失效。

168后序删除让孩子先于父亲清理,在本章依赖父节点链接寻访孩子的实现中必要。若设计先保存链接等其他策略可另论,不能把此说明泛化成任何程序都绝不能用其他遍历组织释放。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 3 处

    • · 查看原书依据

      bitree_rem_left 返回值 无 描述 移除由tree指定的二叉树中node的左子结点为根的子树。如果node为NULL,则移除树中的所有结点。若传递给bitree_init的参数destroy不为NULL,则移除结点时将调用由destroy所指定的函数。 复杂度 O(n),这里n代表子树

    • · 查看原书依据

      按照后序遍历从参数node的左子结点开始依次移除。如果node为NULL,就从树的根结点开始。当destroy不为NULL时,每次移除结点时都要调用destroy所指向的函数完成相应的资源回收工作。每移除一个结点,都要更新数据结构中的size成员。 bitree_rem_left的时间复杂度为O(n

    • · 查看原书依据

      后序遍历的方式来移除恰当的子树?可以采用前序或者中序遍历代替吗? 答:这里必须采用后序遍历。因为子树必须在移除其父结点之前就全部移除。前序遍历需要先将父结点移除,而移除了父结点就无法再访问其子结点了。中序遍历也没办法做到,因为我们仍然会在移除右子树之前先移除父结点,这使得右子树再也无法访问到了。 问

    参考来源

    - 位置:《算法精解:C语言描述》第9章《二叉树的接口定义》(spine1287;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1254.html;u147-ch09-008)。 - 结论依据:147移除两接口与153/154正文、02858–02859递归后序清理代码全部实读,定位NULL缺陷另独立记录,不掩盖正常设计与实际错误差异。 - 原始内容:bitree_rem_left 返回值 无 描述 移除由tree指定的二叉树中node的左子结点为根的子树。如果node为NULL,则移除树中的所有结点。若传递给bitree_init的参数destroy不为NULL,则移除结点时将调用由destroy所指定的函数。 复杂度 O(n),这里n代表子树 - 位置:《算法精解:C语言描述》第9章《bitree_rem_left》(spine1292;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1259.html;u153-ch09-008)。 - 结论依据:153及02858在有效position路径中先rem_left/rem_right清孩子,再destroy(data)、free(*position)、置NULL、size--。意图与实际NULL错误须并列解释,不能以后序步骤正确掩盖前置定位失效。 - 原始内容:按照后序遍历从参数node的左子结点开始依次移除。如果node为NULL,就从树的根结点开始。当destroy不为NULL时,每次移除结点时都要调用destroy所指向的函数完成相应的资源回收工作。每移除一个结点,都要更新数据结构中的size成员。 bitree_rem_left的时间复杂度为O(n - 位置:《算法精解:C语言描述》第9章《问与答》(spine1306;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1273.html;u168-ch09-008)。 - 结论依据:168后序删除让孩子先于父亲清理,在本章依赖父节点链接寻访孩子的实现中必要。若设计先保存链接等其他策略可另论,不能把此说明泛化成任何程序都绝不能用其他遍历组织释放。 - 原始内容:后序遍历的方式来移除恰当的子树?可以采用前序或者中序遍历代替吗? 答:这里必须采用后序遍历。因为子树必须在移除其父结点之前就全部移除。前序遍历需要先将父结点移除,而移除了父结点就无法再访问其子结点了。中序遍历也没办法做到,因为我们仍然会在移除右子树之前先移除父结点,这使得右子树再也无法访问到了。 问