生成所有有根有序树All Rooted Ordered Trees故事文件090解构有根有序树5W1H维度说明What是什么有根有序树Rooted Ordered Trees又称平面树 Plane Trees是每个节点的子节点有固定顺序的有根树。n 个节点的有根有序树共有 C(n-1) 棵第 n-1 个 Catalan 数。Why为什么有根有序树是组合数学中的基础 Catalan 对象与二叉树、Dyck 路径、括弧序列等有一一对应关系。枚举有根有序树是理解 Catalan 数与树结构枚举的核心练习。Who谁理论来源Donald Knuth《The Art of Computer Programming》第四卷 Fascicle 4 第 7.2.1.6 节。When何时需要枚举所有可能的树形结构时如解析树、表达式树、语法树的枚举有根有序树是自然的选择。Where在哪里应用于编译器设计解析树枚举、组合数学Catalan 数的组合证明、算法测试生成所有树形测试用例。How如何通过 left-child-right-siblingLCRS对应关系将 n 个节点的有根有序树与 (n-1) 步 Dyck 路径一一对应复用 Dyck 路径枚举算法与 all_binary_trees.c 相同括弧序列表示在 Dyck 路径对应的括弧串外层加一对括弧。需求定义功能需求catalan(n)计算第 n 个 Catalan 数递推公式不使用浮点运算。next_dyck(path, n)就地生成下一个字典序 Dyck 路径返回是否成功。dyck_to_rooted_tree_parens(path, len, buf)将 Dyck 路径转换为有根有序树的括弧序列在外层加一对括弧。gen_all_rooted_trees(n)生成并打印 n 个节点的所有有根有序树n≤5 时打印返回树的数量。validate_rooted_tree_parens(s)验证括弧序列合法性并返回节点数用于测试。非功能需求不使用math.h或-lm。C99 标准gcc -stdc99 -Wall编译无警告无错误。括弧序列缓冲区大小为2n 1n 个节点对应 2n 个括弧。Dyck 路径前缀数组最大支持 n255popen/pclose长度 512。验收标准编号测试描述期望结果TC-01gen_all_rooted_trees(1)的返回值1 棵C(0)1TC-02gen_all_rooted_trees(2)的返回值1 棵C(1)1TC-03gen_all_rooted_trees(3)的返回值2 棵C(2)2TC-04gen_all_rooted_trees(4)的返回值5 棵C(3)5TC-05gen_all_rooted_trees(5)的返回值14 棵C(4)14TC-06n1…6 枚举数量与catalan(n-1)一致全部匹配TC-07n3 的两棵树括弧序列格式正确各含 3 个节点格式合法TC-08n3 的两棵树括弧序列具体值((()))和(()())关键设计说明与 all_binary_trees.c 的区别all_binary_trees.c n 个内部节点的满二叉树每个节点有 0 或 2 个子节点 括弧序列长度2n 对应 Dyck 路径n 步 数量C(n) all_rooted_trees.c n 个节点的有根有序树每个节点可有任意个子节点 括弧序列长度2n 对应 Dyck 路径n-1 步去掉根节点后对应 n-1 节点的二叉树 数量C(n-1)两者都是 Catalan 数但偏移量不同有根有序树用 C(n-1) 而不是 C(n)。LCRS 对应关系left-child-right-sibling左孩子右兄弟转换将有根有序树转为二叉树有根有序树n 节点 -- (n-1) 节点的二叉树 根节点对应空二叉树中消失 每个非根节点的第一个子节点对应二叉树的左孩子 每个节点的右兄弟对应二叉树的右孩子因此 n 个节点的有根有序树与 (n-1) 步 Dyck 路径一一对应数量为 C(n-1)。括弧序列与 Dyck 路径的对应有根有序树括弧序列 ( Dyck(n-1) 对应的括弧串 )示例n3Dyck(2) 的两条路径Dyck 路径 00 11 - 括弧 (()) - 有根有序树 ((())) 根-子节点-孙节点链式三节点树 Dyck 路径 01 01 - 括弧 ()() - 有根有序树 (()()) 根有两个叶子子节点Catalan 数验证n节点数C(n-1)树的数量1C(0) 112C(1) 113C(2) 224C(3) 555C(4) 14146C(5) 4242