知识卡片

问题卡 · 5654.d.1.e.4.j · 生成模型:未记录

空根分支不能覆盖定位结果

理解等级:中级

bitree_rem_left接口允许node=NULL表示移除整树,但完整源码在if(node==NULL)后设置position=&tree->root,紧接着又无条件设置position=&node->left,漏了else。非空树的销毁会传NULL走这一路,结果试图通过NULL访问成员。

右侧bitree_rem_right也同样漏else,下一句无条件取&node->right。仅凭前面有NULL分支不能断言空根路径已被正确处理;要检查分支之后是否仍执行了不适用的语句。

此示例的修正逻辑是二选一:node为NULL就定位根,否则定位指定孩子,再对该位置进行后序清理。这里记录两处源码缺陷和修正方向,未修改或测试C实现;不能把原bitree_destroy当可安全复用模板。

154及02858–02859 right函数与left同样在设置根position后又无条件设置&node->right;不是换了孩子方向就免除NULL问题。两函数都应将根与非根定位写成互斥分支。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

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

    • · 查看原书依据

      右子结点为根的子树移除(见示例9-2)。该操作的工作方式同bitree_rem_left很相似,除了移除的是以node结点的右子结点为根的子树。 bitree_rem_right的时间复杂度为O(n),这里n代表以结点node的右子结点为根结点的子树中的结点个数。这是因为bitree_rem_rig

    参考来源

    - 位置:《算法精解:C语言描述》第9章《bitree_rem_left》(spine1292;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1259.html;u153-ch09-011)。 - 结论依据:153的NULL根说明与02858完整rem_left,以及02858–02859 rem_right实际代码逐行实读,明确两处均缺else;02856 destroy传NULL证实影响路径。 - 原始内容:如果node为NULL,就从树的根结点开始。当destroy不为NULL时,每次移除结点时都要调用destroy所指向的函数完成相应的资源回收工作。每移除一个结点,都要更新数据结构中的size成员。 bitree_rem_left的时间复杂度为O(n),这里n代表以结点node的左子结点为根结点的子 - 位置:《算法精解:C语言描述》第9章《bitree_rem_right》(spine1293;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1260.html;u154-ch09-011)。 - 结论依据:154及02858–02859 right函数与left同样在设置根position后又无条件设置&node->right;不是换了孩子方向就免除NULL问题。两函数都应将根与非根定位写成互斥分支。 - 原始内容:右子结点为根的子树移除(见示例9-2)。该操作的工作方式同bitree_rem_left很相似,除了移除的是以node结点的右子结点为根的子树。 bitree_rem_right的时间复杂度为O(n),这里n代表以结点node的右子结点为根结点的子树中的结点个数。这是因为bitree_rem_rig