知识卡片
递归遍历须进入存在的子树
递归树遍历应在节点存在时处理它,并递归访问存在的左右子树。若先检查孩子,只应在孩子非NULL时递归;或者允许递归函数收到NULL后立即结束,两种写法都要保持条件一致。
本书02862–02863三函数外层用!bitree_is_eob(node)正确检查当前节点,但六处孩子判断都写成if(bitree_is_eob(child)),反而只向NULL孩子递归,跳过真实子树。按实际宏“is_eob等于node==NULL”理解,非空输入基本只把当前根的数据追加到list,而不是完成所述遍历。
要落实原意,可把这些孩子条件改为非空判断,或去掉孩子条件让递归入口统一处理NULL;然后根数据插入的位置才分别决定先、中、后序。此处记录源码缺陷与修正逻辑,未编译或测试修复,不把原代码当正确输出依据。
261/03025的build_table外层使用if(bitree_is_eob(node)),即只在空结点时进入;正常非空根反而不构码。左右递归同样用空子结点条件,若进入还会读取空结点。须区分空结点终止与非空子结点继续,不能把源码反向条件当正确实现。叶子赋值实际是table[symbol].code=htons(code)、.size=size;不把这两个字段误读为同一赋值。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
preorder、inorder、postorder。它们分别采用前序、中序、后序的方式来遍历表达式树。每个函数都接受两个参数:node和list。 开始遍历时,将参数node设置为希望进行遍历的表达式树的根结点。连续的递归调用会将node设置为将要遍历的子树的根结点。初次每个函数调用时,还会把一个
- · 查看原书依据
示例14-3)解压缩由huffman_compress压缩的数据。首先,此操作读取追加到压缩数据的头。回想一下,头的前4个字节包含编码符号的数量。这个值存放在size中。接下来的256个字节包含所有符号的缩放频率。 利用存放在头中的信息,调用build_tree重建压缩过程中用到的霍夫曼树。一旦重建