知识卡片
空根分支不能覆盖定位结果
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