Tarzan jim John Tom Lucy Cynthia Jane 3 Jim John Tom 2 Tarzan lucy 2 Jane Cynthia 2 Jim jane 2 Tarzan jim 2 Tarzan jane 试题4“树”在计算机科学中是一种非常重要的数据结构。它的应用极为广泛,从计算机图形学中 的空间层次剖分到人工智能中的状态搜索都离不开它。二叉树是一种特殊的树,它的每个节点最多只 有左、右两个子树,如图1所示。 8 11 图 我们用二元组(n,s)来表示二叉树中的任意节点。其中n代表该节点的值,s代表从根节点到该节点 的路径字符串,字符串中只包含'L和R'两种字符,分别指“左子树”和“右子树”。图1中值为13 的节点用(13RL)表示,值为2的节点用(2,LLR)表示;根节点用(5)表示,空路径字符串表示它是根节 点。如果每个节点到根节点的路径上都没有缺少节点,而且每个节点只被赋值一次,则称这样的二叉 树是“完备描述”的。本题目要求你判断给定二叉树是否是“完备描述”的,如果是,输出其节点值 的按层次遍历序列(即先上层后下层、从左至右地遍历)。图1中的二叉树,其节点值的按层次遍历序 列为:5,4,8,11,13,4,7,2,1 输入:输入文件中包含多个二叉树的节点序列,每个节点用上述(ns)形式描述,节点值都是正整数 节点之间以空格分隔,节点内部没有空格。每个二叉树至少包含一个节点,树的结尾处以两个英文括 号字符“(”标记,括号之内没有空格。 输出:针对输入文件中的每个二叉树,分别输出其对应的信息。对于完备描述的二叉树,输出其节点 值的按层次遍历序列。每个二叉树的遍历序列值占据一行,且值与值之间用空格分隔。对于不完备描 述的二又树,则在新的一行中输出字符串“ not completeTarzan Jim John Tom Lucy Cynthia Jane 3 Jim John Tom 2 Tarzan Lucy 2 Jane Cynthia 2 Jim Jane 2 Tarzan Jim 2 Tarzan Jane 试题 4 “树”在计算机科学中是一种非常重要的数据结构。它的应用极为广泛，从计算机图形学中 的空间层次剖分到人工智能中的状态搜索都离不开它。二叉树是一种特殊的树，它的每个节点最多只 有左、右两个子树，如图 1 所示。 图 1 我们用二元组(n,s)来表示二叉树中的任意节点。其中 n 代表该节点的值，s 代表从根节点到该节点 的路径字符串，字符串中只包含’L’和’R’两种字符，分别指“左子树”和“右子树”。图 1 中值为 13 的节点用(13,RL)表示，值为 2 的节点用(2, LLR)表示；根节点用(5,)表示，空路径字符串表示它是根节 点。如果每个节点到根节点的路径上都没有缺少节点，而且每个节点只被赋值一次，则称这样的二叉 树是“完备描述”的。本题目要求你判断给定二叉树是否是“完备描述”的，如果是，输出其节点值 的按层次遍历序列（即先上层后下层、从左至右地遍历）。图 1 中的二叉树，其节点值的按层次遍历序 列为：5, 4, 8, 11, 13, 4, 7, 2, 1。 输入：输入文件中包含多个二叉树的节点序列，每个节点用上述(n,s)形式描述，节点值都是正整数。 节点之间以空格分隔，节点内部没有空格。每个二叉树至少包含一个节点，树的结尾处以两个英文括 号字符“()”标记，括号之内没有空格。 输出：针对输入文件中的每个二叉树，分别输出其对应的信息。对于完备描述的二叉树，输出其节点 值的按层次遍历序列。每个二叉树的遍历序列值占据一行，且值与值之间用空格分隔。对于不完备描 述的二叉树，则在新的一行中输出字符串“not complete