《2022年算术表达式-二叉树 .pdf》由会员分享，可在线阅读，更多相关《2022年算术表达式-二叉树 .pdf（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、最早提出遍历问题的是对存储在计算机中的表达式求值。例如：(a+b(c-d)-e/f。表达式用树形来表示，如图8-11-1 所示。运算符在树中放在非终端结点的位置上，操作数放在叶子结点处。当我们对此二叉树进行先序、中序和后序遍历后，便可得到表达式的前缀、中缀和后缀书写形式：前缀： -+a*b-cd/ef 中缀： a+b*c-d-e/f 后缀： abcd-*+ef/- 其中，中缀形式是算术表达式的通常形式，只是没有括号。在计算机内，使用后缀表达式易于求值。例 1 输入一个算术表达式，判断该表达式是否合法，若不合法，给出错误信息；若合法，则输出合法表达式的表达式树。【算法分析】表达式不合法有三种情况
2、：左右括号不匹配；变量名不合法；运算符两旁无参与运算的变量或数。分析表达式树可以看到：表达式的根结点及其子树的根结点为运算符，其在树中的顺序是按运算的先后顺序从后到前，表达树的叶子为参与运算的变量或数。表达式树如图8-11-2 处理时， 首先找到运算级别最低的运算符“ +”作为根结点， 继而确定该根结点的左、右子树结点在表达式串中的范围为a和 (b-c)/d，再在对应的范围内寻找运算级别最低的运算符作为子树的根结点，直到范围内无运算符，则剩余的变量或数为表达式树的叶子。【算法步骤】 设数组 ex 存放表达式串的各字符，lt、rt 作为结点的左右指针，变量left、 right 用于存放每次取字
3、符范围的左、右界。 设置左界初值为1；右界初值为串长度。 判断左右括号是否匹配，不匹配则认为输入有错误。 在表达式的左右界范围内寻找运算级别最低的运算符，同时判断运算符两旁有否参与运算的变量或数。若无，则输入表达式不合法；若有，作为当前子树的根结点，设置左子树指针及其左右界值，设置右子树指针及其左右界值。 若表达式在左右界范围内无运算符，则为叶子结点，判断变量名或数是否合法。 转，直到表达式字符取完为止。源程序中的h、d、w 用于存放文本画图时结点的坐标位置。program exptree; uses crt; type point=tree; tree=record data:string;
4、 lt:point; rt:point; end; var n,len,k:integer; ex:string; letters:set of char; root:point; procedure error(er:byte); 出错信息提示 begin write(Enter error:); case er of 1:writeln(No letter); 2,3:writeln(No expressint); 4:writeln(No+,*,-or/); 5:writeln(No(or); end; write(Press.);readln;halt(1); end; procedu
5、re create(left,right:integer;var p:point); var q:point; k,n:integer; begin 找运算级别最低的运算符 if exleft=( then begin n:=left+1;k:=0; 例如，表达式：a+(b-c)/d 运算顺序： / a * e f b c d 图 8-11-1 a / d b c 图 8-11-2 表达式树名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - -
6、 - - while (n=0) do begin if exn=( then inc(k); if exn=) then dec(k); inc(n); end; if n=right then begin dec(right);inc(left); end; end; if rightleft then error(1); n:=right;k:=0; repeat if exn=) then inc(k); if exn=( then dec(k); dec(n); until (exn=+) or (exn=-) and (k=0) or (nleft then begin with
7、p do begin data:=exn; new(q);lt:=q; new(q);rt:=q; end; create(left,n-1,p.lt); create(n+1,right,p.rt); end else not found +- begin n:=right; repeat if exn=) then inc(k); if exn=( then dec(k); dec(n); until (exn=*) or (exn=/) and (k=0) or (nleft then begin with p do begin data:=exn; new(q);rt:=q; new(
8、q);lt:=q; end; create(left,n-1,p.lt); create(n+1,right,p.rt); end else only string begin 求叶子结点的字串 for k:=left to right do if not(exk in letters) then error(1); p.data:=; for k:=left to right do p.data:=p.data+exk; p.lt:=nil; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - -
9、 - 第 2 页，共 3 页 - - - - - - - - - p.rt:=nil; end; end; end; procedure pr_tree(w,dep:integer;p:point); 画出生成的表达式树 var h,i,lt,rt:integer; begin h:=40;for i:=1 to dep do h:=h div 2; gotoxy(w-1,dep*3);write(,p.data,); if p.lt=nil then lt:=w else begin lt:=w-h;pr_tree(lt,dep+1,p.lt) end; if p.rt=nil then r
10、t:=w else begin rt:=w+h;pr_tree(rt,dep+1,p.rt); end; if ltrt then begin gotoxy(w,dep*3+1);write(|); gotoxy(lt,3*dep+2);write(|); for i:=lt to rt-2 do write(-);write(|); end; end; begin clrscr; letters:=A.Z,a.z,0.9; repeat write(Enter expression:);readln(ex); len:=length(ex) until len0; n:=1; k:=0; w
11、hile (n=0) do 判断左括号是否匹配 begin if exn=( then inc(k); if exn=) then dec(k); inc(n); end; if k0 then error(5); new(root);create(1,len,root); pr_tree(40,1,root);readln end. 注： Pascal语言的程序中，通过在程序的开头使用uses命令，说明所需要使用的单元，其语法为：uses ；单元名表是指用逗号隔开的1个或多个单元名称 crt 具有屏幕模式控制、扩展键盘码、颜色、窗口、声音等功能 clrscr 清楚当前窗口或屏幕，光标返回到左上角 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -