五.算法设计题 1.[题目分析]以二叉树表示算术表达式,根结点用于存储运算符。若能先分别求出左子树 和右子树表示的子表达式的值,最后就可以根据根结点的运算符的要求,计算出表达式的最 后结果 typedef struct node ElemType data; float val char optr;//只取“+ struct node * lchild, *rchildBiNode, *BiTree float Post Eval(Bitree bt)//以后序遍历算法求以二叉树表示的算术表达式的值 Float lv,rv if(bt!=null) lv= Post Eval(bt-> lchild);//求左子树表示的子表达式的值 rv= Posteval(bt- rchild);//求右子树表示的子表达式的值 switch(bt->optr) aluelvory: break value=lv-rv: break lue=lvar break case 3 return(value): I 2.[题目分析]本题是将符号算术表达式用二叉树表示的逆问题,即将二叉树表示的表 达式还原成原表达式。二叉树的中序遍历序列与原算术表达式基本相同,差别仅在于二叉树 表示中消除了括号。将中序序列加上括号就恢复原貌。当根结点运算符优先级高于左子树(或 右子树)根结点运算符时,就需要加括号 int Precede(char optrl, optr2) ∥/比较运算符级别高低, optrl级别高于optr2时返回1,相等时返回0,低于时返 回-1 Switch(optrl Icase+: case'-':if(optr2=+'Iloptr2==-)return(0); else return(-1) case“*’:case‘/':i(optr1==‘*’|lptr2==/') return(O0); else return(1); void InorderExp (BiTree bt) /输出二叉树表示的算术表达式,设二叉树的数据域是运算符或变量名 lint bracket if(bt) lif(bt->lchild!=null) { bracket= Precede(bt->data,bt- lchild->data)//比较双亲与左子女运算符优 先级 if(bracket==) printf('(') InorderExp(bt->lchild) //输出左子女表示的算术表达式 if( bracket=) printf(“)’)://加上右括号 printf(bt->data) //输出根结点 if(bt->rchild!=null) //输出右子树表示的算术表达式
五．算法设计题 1．[题目分析]以二叉树表示算术表达式，根结点用于存储运算符。若能先分别求出左子树 和右子树表示的子表达式的值，最后就可以根据根结点的运算符的要求，计算出表达式的最 后结果。 typedef struct node {ElemType data; float val; char optr; //只取‘+’， ‘-’， ‘*’，‘/’ struct node *lchild，*rchild }BiNode,*BiTree; float PostEval(BiTree bt) // 以后序遍历算法求以二叉树表示的算术表达式的值 {float lv,rv; if(bt!=null) {lv=PostEval(bt->lchild); // 求左子树表示的子表达式的值 rv=PostEval(bt->rchild); // 求右子树表示的子表达式的值 switch(bt->optr) {case ‘+’: value=lv+rv; break; case ‘-’: value=lv-rv;break; case ‘*’: value=lv*rv;break; case ‘/’: value=lv/rv; } } return(value); } 2.[题目分析] 本题是将符号算术表达式用二叉树表示的逆问题，即将二叉树表示的表 达式还原成原表达式。二叉树的中序遍历序列与原算术表达式基本相同，差别仅在于二叉树 表示中消除了括号。将中序序列加上括号就恢复原貌。当根结点运算符优先级高于左子树（或 右子树）根结点运算符时，就需要加括号。 int Precede(char optr1,optr2) // 比较运算符级别高低，optr1 级别高于 optr2 时返回 1，相等时返回 0，低于时返 回-1 {switch(optr1) {case‘+’:case‘-’:if(optr2==‘+’||optr2==‘-’)return(0);else return(-1); case‘*’:case‘/’:if(optr1==‘*’||optr2==‘/’)return(0);else return(1); } } void InorderExp (BiTree bt) //输出二叉树表示的算术表达式，设二叉树的数据域是运算符或变量名 {int bracket; if(bt) {if(bt->lchild!=null) {bracket=Precede(bt->data,bt->lchild->data)//比较双亲与左子女运算符优 先级 if(bracket==1) printf(‘(’)； InorderExp(bt->lchild); //输出左子女表示的算术表达式 if(bracket==1)printf(‘)’)； //加上右括号 } printf(bt->data); //输出根结点 if(bt->rchild!=null) //输出右子树表示的算术表达式
(bracket=Precede(bt->data, bt->rchild->data) if( bracket=1) printf(“(”)://右子女级别低,加括号 InorderExp (bt->rchild) if( bracket==1) printf(“)”) }/结束 Inorder Exp 3.[题目分析]首先通过对二叉树后序遍历形成后缀表达式,这可通过全局变量的字符 数组存放后缀表达式;接着对后缀表达式求值,借助于一栈存放运算结果。从左到右扫描后 缀表达式,遇操作数就压入栈中,遇运算符就从栈中弹出两个操作数,作运算符要求的运算 并把运算结果压入栈中,如此下去,直到后缀表达式结束,这时栈中只有一个数,这就是表 达式的值 char ar[ maxsize];// mansize是后缀表达式所能达到的最大长度 int i=l void postorder( BiTree t)//后序遍历二叉树t,以得到后缀表达式 lif(t) [ tOrder(t->lchild): PostOrder(b->rchild); ar[i++]=b->data;I }//结束 PostOrder void EXPVALUEO //对二叉树表示的算术表达式,进行后缀表达式的求值 ar[i]=“0 //给后缀表达式加上结束标记 char valuel //存放操作数及部分运算结果 while(ch!=‘0 Switch(ch) case ch in op: andi-pop( value);opnd2=pop( value);//处理运算符 push(operate(opnd2, ch, opnd1)); break default push(value, ch) //处理操作数,压入 栈中 ch=ar[i++] //读入后缀表达式 I printf(value[1]) ∥/栈中只剩下一个操作数,即运算结束 }//结束 EXPVALUE [算法讨论]根据题意,操作数是单字母变量,存放运算结果的栈也用了字符数组。实 际上,操作数既可能是变量,也可以是常量。运算中,两个操作数(opdl和opnd2)也不 会直接运算,即两个操作数要从字符转换成数(如‘3’是字符,而数值3=‘3’-“0’)。 数在压入字符栈也必须转换,算法中的 operate也是一个需要编写的函数,可参见上面算法 设计题1,其细节不再深入讨论。 4.[题目分析]当森林(树)以孩子兄弟表示法存储时,若结点没有孩子(fch=nu11) 则它必是叶子,总的叶子结点个数是孩子子树(fch)上的叶子数和兄弟(nsib)子树上叶 结点个数之和 typedef struct node ElemType data;//数据域 struct node*fch,*nsib;//孩子与兄弟域}*Tree; int Leaves (Tree t
{bracket=Precede(bt->data,bt->rchild->data) if (bracket==1)printf(“(”)； //右子女级别低，加括号 InorderExp (bt->rchild); if(bracket==1)printf(“)”)； } } }//结束 Inorder Exp 3．[题目分析]首先通过对二叉树后序遍历形成后缀表达式，这可通过全局变量的字符 数组存放后缀表达式；接着对后缀表达式求值，借助于一栈存放运算结果。从左到右扫描后 缀表达式，遇操作数就压入栈中，遇运算符就从栈中弹出两个操作数，作运算符要求的运算， 并把运算结果压入栈中，如此下去，直到后缀表达式结束，这时栈中只有一个数，这就是表 达式的值。 char ar[maxsize];//maxsize 是后缀表达式所能达到的最大长度 int i=1; void PostOrder(BiTree t )//后序遍历二叉树 t,以得到后缀表达式 {if(t) {PostOrder(t->lchild); PostOrder(b->rchild)；ar[i++]=b->data; } }//结束 PostOrder void EXPVALUE() //对二叉树表示的算术表达式，进行后缀表达式的求值 {ar[i]=‘\0’; //给后缀表达式加上结束标记 char value[]; //存放操作数及部分运算结果 i=1; ch=ar[i++]; while(ch!=‘\0’) {switch(ch) {case ch in op: opnd1=pop(value);opnd2=pop(value); //处理运算符 push(operate(opnd2,ch,opnd1));break; default: push(value,ch); //处理操作数，压入 栈中 } ch=ar[i++]; //读入后缀表达式 } printf(value[1]); //栈中只剩下一个操作数，即运算结束。 } //结束 EXPVALUE [算法讨论] 根据题意，操作数是单字母变量，存放运算结果的栈也用了字符数组。实 际上，操作数既可能是变量，也可以是常量。运算中，两个操作数（opnd1 和 opnd2）也不 会直接运算，即两个操作数要从字符转换成数（如‘3’是字符，而数值 3=‘3’-‘0’）。 数在压入字符栈也必须转换，算法中的 operate 也是一个需要编写的函数，可参见上面算法 设计题 1，其细节不再深入讨论。 4．[题目分析]当森林（树）以孩子兄弟表示法存储时，若结点没有孩子（fch=null）, 则它必是叶子，总的叶子结点个数是孩子子树（fch）上的叶子数和兄弟（nsib）子树上叶 结点个数之和。 typedef struct node {ElemType data;//数据域 struct node *fch, *nsib;//孩子与兄弟域 }*Tree; int Leaves (Tree t)