最早提出遍历问题的是对存储在计算机中的表达式求值。例如：(a+b ×(c-d))-e/f 。表达式用树形来表示，如图8-11-1所示。运算符在树中放在非终端结点的位置上，操作数放在叶子结点处。
当我们对此二叉树进行先序、中序和后序遍历后，便可得到表达式的前缀、中缀和后缀书写形式：
前缀：-+a*b-cd/ef
中缀：a+b*c-d-e/f 后缀：abcd-*+ef/-
其中，中缀形式是算术表达式的通常形式，只是没有括号。在计算机内，使用后缀表达式易于求值。
例1 输入一个算术表达式，判断该表达式是否合法，若不合法，给出错误信息；若合法，则输出合法表达式的表达式树。 【算法分析】表达式不合法有三种情况：①左右括号不匹配；②变量名不合法；③运算符两旁无参与运算的变量或数。
分析表达式树可以看到：表达式的根结点及其子树的根结点为运算符，其在树中的顺序是按运算的先后顺序从后到前，表达树的叶子为参与运算的变量或数。
表达式树如图8-11-2
处理时，首先找到运算级别最低的运算符“+”作为根结点，继而确定该根结点的左、右子树结点在表达式串中的范围为a 和(b-c)/d ，再在对应的范围内寻找运算级别最低的运算符作为子树的根结点，直到范围内无运算符，则剩余的变量或数为表达式树的叶子。
【算法步骤】
① 设数组ex 存放表达式串的各字符，lt 、rt 作为结点的左右指针，变量left 、right 用于存放每次取字符范围的左、右界。 ② 设置左界初值为1；右界初值为串长度。
③ 判断左右括号是否匹配，不匹配则认为输入有错误。
④ 在表达式的左右界范围内寻找运算级别最低的运算符，同时判断运算符两旁有否参与运算的变量或数。若无，则输入表达式不合法；若有，作为当前子树的根结点，设置左子树指针及其左右界值，设置右子树指针及其左右界值。
⑤ 若表达式在左右界范围内无运算符，则为叶子结点，判断变量名或数是否合法。
⑥ 转④，直到表达式字符取完为止。
源程序中的h 、d 、w 用于存放文本画图时结点的坐标位置。 program exptree; uses crt; type
point=^tree; tree=record
data:string;
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
procedure create(left,right:integer;var p:point); var q:point; k,n:integer;
begin {找运算级别最低的运算符} if ex[left]='(' then begin
n:=left+1;k:=0;
例如，表达式：a+(b-c)/d 运算顺序： ③ ① ② 图8-11-1
图8-11-2 表达式树
while (n
begin
if ex[n]='(' then inc(k);
if ex[n]=')' then dec(k);
inc(n);
end;
if n=right then
begin
dec(right);inc(left);
end;
end;
if right n:=right;k:=0; repeat if ex[n]=')' then inc(k); if ex[n]='(' then dec(k); dec(n); until (((ex[n]='+') or (ex[n]='-')) and (k=0)) or (n if n=left then error(3); if n>left then begin with p^ do begin data:=ex[n]; 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 ex[n]=')' then inc(k); if ex[n]='(' then dec(k); dec(n); until (((ex[n]='*') or (ex[n]='/')) and (k=0)) or (n if n=left then error(3); if n>left then begin with p^ do begin data:=ex[n]; new(q);rt:=q; new(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(ex[k] in letters) then error(1); p^.data:=''; for k:=left to right do p^.data:=p^.data+ex[k]; p^.lt:=nil; 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 rt:=w else begin rt:=w+h;pr_tree(rt,dep+1,p^.rt); end; if lt<>rt 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 len>0; n:=1; k:=0; while (n<=len) and (k>=0) do {判断左括号是否匹配} begin if ex[n]='(' then inc(k); if ex[n]=')' then dec(k); inc(n); end; if k<>0 then error(5); new(root);create(1,len,root); pr_tree(40,1,root);readln end. 注：Pascal语言的程序中，通过在程序的开头使用uses命令，说明所需要使用的单元，其语法为：uses <单元名表>；{单元名表是指用逗号隔开的1个或多个单元名称} crt {具有屏幕模式控制、扩展键盘码、颜色、窗口、声音等功能} clrscr {清楚当前窗口或屏幕，光标返回到左上角} 实验报告 课程名称数据结构 实验项目实验三--创建一个二叉树并输出三种遍历结果 系别■计算机学院 _________________ 专业_______________ 班级/学号_____________ 学生姓名___________ 实验日期— 成绩______________________________ 指导 教师 实验题目：实验三创建一个二叉树并输出三种遍历结果 实验目的 1）掌握二叉树存储结构； 2）掌握并实现二叉树遍历的递归算法和非递归算法; 3）理解树及森林对二叉树的转换; 4）理解二叉树的应用一哈夫曼编码及WPL计算。 实验内容 1）以广义表或遍历序列形式创建一个二叉树，存储结构自选； 2）输出先序、中序、后序遍历序列； 3）二选一应用题：1）树和森林向二叉树转换；2）哈夫曼编码的应用问题。 题目可替换上述前两项实验内容） 设计与编码 1）程序结构基本设计框架 （提示：请根据所选定题目，描述程序的基本框架，可以用流程图、界面描述图、 框图等来表示） 2）本实验用到的理论知识遍历二叉树，递归和非递归的方法 （应用型 (提示：总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，要求结合自己的题目并阐述自己的理解和想法) 3) 具体算法设计 1) 首先，定义二叉树的存储结构为二叉链表存储，每个元素的数 据类型Elemtype,定义一棵二叉树，只需定义其根指针。 2) 然后以递归的先序遍历方法创建二叉树，函数为CreateTree()，在输 入字符时要注意,当节点的左孩子或者右孩子为空的时候,应当输入一 个特殊的字符(本算法为“ #”),表示左孩子或者右孩子为空。 3) 下一步,创建利用递归方法先序遍历二叉树的函数,函数为 PreOrderTreeQ,创建非递归方法中序遍历二叉树的函数，函数为 InOrderTree()，中序遍历过程是：从二叉树的根节点开始，沿左子树 向下搜索，在搜索过程将所遇到的节点进栈；左子树遍历完毕后，从 栈顶退出栈中的节点并访问；然后再用上述过程遍历右子树，依次类 推，指导整棵二叉树全部访问完毕。创建递归方法后序遍历二叉树的 函数，函数为LaOrderTree()。 (提示：该部分主要是利用C、C++ 等完成数据结构定义、设计算法实现各种操作，可以用列表分步形式的自然语言描述，也可以利用流程图等描述) 4) 编码 #include 全国计算机等级考试二级公共基础之树与二叉树 1.6 树与二叉树 1.6.1 树的基本概念 树是一种简单的非线性结构。在树这种结构中，所有元素之间的关系具有明显的层次关系。用图形表示树这种数据结构时，就象自然界中的倒长的树，这种结构就用“树”来命名。如图： 在树结构中，每个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根（如R）。 在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点（如W，Z，A ，L，B，N，O，T，H，X）。 在树结构中，一个结点拥有的后件个数称为结点的度（如R的度为4，KPQDEC 结点度均为2）。 树的结点是层次结构，一般按如下原则分层：根结点在第1层；同一个层所有结点的所有子结点都在下一层。树的最大层次称为树的深度。如上图中的树深度为4。R结点有4棵子树，KPQDEC结占各有两棵子树；叶子没有子树。 在计算机中，可以用树结构表示算术运算。在算术运算中，一个运算符可以有若干个运算对象。如取正（+）与取负（-）运算符只有一个运算对象，称为单目运算符；加（+）、减（-）、乘（*）、除（/）、乘幂（**）有两个运算对象，称为双目运算符；三元函数f(x,y,z)为 f函数运算符，有三个运算对象，称为三目运算符。多元函数有多个运算对象称多目运算符。 用树表示算术表达式原则是： (1)表达式中的每一个运算符在树中对应一个结点，称为运算符结点 (2)运算符的每一个运算对象在树中为该运算结点的子树(在树中的顺序从 左到右) (3)运算对象中的单变量均为叶子结点 根据上面原则，可将表达式：a*(b+c/d)+c*h-g*f表示如下的树。 树在计算机中通常用多重链表表示，多重链表的每个结点描述了树中对应结点的信息，每个结点中的链域（指针域）个数随树中该结点的度而定。 1.6.2 二叉树及其基本性质 1. 什么是二叉树 二叉树是很有用的非线性结构。它与树结构很相似，树结构的所有术语都可用到二叉树这种结构上。 二叉树具有以下两个特点： （1）非空两叉树只有一个根结点 （2）每个结点最多有两棵子树，且分别称该结点的左子树与右子树。 也就是说，在二叉树中，每一个结点的度最大为2，而且所有子树也均为二叉树。二叉树中的每一个结点可以有左子树没有右子树，也可以有右子树没有左子树，甚至左右子树都没有。 实验六：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：a+b*(c-d)-e/f 三、实验要求 如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的个数。求二叉树的深度。十进制的四则运算的计算器可以接收用户来自键盘的输入。由输入的表达式字符串动态生成算术表达式所对应的二叉树。自动完成求值运算和输出结果。四、实验环境 PC微机 DOS操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 1、根据二叉树的各种存储结构建立二叉树； 2、设计求叶子结点个数算法和树的深度算法； 3、根据表达式建立相应的二叉树，生成表达式树的模块； 4、根据表达式树，求出表达式值，生成求值模块； 5、程序运行效果，测试数据分析算法。 六、测试数据 1、输入数据：*（+）3 正确结果： 2、输入数据：(1+2)*3+(5+6*7); 正确输出：56 七、表达式求值 由于表达式求值算法较为复杂，所以单独列出来加以分析： 1、主要思路：由于操作数是任意的实数，所以必须将原始的中缀表达式中的操作数、操作符以及括号分解出来，并以字符串的形式保存；然后再将其转换为后缀表达式的顺序，后缀表达式可以很容易地利用堆栈计算出表达式的值。 例如有如下的中缀表达式： a+b-c 转换成后缀表达式为： ab+c- 然后分别按从左到右放入栈中，如果碰到操作符就从栈中弹出两个操作数进行运算，最后再将运算结果放入栈中，依次进行直到表达式结束。如上述的后缀表达式先将a 和b 放入栈中，然后碰到操作符“+”，则从栈中弹出a 和b 进行a+b 的运算，并将其结果d（假设为d）放入栈中，然后再将c 放入栈中，最后是操作符“-”，所以再弹出d和c 进行d-c 运算，并将其结果再次放入栈中，此时表达式结束，则栈中的元素值就是该表达式最后的运算结果。当然将原始的中缀表达式转换为后缀表达式比较关键，要同时考虑操作符的优先级以及对有括号的情况下的处理，相关内容会在算法具体实现中详细讨论。 2、求值过程 一、将原始的中缀表达式中的操作数、操作符以及括号按顺序分解出来，并以字符串的 形式保存。 二、将分解的中缀表达式转换为后缀表达式的形式，即调整各项字符串的顺序，并将括 号处理掉。 三、计算后缀表达式的值。 3、中缀表达式分解 DivideExpressionToItem()函数。分解出原始中缀表达式中的操作数、操作符以及括号，保存在队列中，以本实验中的数据为例，分解完成后队列中的保存顺序如下图所示： 《数据结构与数据库》 实验报告 实验题目 算术表达式求值 学院：化学与材料科学学院 专业班级：09级材料科学与工程系PB0920603 姓名：李维谷 学号：PB09206285 邮箱：liwg@https://www.doczj.com/doc/9912102299.html, 指导教师：贾伯琪 实验时间：2010年10月10日 一、需要分析 问题描述： 表达式计算是实现程序设计语言的基本问题之一，它的实现是栈的应用的一个典型例子。设计一个程序，演示通过将数学表达式字符串转化为后缀表达式，并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。 问题分析： 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 设置运算符栈（字符型）和运算数栈（浮点型）辅助分析算符优先关系。在读入表达式的字符序列的同时完成运算符和运算数的识别处理，然后进行运算数的数值转换在进行四则运算。 在运算之后输出正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。 算法规定： 输入形式：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为使实验更完善，允许操作数为实数，操作符为（、）、.（表示小数点）、+、-、*、/、^（表示乘方），用#表示结束。 输出形式：演示表达式运算的中间结果和整个表达式的最终结果，以浮点型输出。 程序功能：对实数内的加减乘除乘方运算能正确的运算出结果，并能正确对错误输入和无定义的运算报错，能连续测试多组数据。 测试数据：正确输入：12*（3.6/3+4^2-1）# 输出结果：194.4 实验报告 姓名：黄雄镖学号：13331093 院系专业：软件学院2013级教务4班 完成日期：2014 年10 月20 日 实验题目：实现一个较为通用的计算器 需求分析： 实现一个包含加减乘除运算的较为通用的计算器，操作数可能是负数，并且可能是多位数。运算式中可以有括号和多余空格。计算器对负号不敏感, 形如1+-1或者1+(-1)都是可以接受的。 概要设计 思路: 将表达式的中缀表达式转换成后缀表达式，然后利用一个栈或者建立二叉树对后缀表达式进行求值。 由于多位数在转为后缀表达式时会分不清, 故在每个数和运算符后面加上一个空格作为区别 在主程序中调用用栈求值的计算器类和用二叉树计算的计算器类, 输出算式的结果 13331093_03.h里存放用栈求值的计算器类 13331093_03_tree.h里存放用二叉树计算的计算器类 13331093_03.h的类里主要包括: 获得算术表达式的函数getexpression(string expression), expression为所要计算的算术表达式计算函数calculate(string num2, string num1, string op), 输入为两个数(字符串形式)和一个操作符, 返回值为计算结果(字符串形式) 返回中缀表达式函数ShowMiddleExpression(), 返回的中缀表达式为字符串形式 RidSpace(string origin)用于去除输入中多余的空格, 输入为要除去空格的算术表达式, 返回去掉空格的算术表达式 MidToLast(string str)中缀表达式转后缀表达式 获得后缀表达式函数GetLastExpression(), 返回的后缀表达式为字符串形式 用栈执行计算后缀表达式函数exe(), 返回计算结果为字符串形式 13331093_03_tree.h类里主要包括: 获得算术表达式的函数getexpression(string expression), expression为所要计算的算术表达式计算函数calculate(string num2, string num1, string op), 输入为两个数(字符串形式)和一个操作符, 返回值为计算结果(字符串形式) 返回中缀表达式函数ShowMiddleExpression(), 返回的中缀表达式为字符串形式 RidSpace(string origin)用于去除输入中多余的空格, 输入为要除去空格的算术表达式, 返回去掉空格的算术表达式 MidToLast(string str)中缀表达式转后缀表达式 获得后缀表达式函数GetLastExpression(), 返回的后缀表达式为字符串形式 生成一颗二叉树的函数makeTree(TNode *&p) 后序遍历二叉树并计算的函数PostOrder(TNode *p), 返回计算结果为字符串形式 a.调试过程遇到的问题与解决方案： 遇到的问题:调试过程中出现程序崩溃的现象, 后来debug发现是没有考虑到执行运算过程中出现的-()的情况 原因:没有考虑-()的情况, 导致栈为空的时候还弹出元素 解决方案：特殊处理这种情况 b.时间和空间复杂度： 数据结构程序报告（3） 2011.3.29 2. 需求分析： （1）功能：表达式可以用二叉树表示，对于简单的四则运算，请实现以下功能【1】对于任意给出的前缀表达式（不带括号）、中缀表达式（可以带括号）或后缀表达式（不带括号），能够在计算机内部构造出一棵表达式二叉树，并且图示出来（图形的形式）。 【2】对于构造好的内部表达式二叉树，按照用户的要求输出相应的前缀表达式（不带括号）、中缀表达式（可以带括号，但不允许冗余括）或后缀表达式（不带括号）。 提示：所谓中缀表达式中的冗余括号，就是去掉括号后不影响表达式的计算顺序。例如：“（c+b）+a”中的括号是冗余的，可以表示成不冗余的“c+b+a”。 （2）输入输出要求：请输入字符串表达式： 树形二叉树（图形显示） 中缀表达式为： 前缀表达式为： 后缀表达式为： 3.概要设计：（算法） 分成两部分完成： 【1】前缀、中缀、后缀表达式->二叉树表达式 前缀表达式->二叉树表达式：（a）碰到操作数则把其值赋给相应的新申请的二叉树结点，地址压栈；（b）碰到操作符则把其值赋给相应的新申请的二叉树，并从栈中弹出两个地址，分别作为其右指针和左指针，然后再把其地址压栈，最后一个地址即为二叉树的根结点地址。 中缀表达式->二叉树表达式：把中缀表达式转换成后缀表达式，然后再建立二 叉树。 后缀表达式->二叉树表达式：（a）碰到操作数则把其值赋给相应的新申请的二叉树结点，若栈为空则地址压栈，若非空则取栈顶元素，若栈顶元素的左孩子为空则当前结点设为其左孩子，左孩子为满则设为其右孩子再压栈；（b）碰到操作数则把其值赋给相应的新申请的二叉树结点，取栈顶元素，若栈顶元素的左孩子为空则设为其左孩子，左孩子为满则设为其右孩子开始那个元素地址为根结点地址，开始时用变量root保存。 【1】二叉树表达式->前缀、中缀、后缀表达式 二叉树表达式->前缀表达式：对二叉树表达式进行前序遍历。 二叉树表达式->中缀表达式：对二叉树表达式进行中序遍历，若结点操作符的优先级高于其左或右子树，在打印相应的子树之前先打印开括号，在打印相应的子树最后在打印一个闭括号。 二叉树表达式->后缀表达式：对二叉树表达式进行后序遍历。 数理学院 课程设计报告书 课程名称数据结构课程设计 设计题目算术表达式求值演示 专业班级 学号 姓名 指导教师 2014 年12 月 4.2.2 基本操作： InitStack(&S) 操作结果：构造一个空栈S。 GetTop(S) 初始条件：栈S 已存在。 操作结 果： 用P 返回S的栈顶元素。Push(&S 初始条 件：，ch) 栈S 已存在。 操作结 果：插入元素ch 为新的栈顶元素。 Pop(&S) 初始条件：栈S 已存在。 操作结 果：删除S 的栈顶元素。 In(ch) 操作结果：判断字符是否是运算符，运算符即返回1 Precede(c1, c2) 初始条件：c1,c2 为运算符。操作结果：判断运算符优先权，返回优先权高的。Operate(a,op,b) 初始条件：a,b 为整数，op为运算符。操作结果： a 与 b 进行运算，op 为运算符，返回其值。num(n) 操作结果：返回操作数的长度。EvalExpr() 初始条件：输入表达式合法。操作结果：返回表达式的最终结果。}ADT Stack 主程序的流程： EvaluateExpression() 函数实现了对表达式求值的功能，main() 函数直接调用EvaluateExpression() 对输入的表达式求值输出。 4.2.3 函数的调用关系图 4.3 详细设计 4.3.1 ① . Precede(char c1,char c2)判断运算符优先权，返回优先权高的 算符间的优先关系 如下： 算法伪代码如下： char Precede(char c1,char c2) { static char array[49]={ >', '>', '<', '<', '<', '>', '>', >', '>', '<', '<', '<', '>', '>', >', '>', '>', '>', '<', '>', '>', >', '>', '>', '>', '<', '>', '>', <', '<', '<', '<', '<', '=', '!', >', '>', '>', '>', '!', '>', '>', <', '<', '<', '<', '<', '!', '='}; // 用一维数组存储 49 种情况 switch(c1) { /* i 为下面 array 的横标 */ case '+' : i=0;break; case '-' : i=1;break; case '*' : i=2;break; 实验课题一：将下图中得二叉树用二叉链表表示： 1用三种遍历算法遍历该二叉树，给出对应得输出结果; 2写一个函数对二叉树搜索,若给出一个结点，根据其就是否属于该树，输出tｒｕe或者f ａｌse。 3写函数完成习题4、31(Ｃ＋+版)或4、2８（C版教科书）。 #iｎclｕde "stdio、h＂ ＃incluｄe”mallｏc、h" typedｅfｓtruct BｉTＮode ｛ cｈar data; sｔrucｔBiTＮode *lｃｈild,*rｃhiｌd; }ＢiTＮodｅ，*BiTrｅe； BｉＴree Creaｔe（BｉTｒeｅT) ｛ char ch； ch=getchａｒ(）; ｉｆ(ch=='#’） T=NULL; elｓe { T=(BiＴNode *）maｌloc(sｉｚｅｏf（ＢiTNｏｄe)）; Ｔ-〉data=ｃh； Ｔ-＞lｃｈiｌd=Creaｔe(T—〉lchilｄ); T—〉rchild=Creａte(Ｔ－〉rchｉld）； ｝ retuｒn Ｔ； } ｉnt node(BiＴrｅe Ｔ) { int sum1=0，a,b; ?iｆ（T) ｛ if（Ｔ！=ＮUＬL） ??sｕm1++; ?ａ=ｎode（Ｔ->lchiｌd); sｕm1＋=ａ； b=node(T—>rchｉld)； sum1+=b; ?} ｒetｕrn sum1； } int mｎode（BiTree T） { ?int sum２=0,ｅ，ｆ； if（T) { ?ｉf（（T->lcｈiｌd!=NULL）&＆(T－〉rchild!=NULL）)?sum2++； ?e=ｍnoｄｅ（Ｔ－〉lchild); suｍ2＋=e; f＝mnoｄｅ（T－〉rchｉｌd)； sum２+=f； ?｝ retｕrn sum2; ｝ void Preorｄer（BiTree T) { ｉf(Ｔ） { pｒintf（＂%c”，T－>daｔa)； Ｐreoｒder(Ｔ—>lchiｌｄ）； Ｐreorder（T－〉rchｉld）； ｝ } iｎt Sumｌeaｆ（BiTｒｅe T) { int suｍ=0,m，n; if（T） { if((！T-〉lchild）&&（!T-〉rｃhiｌd)) sum++； m=Ｓuｍleaf（T－>lchｉld)； suｍ+=m； n=Sumleaf(T—＞rｃhｉｌd); suｍ+＝ｎ； ｝ retuｒn ｓum； } 第六章 树和二叉树 一、选择题 1．算术表达式a+b*（c+d/e ）转为后缀表达式后为（ B ） A ．ab+cde/* B ．abcde/+*+ C ．abcde/*++ D ．2. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ C ） A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G 3. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1 ，1 则T 中的叶子数为（ D ） A ．5 B ．6 C ．7 D ．8 4. 在下述结论中，正确的是（ D ） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意 交换; ④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A ．①②③ B ．②③④ C ．②④ D ．①④ 5. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（ A ） A ．m-n B ．m-n-1 C ．n+1 D ．条件不足，无法确定 6．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B ） A ．9 B ．11 C ．15 D ．不确定 7．设森林F 中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F 对应的二叉树根结点的右子树上的结点个数是（ D ）。 A ．M1 B ．M1+M2 C ．M3 D ．M2+M3 8．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ E ） A ． 250 B ． 500 C ．254 D ．505 E ．以上答案都不对 9. 有关二叉树下列说法正确的是（ B ） A ．二叉树的度为2 B ．一棵二叉树的度可以小于2 C ．二叉树中至少有一个结点的度为2 D ．二叉树中任何一个结点的度都为2 10．二叉树的第I 层上最多含有结点数为（ C ） A ．2I B ． 2I-1-1 C ． 2I-1 D ．2I -1 11. 一个具有1025个结点的二叉树的高h 为（ C ） A ．11 B ．10 C ．11至1025之间 D ．10至1024之间 12．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( B )结点 A ．2h B ．2h-1 C ．2h+1 D ．h+1 13. 一棵树高为K 的完全二叉树至少有（ C ）个结点 A ．2k –1 B. 2k-1 –1 C. 2k-1 D. 2 k 14．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( C )次序的遍历 实现编号。 A ．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 15．一棵二叉树的前序遍历序列为ABCDEFG ，它的中序遍历序列可能是（ B ） 山西大学 课程设计任务书 设计题目算术表达式与二叉树 所属课程：数据结构 系别软件学院 专业软件工程 班级软工1408班 姓名霍志斌 指导教师李雪梅 设计任务下达日期 2015年 12 月15 日 设计时间2016年1月4日至 2016年1月8日 目录： 一、需求分析 二、概要设计 1、数据类型的声明： 2、表达式的抽象数据类型定义 3、整体设计 三、详细设计 1、二叉树的存储类型 2、顺序栈的存储类型 3、表达式的基本操作 4、主程序和其他伪码算法 5、函数的调用关系 四、设计和调试分析 五、测试 六、课程设计的心得和心得以及问题 一、需求分析【课程设计要求】 【问题的描述】 一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式Expression的操作。 【基本要求】 假设算术表达式Expression内可以含有变量（a-z）,常量（0-9）和二元运算符（+，-，*，/，^（乘幂））。实现以下操作： （1）ReadExpr(E)――以字符序列的形式输入语法正确的前缀表达式并构造表达式E。 （2）WriteExpr(E)――用带括号的中缀表达式输出表达式E。 （3）Assign(V，c)――实现对变量V的赋值（V=c），变量的初值为0。 （4）Value(E)――对算术表达式E求值。 （5）CompoundExpr(p,E1,E2)――构造一个新的复合表达式（E1）p（E2）。【测试数据】 1)分别输入0；a;-91;+a*bc;+*5x2*8x;+++*3^*2^x2x6并输出。 2)每当输入一个表达式后，对其中的变量赋值，然后对表达式求值。 二、概要设计 1、数据类型的声明： 在这个课程设计中，采用了链表二叉树的存储结构，以及两个顺序栈的辅助存储结构 /*头文件以及存储结构*/ #include 目录 一、系统开发的背景 (1) 二、系统分析与设计 (1) （一）系统功能要求 (1) （二）系统模块结构设计 (1) 三、系统的设计与实现 (3) （一）二叉树的遍历 (3) （二）算术表达式求值 (5) 四、系统测试 (9) （一）测试二叉树遍历函数 (9) （二）测试算术表达式求值函数 (10) 五、总结 (10) 六、附件（代码、部分图表） (10) (一)程序代码 (10) (二)实验截图 (15) 算术表达式与二叉树 一、系统开发的背景 为了方便进行基本的算术运算，减轻对数字较大的数操作时所带来的麻烦，及其在运算过程中错误的避免。因此设计算术表达式与二叉树的程序来解决此问题。 二、系统分析与设计 （一）系统功能要求 由于一个表达式和一棵二叉树之间，存在着自然的对应关系。遍写一个程序，实现基于二叉树表示的算术表达式的操作。算术表达式内可以含有变量（a～z）、常量（0～9）和二元运算符（+，-，*，/，^(乘幂)）。 具体实现以下操作： 1以字符序列的形式输入语法正确的前缀表达式并构造表达式。 2用带括弧的中缀表达式输出表达式。 3实现对变量V的赋值（V=c），变量的初值为0。 4对算术表达式E求值。 （二）系统模块结构设计 通过对系统功能的分析，基于二叉树表示的算术表达式的功能 如图（1）所示。 图1：基于二叉树表示的算术表达式的功能图 通过上图的功能分析，把整个系统划分为主要的两大个模块： 1、将语法正确的前缀表达式用二叉树的遍历转换成相应的遍历序列，必要时可以求出此二叉树的结点数及其树的深度。该模块借助函数BiTree Create(BiTree T)创建二叉树，void Preorder(BiTree T) 先序遍历， void InOrder(BiTree T)中序遍历，void PostOrder(BiTree T)后序遍历，int Sumleaf(BiTree T)统计叶结点的数目，int Depth(BiTree T)二叉树的深度6个函数联合来实现； 2、计算中序遍历所得的算术表达式的值。其中先要将扫描得到的中缀表达式转换为后缀表达式，然后利用栈的初始化，进栈与取栈顶元素操作进行对后缀表达式进行计算。该模块借助函数void InitStack(SeqStack *S)初始化栈，int PushStack(SeqStack *S,char e)进栈，int GetTop(SeqStack 实验报告 课程名称： 程序设计与数据结构 指导老师： ljq 成绩： 实验名称：基于二叉树结构的表达式求值算法 实验类型： 上机 同组学生姓名： 一、实验目的和要求（必填） 三、代码缺陷及修正记录 五、讨论、心得 二、实验内容和代码（必填） 四、实验结果与分析（必填） 一、实验目的和要求 1. 掌握编程工具的使用 2. 掌握二叉树数据结构在计算机上的实现 3. 掌握通过计算机编程解决问题的基本方法 二、实验内容和代码 1．实验内容： ● 编程实现基于二叉树结构的表达式求值算法 ● 表达式包含加减乘除四则运算以及至少一层括弧运算 ● 首先将输入的原表达式转换成二叉树结构，然后采用二叉树的后序递归遍历 方法求得表达式的值 ● 将所有实验内容合并到一个工程，增加交互操作和循环处理（持续） 2．代码 1.头文件expnbitree .h 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include 课程设计 教学院 课程名称 题目 专业 班级 姓名 同组人员 指导教师 2013 年 6 月22 日 (完成时间) 目录 一．概述 (2) 二．总体方案设计 (4) 三．详细设计 (6) 四．程序的调试与运行结果说明 (14) 五．课程设计总结 (14) 六．附录 (16) 参考文献 (3233) （“目录”要求必须自动生成） 一概述（宋体，三号，加粗，居中） 1.课程设计的目的（小标题，宋体，四号，加粗，左对齐顶格） （1）．理解和掌握该课程中的有关基本概念，程序设计思想和方法。 （2）．培养综合运用所学知识独立完成课题的能力。 （3）．培养勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。 （4）．掌握从资料文献、科学实验中获得知识的能力，提高学生从别人经验中找到解决问题的新途径的悟性，初步培养工程意识和创新能力。 2.课程设计的要求 算术表达式求值程序实现以下功能： (1)构造一个空栈S,初始条件：栈S已存在 (2)用P返回S的栈顶元素 (3)插入元素ch为新的栈顶元素 (4)删除S的栈顶元素 (5)判断字符是否是运算符，运算符即返回1 (6)判断运算符优先权，返回优先权高的 (7)输入表达式 (8)返回表达式的最终结果。 二总体方案设计 a)需求分析 该程序能实现算术四则运算表达式的求值，显示运算过程。 输入的形式：表达式，例如5*（3+7）#。 包含的运算符只能有'+'、 '-'、'*'、 '/'、 ' (' ') '； 程序所能达到的功能：对表达式求值并输出。 b)总体设计 本程序使用的是编程工具是Visual c++ 6.0，实现了运算器的功能和仿真界面（大体界面如下图所示）。在基本要求的基础上，运算数可以是实数类型，同时增加了乘方运算的功能；可以实现对负数的运算，例如用户输入表达式6* （-0.25）,则程序会在负号的前面自动加上一个0。 1)算符包括加（+）、减（-）、乘（*）、除（/）、乘方（^）；另一个称作 OPND，用以寄存操作数和运算结果，操作数可以是float型的浮点数。 算法的基本思想是： 2)首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素； 依次读入表达式中的每个字符，若是操作数（浮点数）则进OPND栈， 若是运算符（+、—、*、/、^）则和OPTR栈的栈顶运算符比较优先权 后作相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当 前读入的字符均为“#”）。 3)编写一个原型为void strtofloat(char str[ ],int n,int i)，把一 个数字串转换为一个实型数，并压入运算数栈中。（整个程序的源代码 见附录，并有具体解释） #include "stdio.h" #include "stdlib.h" #define STACK_INIT_SIZE 100 //栈存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 //------二叉树的存储结构表示------// typedef struct BiTNode{ int data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //-----顺序栈的存储结构表示------// typedef struct{ BiTree *top; BiTree *base; int stacksize; }SqStack; //*************************************************** //构造一个空栈s SqStack *InitStack(); //创建一颗二叉树 BiTree CreatBiTree(); //判断栈空 int StackEmpty(SqStack *S); //插入元素e为新的栈顶元素 void Push(SqStack *S,BiTree p); //若栈不为空，则删除s栈顶的元素e，将e插入到链表L中void Pop(SqStack *S,BiTree *q); //非递归先序遍历二叉树 void PreOrderTraverse(BiTree L); //非递归中序遍历二叉树 void InOrderTraverse(BiTree L); //非递归后序遍历二叉树 void PostOrderTraverse(BiTree L); //递归后序遍历二叉树 void PostOrder(BiTree bt); //递归中序遍历二叉树 void InOrder(BiTree bt); //递归先序遍历二叉树 void PreOrder(BiTree bt); //*************************************************** 目录 题目一.二叉树操作（1）二.算术表达式求 (1) 一、课程设计的目的 (1) 二、课程设计的内容和要求 (1) 三、题目一设计过程 (2) 四、题目二设计过程 (6) 五、设计总结 (17) 六、参考文献 (18) 题目一.二叉树操作（1）二.算术表达式求 一、课程设计的目的 本学期我们对《数据结构》这门课程进行了学习。这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。这次课程设计不但要求学生掌握《数据结构》中的各方面知识，还要求学生具备一定的C语言基础和编程能力。 （1）题目一的目的： 1、掌握二叉树的概念和性质 2、掌握二叉树的存储结构 3、掌握二叉树的基本操作 （2）题目二的目的： 1、掌握栈的顺序存储结构和链式存储结构 2、掌握栈的先进后出的特点 3、掌握栈的基本运算 二、课程设计的内容和要求 （1）题目一的内容和要求： 1、编写已知二叉树的先序、中序序列，恢复此二叉树的程序 2、编写求二叉树深度的程序 （2）题目二的内容和要求： 1、算术表达式由操作数、运算符和界限符组成。操作数是正整数，运算符为 加减乘除，界限符有左右括号和表达式起始 2、将一个表达式的中缀形式转化为相应的后缀形式 3、依据后缀表达式计算表达式的值 三、题目一设计过程 1、题目分析 现已知一棵二叉树的先序遍历序列和中序遍历序列，依次从先序遍历序列中取结点，由先序序列确定根结点(就是第一个字母)，每次取出一个结点就与中序遍历的序列进行比较，当相等的时候，中序遍历序列就被分成以该结点为根的二叉树子树，该结点左部分为左子树，右部分为右子树，直到取完先序列里的所有结点，则二叉树构造完毕（树用链式存储结构存储），用递归实现！ 由建好的二叉树，先判断这棵树是否为空，若不为空则找数的左子树，统计它的高度，然后找树的右子树，统计它的高度，比较左子树和右子树的高度，然后返回其中大的那个值加一，则求出数的高度。这里用递归实现！ 2、算法描述 main ( )（主函数） 先构造一颗二叉树，初始化为空，用来存储所构造的二叉树，并输入一棵树的先序序列和中序序列，并统计这个序列的长度。然后调用实现功能的函数。 void CreateBiTree(BiTree *T,char *pre,char *in,int len)（由先序序列和中序序列构造二叉树） 根据前序遍历的特点, 知前序序列(pre)的首个元素(pre[0])为根(root), 然后在中序序列(in)中查找此根(pre[0]), 根据中序遍历特点, 知在查找到的根(root) 前边的序列为左子树, 后边的序列为右子树。设根前边有n个元素，则又有, 在前序序列中，紧跟着根(root)的n个元素序列(即pre[1...n]) 为左子树, 在后边的为右子树，而构造左子树问题其实跟构造整个二叉树问题一样，只是此时前序序列为pre[1...n]), 中序序列为in[0...n-1], 分别为原序列的子串, 构造右子树同样。这里用递归实现！ int Depth(BiTree T)（求树的深度） 当所给的参数T是NULL时，返回0。说明这个树只有一个叶子节点深度为0，当所给的参数不是NULL时，函数调用自己看看这个参数的左分支是不是NULL， 源代码： //用来存储字符的结点类型 typedef struct CharNode { char c; struct CharNode *next; }CharNode; //用来存储数的结点类型 typedef struct IntNode { long double i; struct IntNode *next; }IntNode; //用来存储数的结点类型 typedef struct Node { long double n; struct Node_ys_char *next; }Node; //用来存储运算符的结点类型 typedef struct Node_ys_char { char c; struct Node_ys_char *next_c; struct Node *next; }Node_ys_char; char Precede(char x,char y)//运算符优先级判断{ int i,j; int from[5][5] ={ {0,0,-1,-1,0}, {0,0,-1,-1,0}, {1,1,0,0,1}, {1,1,0,0,1}, {0,0,-1,-1,0} };//定义一个二维数组存放算术符号的优先级 switch(x) { case '+':i=0;break; case '-':i=1;break; case '*':i=2;break; case '/':i=3;break; case '#':i=4;break; } switch(y) { case '+':j=0;break; case '-':j=1;break; case '*':j=2;break; case '/':j=3;break; case '#':j=4;break; } if(from[i][j]==1)//说明运算符i的优先级比j的优先级高return '>'; if(from[i][j]==-1) return '<'; else return '='; } //输入表达式，并对特殊情况做处理 CharNode *CreatRegister() { CharNode *top,*p,*q,*e; top=(CharNode *)malloc(sizeof(CharNode)); p=q=top; scanf("%c",&p->c); scanf("%c",&p->c);创建一个二叉树并输出三种遍历结果
全国计算机等级考试二级公共基础之树与二叉树1
数据结构实验二叉树
数据结构实验二——算术表达式求值实验报告
用栈和二叉树实现中缀表达式转后缀表达式构建计算机并求值实验报告
表达式用二叉树表示(1)
算术表达式求值演示程序
数据结构C语言实现二叉树三种遍历
第6章树和二叉树习题
算术表达式与二叉树课程设计
算术表达式与二叉树
基于二叉树结构的表达式求值算法
算术表达式求值课程设计报告
二叉树的建立及几种简单的遍历方法
c语言实现一.二叉树操作 二.用栈实现算术表达式求值 课设报告
C语言_算术表达式求值_代码
相关主题
文本预览