二叉树求表达式的值

.

（一）实验目的

本实验以二叉树的创建与访问算法设计作为实验内容，掌握树型结构的实现方法，培养解决负责问题的能力。

（二）实验内容

1、编写生成二叉树的函数，二叉树的元素从键盘输入；

2、编写在二叉树中输入表达方式的函数；

3、编写在二叉树中实现表达方式的值的函数；

4、编写遍历并输出二叉树的函数。

(三）实验要求

1、掌握树型结构的机器内表示；

2、掌握树型结构之上的算法设计与实现；

3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。

(四)实验设计思路

实验采用递归创建二叉树的表达,并实现了后序遍历二叉数表达式,既逆波兰表达式的输出,编写函数计算表达式的值,并输出。对实验题目进行细分,逐一实现函数预期的功能,如下图，先序输入创建二叉树表达式:+*-99##89##2##/66##3##

输出结果：42

实验报告

(一)部分算法流程图

1先序创建二叉树表达式

(五)程序清单

#i n c l u d e #i n c l u d e #i n c l u d e

#d e f i n e l e n 20 #d e f i n e N U L L 0

s t r u c t t r e e { c h a r d a t a [l e n ]; t r e e *l c h i l d ,*r c h i l d ;

};

v o i d c r e a t e t r e e(t r e e*&t r e)//创建二叉树

{

c h a r c h[l e n];

s c a n f("%s",c h);

g e t c h a r();

i f(s t r c m p(c h,"#")==0)t r e=N U L L;

e l s e

{

t r e=(t r e e*)m a l l o c(s i z e o f(t r e e));

s t r c p y(t r e->d a t a,c h);

c r e a t e t r e e(t r e->l c h i l d);

c r e a t e t r e e(t r e->r c h i l d);

}

}

v o i d i n p u t t r e e(t r e e*t r e)//输出二叉树

{

i f(t r e!=N U L L)

{

p r i n t f("%s",t r e->d a t a);

i f(t r e->l c h i l d!=N U L L||t r e->r c h i l d!=N U L L)

{

p r i n t f("(");

i n p u t t r e e(t r e->l c h i l d);

i f(t r e->r c h i l d!=N U L L)p r i n t f(",");

i n p u t t r e e(t r e->r c h i l d);

p r i n t f(")");

}

}

}

v o i d t r a v e r s e t r e e(t r e e*t r e)//后续遍历

{

i f(t r e!=N U L L)

{

t r a v e r s e t r e e(t r e->l c h i l d);

t r a v e r s e t r e e(t r e->r c h i l d);

p r i n t f("%s",t r e->d a t a);

}

}

v o i d i n o r d e r t r a v e r s(t r e e*t r e)//中续遍历{

i f(t r e!=N U L L)

{

t r a v e r s e t r e e(t r e->l c h i l d);

p r i n t f("%s",t r e->d a t a);

t r a v e r s e t r e e(t r e->r c h i l d);

}

}

d o u b l

e s o l u t i o n(t r e e*t r e)//二叉树表达式求值

{

i f(t r e->l c h i l d==N U L L&&t r e->r c h i l d==N U L L&&

t r e->d a t a[0]>='0'&&t r e->d a t a[0]<='9')

r e t u r n a t o f(t r e->d a t a);

e l s e

{

s w i t c h(t r e->d a t a[0])

{

c a s e'*':r e t u r n s o l u t i o n(t r e->l c h i l d)*s o l u t i o n(t r e->r c h i l d);

c a s e'-':r e t u r n s o l u t i o n(t r e->l c h i l d)-s o l u t i o n(t r e->r c h i l d);

c a s e'+':r e t u r n s o l u t i o n(t r e->l c h i l d)+s o l u t i o n(t r e->r c h i l d);

c a s e'/':r e t u r n

s o l u t i o n(t r e->l c h i l d)/s o l u t i o n(t r e->r c h i l d);

}

}

}

i n t m a i n()

{

t r e e*t r e;

d o u b l

e s u m;

i n t c h;

d o

{

p r i n t f("………………选择下面功能……………………\n");

p r i n t f(" 1.先序创建二叉数表达式\n");

p r i n t f(" 2.后序遍利二叉数表达式\n");

p r i n t f(" 3.求二叉数表达式的数值\n");

p r i n t f(" 4.中序遍利二叉数表达式\n");

p r i n t f(" 5.退出二叉数\n");

p r i n t f("……………………………………………………\n");

s c a n f("%d",&c h);

s w i t c h(c h)

{

c a s e1:

p r i n t f("输入创建的二叉树：\n");g e t c h a r();

c r e a t e t r e e(t r e);i n p u t t r e e(t r e);

p r i n t f("\n");b r e a k;

c a s e2:

p r i n t f("后序遍历的二叉树：\n");

t r a v e r s e t r e e(t r e);p r i n t f("\n");b r e a k;

c a s e3:

s u m=s o l u t i o n(t r e);p r i n t f("二叉树表达式

的值为=%l f\n",s u m);b r e a k;

c a s e4:

p r i n t f("中序遍历的二叉树：\n");

i n o r d e r t r a v e r s(t r e);p r i n t f("\n");b r e a k;

c a s e5:b r e a k;

}

}w h i l e(c h!=5);

r e t u r n0;

}

（六）实验结果

………………选择下面功能……………………

1.先序创建二叉数表达式

2.后序遍利二叉数表达式

3.求二叉数表达式的数值

5.退出二叉数……………………………………………………

1

输入创建的二叉树：

+

*

-

99

#

#

89

#

#

2

#

#

/

66

#

#

3

#

#

+(*(-(99,89),2),/(66,3))

………………选择下面功能……………………

1.先序创建二叉数表达式

2.后序遍利二叉数表达式

3.求二叉数表达式的数值

4.中序遍利二叉数表达式

5.退出二叉数……………………………………………………

2

后序遍历的二叉树：

9989-2*663/+

………………选择下面功能……………………

1.先序创建二叉数表达式

2.后序遍利二叉数表达式

3.求二叉数表达式的数值

4.中序遍利二叉数表达式

5.退出二叉数……………………………………………………

4

中序遍历的二叉树：

9989-2*+663/

………………选择下面功能……………………

2.后序遍利二叉数表达式

3.求二叉数表达式的数值

4.中序遍利二叉数表达式

5.退出二叉数

……………………………………………………

3

二叉树表达式的值为=42.000000

………………选择下面功能……………………

1.先序创建二叉数表达式

2.后序遍利二叉数表达式

3.求二叉数表达式的数值

4.中序遍利二叉数表达式

5.退出二叉数

……………………………………………………

5

请按任意键继续. . .

（七）实验遇到的问题

二叉树的递归创建只能先序创建吗？若采用中序或后序创建，必须先输入左子树，我们所定义二叉树往电脑输入时，必须有终止条件，比如if(strcmp(ch,"#")==0)tre=NULL;所以，一颗二叉树中序或后序建立时，必先输入左子树，而左子树是终止条件，所以，无法建立一颗二叉树。

表达式二叉树·实验代码

实验：表达式二叉树 实验要求： 建立表达式二叉树，并打印（可逆时针旋转90度打印，也可尝试正向打印） 以中缀表达式a*b+(c-d)/e-f 为例，建立以"-"号为根的表达式二叉树。 提示：若直接利用中缀表达式建立困难，可先将中缀表达式转化为后缀表达式（可利用栈中的中缀到后缀转化程序实现中缀表达式到后缀表达式的转换，再根据后缀表达式建立表达式二叉树，可参考栈中后缀表达式计算方法）。 实验代码： #include #include #include #include #include using namespace std; class tnode; void buildexptree(const string &exp); void printexptree(); int judgerank(char ch); bool isoperator(char ch); void test(); void setxy(tnode *tn, int y); int X = 0; int Y = 0; int depth = 0; vectorvt; class tnode{ public: char nodeV alue; int x, y; tnode *left; tnode *right;

tnode(){ x = 0; y = 0; } tnode(char &item, tnode *lptr = NULL, tnode *rptr = NULL): nodeV alue(item), left(lptr), right(rptr){ x = 0; y = 0; } }; tnode *myNode; bool cmp(tnode *t1, tnode *t2){ if(t1->y != t2->y) return (t1->y) > (t2->y); return (t1->x) < (t2->x); } class zpair{ //将operator和rank打包为一体,临时存储在stk2中public: char op; int rank; zpair(){} zpair(char _op, int _rank){ op = _op; rank = _rank; } }; int judgerank(char ch){ if(ch == '(') return -1; if(ch == '+' || ch == '-') return 1; if(ch == '*' || ch == '/') return 2; return 0; } bool isoperator(char ch){ if(ch == '(' || ch == ')' || ch == '+' || ch == '-' || ch == '*' || ch == '/') return true; else return false; }

波兰算法求二叉树表达式的值

逆波兰表达式 问题描述 逆波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2 + 3的逆波兰表示法为+ 2 3。逆波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2 + 3) * 4的逆波兰表示法为* + 2 3 4。本题求解逆波兰表达式的值，其中运算符包括+ - * / 四个。 输入数据 输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数 输出要求 输出为一行，表达式的值。 输入样例 * + 11.0 12.0 + 24.0 35.0 输出样例 1357.000000 #include #include #include "string.h" struct node { char data[20]; node *lChild,*rChild; }; int k=0; doubleCalculateEepress(node *root) { k++; if(root->data[0]>='0'&&root->data[0]<='9') return atof(root->data); else { switch(root->data[0]) { case '+': return CalculateEepress(root->lChild)+CalculateEepress(root->rChild); case '-': return CalculateEepress(root->lChild)-CalculateEepress(root->rChild); case '*': return CalculateEepress(root->lChild)*CalculateEepress(root->rChild); case '/': return CalculateEepress(root->lChild)/CalculateEepress(root->rChild); } } } voidconstructExpress(node *&root) { char sub[20];

第6章树和二叉树习题

第六章 树和二叉树 一、选择题 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 ）

算术表达式与二叉树

目录 一、系统开发的背景 (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

数据结构实验二叉树

实验六：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：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()函数。分解出原始中缀表达式中的操作数、操作符以及括号，保存在队列中，以本实验中的数据为例，分解完成后队列中的保存顺序如下图所示：

表达式用二叉树表示(1)

数据结构程序报告（3） 2011.3.29

2. 需求分析： （1）功能：表达式可以用二叉树表示，对于简单的四则运算，请实现以下功能【1】对于任意给出的前缀表达式（不带括号）、中缀表达式（可以带括号）或后缀表达式（不带括号），能够在计算机内部构造出一棵表达式二叉树，并且图示出来（图形的形式）。 【2】对于构造好的内部表达式二叉树，按照用户的要求输出相应的前缀表达式（不带括号）、中缀表达式（可以带括号，但不允许冗余括）或后缀表达式（不带括号）。 提示：所谓中缀表达式中的冗余括号，就是去掉括号后不影响表达式的计算顺序。例如：“（c+b）+a”中的括号是冗余的，可以表示成不冗余的“c+b+a”。 （2）输入输出要求：请输入字符串表达式： 树形二叉树（图形显示） 中缀表达式为： 前缀表达式为： 后缀表达式为： 3.概要设计：（算法） 分成两部分完成： 【1】前缀、中缀、后缀表达式->二叉树表达式 前缀表达式->二叉树表达式：（a）碰到操作数则把其值赋给相应的新申请的二叉树结点，地址压栈；（b）碰到操作符则把其值赋给相应的新申请的二叉树，并从栈中弹出两个地址，分别作为其右指针和左指针，然后再把其地址压栈，最后一个地址即为二叉树的根结点地址。 中缀表达式->二叉树表达式：把中缀表达式转换成后缀表达式，然后再建立二

叉树。 后缀表达式->二叉树表达式：（a）碰到操作数则把其值赋给相应的新申请的二叉树结点，若栈为空则地址压栈，若非空则取栈顶元素，若栈顶元素的左孩子为空则当前结点设为其左孩子，左孩子为满则设为其右孩子再压栈；（b）碰到操作数则把其值赋给相应的新申请的二叉树结点，取栈顶元素，若栈顶元素的左孩子为空则设为其左孩子，左孩子为满则设为其右孩子开始那个元素地址为根结点地址，开始时用变量root保存。 【1】二叉树表达式->前缀、中缀、后缀表达式 二叉树表达式->前缀表达式：对二叉树表达式进行前序遍历。 二叉树表达式->中缀表达式：对二叉树表达式进行中序遍历，若结点操作符的优先级高于其左或右子树，在打印相应的子树之前先打印开括号，在打印相应的子树最后在打印一个闭括号。 二叉树表达式->后缀表达式：对二叉树表达式进行后序遍历。

C语言二叉树运算

#include #include typedef struct bitnode { char data; struct bitnode *lchild; struct bitnode *rchild; }bitnode,*bitree; bitree createbitree(bitree &T){ char ch; printf("输入结点值ch="); scanf("%c",&ch); scanf("%c",&ch); if(ch!='#'){ if(!(T=(bitnode*)malloc(sizeof(bitnode)))) return 0; T->data=ch; T->lchild=NULL; T->rchild=NULL; createbitree(T->lchild); createbitree(T->rchild); } return T; } void preorder(bitree &p) { if(p) { printf("%c",p->data); if(p->lchild!=NULL) preorder(p->lchild); if(p->rchild!=NULL) preorder(p->rchild); }else printf("NULL"); } void inorder(bitree &p) { if(p) {

if(p->lchild!=NULL) inorder(p->lchild); printf("%c",p->data); if(p->rchild!=NULL) inorder(p->rchild); } } void postorder(bitree &p) { if(p) { if(p->lchild!=NULL) postorder(p->lchild); if(p->rchild!=NULL) postorder(p->rchild); printf("%c",p->data); } } int number(bitree &bt){ int n1,n2; if(!bt)return 0; if(!bt->lchild&&!bt->rchild) return 1; n1=number(bt->lchild); n2=number(bt->rchild); return(n1+n2+1); } int leafs(bitree &bt){ int n1,n2; if(!bt) return 0; if(!bt->lchild&&!bt->rchild) return 1; n1=leafs(bt->lchild); n2=leafs(bt->rchild); return n1+n2; } int height(bitree &bt){ int h1,h2; if(!bt) return 0;

算术表达式与二叉树课程设计

山西大学 课程设计任务书 设计题目算术表达式与二叉树 所属课程：数据结构 系别软件学院 专业软件工程 班级软工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 #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW 0 typedef int Status; 2、表达式的抽象数据类型定义 ADT Expression{ 数据对象D：D是具有数值的常量C和没有数值的变量V； 数据关系：R={<(V或者C)P(V或者C)>|V,C∈D, <(V或者C)P(V或者C)>表示由运算符P结合起来的表达式E} 基本操作： Status Input_Expr(&string,flag) 操作结果：以字符序列的形式输入语法正确的前缀表达式，保存到字符串string； 参数flag表示输出的提示信息是什么，输入成功返回OK，否则，返回ERROR。 void judge_value(&E,&string,i) 初始条件：树E存在，表达式的前缀字符串string存在； 操作结果：判断字符string[i]，如果是'0'-'9'常量之间，二叉树结点E存为整 型；否则，存为字符型。 Status ReadExpr(&E,&exprstring) 初始条件：表达式的前缀形式字符串exprstring存在； 操作结果：以正确的前缀表示式exprstring并构造表达式E，构造成功，返回OK， 否则返回ERROR。 Status Pri_Compare(c1,c2)

表达式二叉树

数据结构与算法实习报告第4次上机实习报告

2 数据结构与算法实习报告 诚信保证：我保证没有抄袭他人作业！问题部分 1.1 问题描述 【1】对于任意给出的前缀表达式（不带括号）、中缀表达式（可以带括号）或后缀表达式（不带括号），能够在计算机内部构造出一棵表达式二叉树，并且图示出来（图形的形式）。 【2】对于构造好的内部表达式二叉树，按照用户的要求输出相应的前缀表达式（不带括号）、中缀表达式（可以带括号，但不允许冗余括）或后缀表达式（不带括号）。 （2）输入输出要求： 请输入表达式类型；请输入表达式类型，前缀表达式输入-1，中缀表达式输入0，后缀表达式输入1. 请输入字符串表达式： 树形二叉树（图形显示） 中缀表达式为： 前缀表达式为： 后缀表达式为： 1.2 问题分析 一、前缀、中缀、后缀表达式->二叉树表达式

数据结构实习报告前缀表达式->二叉树表达式：从后往前扫描 （a）碰到操作数则把其值赋给相应的新申请的二叉树结点，地址压栈； （b）碰到操作符则把其值赋给相应的新申请的二叉树，若栈非空，从栈中弹出一个地址，则栈顶指针所指结点设置成当前结点左孩子，若栈非空，再从栈中弹出一个地址，则栈顶指针所指结点设置成当前结点右孩子，操作完毕后把当前节点压栈，最后一个地址即为二叉树的根结点地址。 中缀表达式->二叉树表达式：把中缀表达式转换成后缀表达式，然后再建立二叉树。 后缀表达式->二叉树表达式：从前往后扫描 （a）碰到操作数则把其值赋给相应的新申请的二叉树结点，若栈为空则地址压栈， （b）碰到操作符则把其值赋给相应的新申请的二叉树结点，若当前元素的左孩子为空则设为其左孩子，左孩子为满则设为其右孩子,开始那个元素地址为根结点地址，开始时用变量root保存。 二、二叉树表达式->前缀、中缀、后缀表达式 二叉树表达式->前缀表达式：对二叉树表达式进行前序遍历。 二叉树表达式->中缀表达式：对二叉树表达式进行中序遍历，如果当前节点的左子树是运算符，且运算符优先级低于当前运算符，那么左边的表达式要先计算，需要加括号，否则直接输出左子树；如果当前节点的右子树是运算符，且运算符优先级不高于当前运算符，那么右边的表达式要先计算，需要加括号，狗则直接输出右子树。

基于二叉树结构的表达式求值算法

实验报告 课程名称： 程序设计与数据结构 指导老师： 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 #include #include #define EXP_LEN 100 //定义表达式的最大长度 #define DATA_LEN 20 //定义每个操作数的最大长度 typedef struct BiTNode { int dflag; //标志域,值为1,data[]存放操作运算符;值为0,data[]存放操作数char data[DATA_LEN + 1]; //数据域,存放:操作运算符或操作数 struct BiTNode *lchild, *rchild; //分别指向结点的左、右子树 }BiTNode, *BiTree; //定义二叉树结点及二叉树类型指针 int CreateBiTree(BiTree &bt, char *p, int len); //创建二叉树,并用bt返回树的根地址,p为表达式的首地址,l为表达式的长度 int Calculate(BiTree bt, double &rst); //计算表达式的值,bt为据表达式创建的二叉树,用rst返回表达式的值 int PreOrderTraverse(BiTree bt);//先序遍历二叉树bt,输出先序遍历序列 int InOrderTraverse(BiTree bt); //中序遍历二叉树bt,输出中序遍历序列 int PostOrderTraverse(BiTree bt); //后序遍历二叉树bt,输出后序遍历序列 int DestroyBiTree(BiTree &bt); //销毁二叉树 //二叉树结构的表达式求解算法入口

15算术表达式与二叉树

《数据结构与算法》课程设计任务书 题目：算术表达式与二叉树 学生姓名：学号： 班级： 题目类型：软件工程（R）指导教师： 一．题目简介 一个表达式和一棵二叉树之间，存在着自然的对应关系。本设计要求学生编程实现基于二叉树表示的算术表达式的操作。通过该题目的设计过程，可以加深理解树及二叉树的逻辑结构、存储结构以及递归算法设计的基本原理，掌握树及二叉树上基本运算的实现。进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。 二．主要任务 第一部分：基本算法实现 1、线性结构基本算法实现（指导老师根据题目指定）； 2、树型结构基本算法实现（指导老师根据题目指定）； 3、图型结构基本算法实现（指导老师根据题目指定）； 4、查找基本算法实现（指导老师根据题目指定）； 5、排序基本算法实现（指导老师根据题目指定）； 第二部分：指定题目的设计与实现 1、查阅文献资料，一般在3篇以上； 2、建立数据的逻辑结构和物理结构； 3、完成相应算法的设计； 4、完成测试工作；

5、撰写设计说明书； 6、做好答辩工作。 三．主要内容、功能及技术指标 假设算术表达式Expression内可以含有变量（a～z）、常量（0～9）和二元运算符（+，-，*，/，^(乘幂)）。实现以下操作： （1）ReadExpre(E)—以字符序列的形式输入语法正确的前缀表达式并构造表达式E。 （2）WriteExpre(E)—用带括弧的中缀表达式输出表达式E。 （3）Assign(V,c)—实现对变量V的赋值（V=c），变量的初值为0。 （4）Value(E)—对算术表达式E求值。 （5）CompoundExpr（P，E1，E2）--构造一个新的复合表达式（E1）P（E2）（6）算法对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；对算法实现过程中的异常情况能给出有效信息； （7）较高要求：实现图形化操作界面。 四．提交的成果 1. 设计说明书一份，内容包括： 1) 中文摘要100字；关键词3-5个； 2) 序言； 3）采用类c语言定义相关的数据类型 4）各模块的伪码算法 5）函数的调用关系图 6）调试分析 a、调试中遇到的问题及对问题的解决方法； b、算法的时间复杂度和空间复杂度。 7）测试结果 8）源程序（带注释）

c语言实现一.二叉树操作 二.用栈实现算术表达式求值 课设报告

目录 题目一.二叉树操作（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，

四则运算表达式求值(栈+二叉树,c++版)

HUNAN UNIVERSITY 课程实习报告 题目：四则运算表达式求值 学生姓名：周华毅 学生学号：201308010411 专业班级：计科1304 指导老师：吴帆 完成日期：2015/5/1

一、需求分析 a)四则运算表达式求值，将四则运算表达式用中缀表达式表示，然后转换为后缀表达 式，并计算结果。 b)本程序要求利用二叉树后序遍历来实现表达式的转换，同时可以使用实验2的结 果来求解后缀表达式的值。 c)在字符界面上输入一个中缀表达式，回车表示结束。如果该中缀表达式正确，那么 在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔 开；如果不正确，在字符界面上输出表达式错误提示。 d)测试数据 输入： 21+23*（12-6） 输出： 21 23 12 6 -*+ 二、概要设计 抽象数据类型 为实现上述程序的功能，应以字符串存储用户的输入，以及计算出的结果。 算法的基本思想 根据题目要求，利用二叉树后序遍历来实现表达式的转换。该算法的基本模块包括二叉树的建立以及如何把输入的中缀表达式利用二叉树后序遍历转化为后缀表达式。 1、首先要将输入的中缀表达式（数字字符）存入到二叉树中，由于存在两位或者两位以上的数，甚至还有小数，所以考虑用字符型指针存储数字字符和操作符。 2、为了便于将中缀表达式存入二叉树中，在录入中缀表达式后，要进行相应的处理，比如去掉空格符，添加结束标志，如‘=’、‘#’等。 3、中缀表达式存入到二叉树的过程中，要注意处理的顺序，如‘+’、‘-’号的优先级比‘*’、‘/’号的低，当遇到‘*’、‘/’号时，要判断树以上的节点中是否有‘+’、‘-’号，有的话要与其交换位置。遇到‘（’时要反复创建二叉树的结点，构建子二叉树，考虑到括号内要处理的步骤可能会较多，可以考虑用递归。遇到‘）’时则直接结束此子二叉树的建立。此外二叉树中叶子结点存储操作数，非叶子结点存储操作码。 4、对创建好的二叉树进行后序遍历，即可得到相应的后缀表达式，实现方法可以用递归的方式，由于后面还要计算表达式的值，故便利的过程中要将结点中得到的数据存入新的字符数组中。 程序的流程 程序由三个模块组成： （1）输入模块：完成一个中缀表达式的输入，存入字符串数组array[Max]中。 （2）计算模块：设计一个建立二叉树的函数，Node* crtTree(Node* root)，传入根结点指针，返回根结点指针，该函数的实现还要反复使用另一个函数char getOp(Node *temp)，其将数字字符存入一个结点，并返回数字字符的后一 个符号。void deal()函数功能是对字符数组进行处理。void output(Node *root); 函数功能是获得处理后的字符串，也就是中缀表达式转化为的后 缀表达式。 （3）输出模块：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式和表达式的值；如果不正确，在字符界面上输出表达式错误提示。 三、详细设计

实验二叉树及其应用(严选材料)

实验6：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：a+b*(c-d)-e/f 三、实验要求 1、 如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算 a) 统计叶子结点的个数。 b) 求二叉树的深度。 2、 十进制的四则运算的计算器可以接收用户来自键盘的输入。 3、 由输入的表达式字符串动态生成算术表达式所对应的二叉树。 4、 自动完成求值运算和输出结果。 四、实验环境 PC 微机 DOS 操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 1、根据二叉树的各种存储结构建立二叉树； 2、设计求叶子结点个数算法和树的深度算法； 3、根据表达式建立相应的二叉树，生成表达式树的模块； - + / a * b - e f C d

4、根据表达式树，求出表达式值，生成求值模块； 5、程序运行效果，测试数据分析算法。 六、功能分析 存储结构 typedef union{ int Operator; // 操作符 float Operand; // 操作数 }Int_Float; //表达式树 typedef struct BinaryTreeNode{ Int_Float Data; //数据域 int IsOperator; //判断是不是操作数的标志位 struct BinaryTreeNode *RChild;//左子树 struct BinaryTreeNode *LChild;//右子树 }BiTreeNode, *lpBiTreeNode; //栈的定义 typedef struct { lpBiTreeNode *base; lpBiTreeNode *top; int stacksize; }SqStack; 函数一览表 lpBiTreeNode GetTop( SqStack s );//取栈顶结点函数 int IsEmpty( SqStack s );//判空函数 int InitStack( SqStack &s );//初始化栈函数 int Pop( SqStack &s, lpBiTreeNode &e );//出栈函数 int Push( SqStack &s, lpBiTreeNode e );//入栈函数 int In( int c, int* op );// 判断c是否在op中 int Precede( int theta1, int theta2 );//比较运算符号的优先级 int isNum( int c );//判断是不是数 int GetInput(Int_Float *Result);//读入输入的数 lpBiTreeNode CreateBiTree();//创建二叉树 bool calculate(lpBiTreeNode Root, float *result);//计算二叉树化表达式的值int getLeafNum(lpBiTreeNode Root);//计算二叉树的叶子结点数

树和二叉树习题)

第6章 树和二叉树 一、选择题 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（ 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 ．以上答案都不对(501) 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. 2k 14．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( C )次序的遍历实现编号。 A ．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 15．一棵二叉树的前序遍历序列为ABCDEFG ，它的中序遍历序列可能是（ B ） A ．CABDEFG B ．ABCDEFG C ．DACEFBG D ．ADCFEG

中缀表达式表示成二叉树

将一个中缀表达式表示成二叉树的形式，相关提示如下： （1）基本思路：中缀先转换成后缀，然后再表示成二叉树。这样做起来要方便的多；（2）打印二叉树时，可以用课件上的逆时针旋转90度打印方式。 #include #include #include"d_except.h" using namespace std; #ifndef STACK #define STACK const MAXSTACKSIZE=50; template class stack //有限栈 { public: stack(); void push(const T& item); void pop(); T& top(); const T& top() const; bool empty() const; bool full() const; int size() const; private: T stackList[MAXSTACKSIZE]; int topIndex; }; template stack::stack(){topIndex=-1;} template void stack::push(const T& item) { if(full()) throw underflowError("miniStack top():stack empty");//exit(1); topIndex++; stackList[topIndex]=item; } template void stack::pop() { if (empty()) throw underflowError("miniStack top(): stack empty");