分析
这道题是一道非常普通的求表达式树的后缀表达式的题. 一般的做法是对树进行后序遍历, 但唯一的坑点在于, 运算符“+”“-”除了作为双目运算符表示相加或相减外, 还可以作为单目运算符表示正或负, 此时只需要一个运算数, 即只有一颗子树(度为1)。所以我们需要额外加一个判断:当前结点是否度为1, 如果是的话应该执行先序遍历, 即运算符要在运算数前面。
树的存储及读入树的信息
在本题输入中, 树的左右孩子的信息均为编号(pat的题为什么要用这么怪异的输入风格),所以显然用一个数组来存储树最好。
N<=20, 所以我们定义的结构体数组的索引最大值为20, 长度为21.
typedef struct{
char data[11];//结点的内容
int left, right;
int pre;//前驱
}node;
node Tree[21];
在信息读入之前, 我们有必要对数组进行基本的初始化
void InitTree(void){
for(int i=1; i<21; i++){
Tree[i].left = Tree[i].right = Tree[i].pre = -1;
}
}
进行信息的读入, 如果当前i结点的左/右孩子不为空(-1)的话, 我们就把左/右孩子的前驱设为i, 至于为什么要多一个前驱信息马上揭晓.
void CreateTree(int N){
for(int i=1; i<=N; i++){
scanf("%s%d%d", Tree[i].data, &Tree[i].left, &Tree[i].right);
if(Tree[i].left != -1){
Tree[Tree[i].left].pre = i;
}
if(Tree[i].right != -1){
Tree[Tree[i].right].pre = i;
}
}
}
打印后缀表达式
正如最开始我们提到的, 要根据当前结点是否度为1采用不同的遍历策略.
判断是否度为1的函数
int IsOneChild(int root){
if(Tree[root].left == -1 && Tree[root].right == -1){
return 0;
}
if(Tree[root].left != -1 && Tree[root].right != -1){
return 0;
}
return 1;
}
遍历树的函数, 值得注意的是在本题的测试数据中, 如果一个结点入度为1, 则它的子树一定是有右子树, 但本程序中并没有使用这个特性
void SuffixExp(int root){
if(root == -1){
return;
}
printf("(");
if(IsOneChild(root)){//入度为1执行先序遍历
printf("%s", Tree[root].data);
SuffixExp(Tree[root].left);
SuffixExp(Tree[root].right);
}
else{//否则执行后序遍历
SuffixExp(Tree[root].left);
SuffixExp(Tree[root].right);
printf("%s", Tree[root].data);
}
printf(")");
}
要遍历一颗树当然要从树的根结点开始, 但我们并不能确定究竟哪个是根结点, 所以前驱的作用就体现出来了, 它能帮我们快速定位根结点, 因为从任一结点开始不断找前驱总会到达根结点, 而根结点的标志就是没有前驱(-1)
int getRoot(void){
int i = 1;
while(Tree[i].pre != -1){
i = Tree[i].pre;
}
return i;
}
主逻辑
将上面几个函数组合一下, 我们的程序就完成了
#include <stdio.h>
#include <string.h>
typedef struct{
char data[11];//结点的内容
int left, right;
int pre;//前驱
}node;
node Tree[21];
void InitTree(void){
for(int i=1; i<21; i++){
Tree[i].left = Tree[i].right = Tree[i].pre = -1;
}
}
void CreateTree(int N){
for(int i=1; i<=N; i++){
scanf("%s%d%d", Tree[i].data, &Tree[i].left, &Tree[i].right);
if(Tree[i].left != -1){
Tree[Tree[i].left].pre = i;
}
if(Tree[i].right != -1){
Tree[Tree[i].right].pre = i;
}
}
}
int getRoot(void){
int i = 1;
while(Tree[i].pre != -1){
i = Tree[i].pre;
}
return i;
}
int IsOneChild(int root){
if(Tree[root].left == -1 && Tree[root].right == -1){
return 0;
}
if(Tree[root].left != -1 && Tree[root].right != -1){
return 0;
}
return 1;
}
void SuffixExp(int root){
if(root == -1){
return;
}
printf("(");
if(IsOneChild(root)){
printf("%s", Tree[root].data);
SuffixExp(Tree[root].left);
SuffixExp(Tree[root].right);
}
else{
SuffixExp(Tree[root].left);
SuffixExp(Tree[root].right);
printf("%s", Tree[root].data);
}
printf(")");
}
int main(void){
int N;
scanf("%d", &N);
InitTree();
CreateTree(N);
SuffixExp(getRoot());
}
嘿嘿
#可恶, 好羞耻
当某个非叶结点n的左子树为空时, n存储的内容不在被认为是运算符, 而是右子树值的符号
大佬这个是从题目输出样例中推出来的吗在表达式树中, 根结点是运算符, 两个子树的值是运算数对吧.
那么当一个结点n只有一颗子树时, 就只有一个运算数, 显然这个时候这个n结点只能是减号”-“或加号”+”, 因为这两个运算符可以是单目的表示正负.
所以这里其实要判断的是某个结点是否只有一颗子树, 但这道题的数据比较特殊的是如果一个结点只有一颗子树就一定是右子树, 所以就有了文中的结论了(这里确实写的不够清楚)
感谢