知识卡片
删除子树要先清理孩子
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 条
还没有人提交反馈。
在整书笔记中的位置
- · 删除子树要先清理孩子
- · bitree_rem_left
- · 问与答
原书出处 · 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
- · 查看原书依据
后序遍历的方式来移除恰当的子树?可以采用前序或者中序遍历代替吗? 答:这里必须采用后序遍历。因为子树必须在移除其父结点之前就全部移除。前序遍历需要先将父结点移除,而移除了父结点就无法再访问其子结点了。中序遍历也没办法做到,因为我们仍然会在移除右子树之前先移除父结点,这使得右子树再也无法访问到了。 问