2017年（408）计算机学科专业基础综合试题 - 第41题回答
（1）采用递归方式实现二叉树的中序遍历，在每次递归调用时，若子树不为空，则先加上左括号，若左右子树均为空，即递归返回时，加上右括号，采用一个high值表示树高，当high值为1时，位于根节点，此时调用不加左右括号
（2）
初始化树;
int high=1;
void LNR(BTree* tree,int high)
{
if(high!=1)cout<<"(";//进行调用时，先加左括号，根节点调用不加括号
if(tree->left!=NULL) LNR(tree->left,high+1);
cout<<tree->data;//输出节点
if(tree->right!=NULL)LNR(tree->right,high+1);
if(high!=1)cout<<")";//调用完毕后，添加右括号，根节点调用同样不添加括号
}
评分及理由
（1）得分及理由（满分5分）
得分：3分
理由：学生基本理解了中序遍历的思路，并提到了通过括号反映计算次序，使用high参数控制括号添加。但是设计思想描述不够准确：
- 提到"若子树不为空，则先加上左括号" - 这不够精确，应该是当深度大于1（非根节点）时才需要加括号
- 提到"若左右子树均为空，即递归返回时，加上右括号" - 这个描述有误，右括号的添加应该与左括号对应，而不是在递归返回时
- 没有明确说明叶结点（操作数）不需要括号的处理
（2）得分及理由（满分10分）
得分：6分
理由：代码实现存在以下逻辑错误：
- 在进入递归前就添加左括号，这是错误的，应该在递归调用左右子树之前添加左括号
- 没有处理叶结点（操作数）的特殊情况，对操作数也会添加不必要的括号
- 括号的添加位置不正确，导致生成的表达式括号匹配错误
- 没有对空树进行判断
- 代码使用了C++的cout但函数声明是C风格，存在语法不一致
优点：基本框架正确，使用了中序遍历，使用了深度参数控制括号
题目总分：3+6=9分
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
暂无评论，来抢沙发