表达式与二叉树的相互转换

The Mutual Conversion Between an Expression and a Binary Tree

数学表达式、栈的操作、二又树的遍历，这几个概念在数据结构的教材中是不可缺少的。数学表达式求值是程序设计语言编译中的一个最基本问题，也是栈应用的一个典型例子，用它来研制出各种类型的电子计算器（前缀计算器、中缀计算器（常见的计算器）、后缀计算器）。在数据结构中没有解决表达式与二又树之间的相互转换关系，也就是说不能由一种表达式迅速地得到另外的两种表达式，也就难于解决其他两种计算器的研制过程。本文旨在研究表达式与二叉树间的相互转换关系，便于由一种表达式（或表达式树）迅速求出其他的表达式，再通过栈的应用（操作）研制出三种不同的计算器（栈的应用在数据结构的教材中都有，在此文中不予介绍）。

The concepts such as mathematical expression, stack operation and binary tree traversal must be presented in data structure. Eval- uation of a mathematical expression is not only a basic problem in a programming language compiling, but also a typical example of stack application which could be used to develop all kinds of calculators （prefix calculator, infix calculator and postfix calculator）. Mutual conversions between an expression and a binary tree remain unsolved in data structure, that is to say, it is impossible to obtain two kinds expressions from one expression. So it is difficult to work out the process of developing another two calculators. This paper discusses the mutual conversion between an expression and a binary tree SO as to workout the other expressions from one expression and develop three kinds of different calculators with stack application.