知识卡片

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

递归遍历须进入存在的子树

理解等级:中级

递归树遍历应在节点存在时处理它,并递归访问存在的左右子树。若先检查孩子,只应在孩子非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重建压缩过程中用到的霍夫曼树。一旦重建

    参考来源

    - 位置:《算法精解:C语言描述》第9章《二叉树示例:表达式处理》(spine1296;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1263.html;u157-ch09-015)。 - 结论依据:157递归说明、02862–02863完整三个函数和已读02854宏逐项对照,六个孩子条件缺否定与当前入口有否定直接可见;未运行。 - 原始内容:preorder、inorder、postorder。它们分别采用前序、中序、后序的方式来遍历表达式树。每个函数都接受两个参数:node和list。 开始遍历时,将参数node设置为希望进行遍历的表达式树的根结点。连续的递归调用会将node设置为将要遍历的子树的根结点。初次每个函数调用时,还会把一个 - 位置:《算法精解:C语言描述》第14章《huffman_uncompress》(spine1386;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1352.html;u261-ch09-015)。 - 结论依据:261/03025的build_table外层使用if(bitree_is_eob(node)),即只在空结点时进入;正常非空根反而不构码。左右递归同样用空子结点条件,若进入还会读取空结点。须区分空结点终止与非空子结点继续,不能把源码反向条件当正确实现。叶子赋值实际是table[symbol].code=htons(code)、.size=size;不把这两个字段误读为同一赋值。 - 原始内容:示例14-3)解压缩由huffman_compress压缩的数据。首先,此操作读取追加到压缩数据的头。回想一下,头的前4个字节包含编码符号的数量。这个值存放在size中。接下来的256个字节包含所有符号的缩放频率。 利用存放在头中的信息,调用build_tree重建压缩过程中用到的霍夫曼树。一旦重建