表達(dá)式與二叉樹的相互轉(zhuǎn)換

摘要:數(shù)學(xué)表達(dá)式、棧的操作、二叉樹的遍歷，這幾個(gè)概念在數(shù)據(jù)結(jié)構(gòu)的教材中是不可缺少的。數(shù)學(xué)表達(dá)式求值是程序設(shè)計(jì)語言編譯中的一個(gè)最基本問題，也是棧應(yīng)用的一個(gè)典型例子，用它來研制出各種類型的電子計(jì)算器(前綴計(jì)算器、中綴計(jì)算器(常見的計(jì)算器)、后綴計(jì)算器)。在數(shù)據(jù)結(jié)構(gòu)中沒有解決表達(dá)式與二叉樹之間的相互轉(zhuǎn)換關(guān)系，也就是說不能由一種表達(dá)式迅速地得到另外的兩種表達(dá)式，也就難于解決其他兩種計(jì)算器的研制過程。本文旨在研究表達(dá)式與二叉樹間的相互轉(zhuǎn)換關(guān)系，便于由一種表達(dá)式(或表達(dá)式樹)迅速求出其他的表達(dá)式，再通過棧的應(yīng)用(操作)研制出三種不同的計(jì)算器(棧的應(yīng)用在數(shù)據(jù)結(jié)構(gòu)的教材中都有，在此文中不予介紹)。

關(guān)鍵詞:表達(dá)式;波蘭式;逆波蘭式;二叉樹的遍歷;表達(dá)式樹

中圖分類號(hào):TP3 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1009-3044(2010)05-1201-03

The Mutual Conversion Between an Expression and a Binary Tree

HE Zhi-hong1， MAO Zhi-jun2

(1.Guangzhou Kangda Institute of South China Normal University， Guangzhou 510000， China; 2.Guangzhou Vocational School of Tourism and Business， Guangzhou 510515， China)

Abstract: The concepts such as mathematical expression， stack operation and binary tree traversal must be presented in data structure. Evaluation 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.

Key words: expression; polish notation; reverse polish notation; binary tree traversal; expression tree

1 概述

數(shù)學(xué)表達(dá)式求值是程序設(shè)計(jì)語言編譯中的一個(gè)最基本問題。因此，數(shù)學(xué)表達(dá)式、棧的操作、二叉樹的遍歷，這幾個(gè)概念在數(shù)據(jù)結(jié)構(gòu)的教材中往往經(jīng)常出現(xiàn)。表達(dá)式的求值過程是棧應(yīng)用的一個(gè)典型例子，用它來研制出電子計(jì)算器:當(dāng)用戶輸入一個(gè)由數(shù)據(jù)(操作數(shù))和運(yùn)算符組成的算術(shù)表達(dá)式，計(jì)算器使用一個(gè)堆棧來計(jì)算運(yùn)算結(jié)果。當(dāng)然表達(dá)式也有幾種形式:前綴表達(dá)式、中綴表達(dá)式、后綴表達(dá)式。因此，又出現(xiàn)了前綴計(jì)算器、中綴計(jì)算器(常見的計(jì)算器)、后綴計(jì)算器。對于中綴表達(dá)式就是我們常用的數(shù)學(xué)表達(dá)式中去掉括號(hào)的部分表達(dá)式，是經(jīng)常可看見的;但是，前綴表達(dá)式和后綴表達(dá)式是怎么得出來的呢?我們的數(shù)據(jù)結(jié)構(gòu)教材中是將一個(gè)數(shù)學(xué)表達(dá)式或者中綴表達(dá)式以及其所表示的二叉樹，對該二叉樹的前序遍歷得到前綴表達(dá)式，對該二叉樹的中序遍歷就得到中綴表達(dá)式，對該二叉樹的后序遍歷就得到后綴表達(dá)式，再根據(jù)這些表達(dá)式用堆棧來實(shí)現(xiàn)，以得到不同的計(jì)算器。也就是說，教材中所闡述的過程是這樣的:數(shù)學(xué)表達(dá)式(中綴表達(dá)式)+該表達(dá)式的二叉樹→二叉樹的遍歷→前綴表達(dá)式、中綴表達(dá)式、后綴表達(dá)式→棧的實(shí)現(xiàn)→前綴計(jì)算器、普通計(jì)算器、后綴計(jì)算器。用圖形表示其過程如下:

初看起來顯然是比較合理的，但是我們的教材上從來沒有提到過怎樣得到該“數(shù)學(xué)表達(dá)式”的“二叉樹”。本文正想闡明怎樣由一個(gè)“表達(dá)式”得出其相應(yīng)的“二叉樹”。

2 相關(guān)術(shù)語

2.1 中綴表達(dá)式

就是運(yùn)算符(操作符)在兩個(gè)運(yùn)算對象(操作數(shù))中間的表達(dá)式。如:A+B，C*D-E。

2.2 前綴表達(dá)式

就是在一個(gè)數(shù)學(xué)表達(dá)式中，運(yùn)算符(操作符)在兩個(gè)運(yùn)算對象(操作數(shù))之前的表達(dá)式。如:+AB，-*CDE。前綴表達(dá)式又稱波蘭式(PN，Polish Notation)。

2.3 后綴表達(dá)式

就是在一個(gè)數(shù)學(xué)表達(dá)式中，運(yùn)算符(操作符)在兩個(gè)運(yùn)算對象(操作數(shù))之后的表達(dá)式。如:AB+， CD*E-。后綴表達(dá)式又稱逆波蘭式(RPN，Reverse Polish Notation)。

2.4 表達(dá)式樹

就是將一個(gè)數(shù)學(xué)表達(dá)式用一棵二叉樹表示。其中，運(yùn)算對象作為樹的葉子結(jié)點(diǎn)(沒有后繼的結(jié)點(diǎn))，運(yùn)算符作為樹的非葉子結(jié)點(diǎn)。如圖1，圖2所示。

2.5 二叉樹的三種遍歷

1) 先根(先序)遍歷:先遍歷根結(jié)點(diǎn)，再先根遍歷左子樹，再先根遍右子樹。對于上面的圖1、圖2分別為:+AB，-*CDE。得到相應(yīng)表達(dá)式的前綴表達(dá)式(波蘭式(PN，Polish Notation))。

2) 中根(中序)遍歷:先中根遍歷左子樹，訪問根結(jié)點(diǎn)，中根遍歷右子樹。對于上面的圖1、圖2分別為:A+B，C*D-E。得到相應(yīng)表達(dá)式的中綴表達(dá)式。

3) 后根(后序)遍歷:先后根遍歷左子樹，再后根遍歷右子樹，最后訪問根結(jié)點(diǎn)。對于上面的圖1、圖2分別為:AB-，CD*E-。得到相應(yīng)表達(dá)式的后綴表達(dá)式(逆波蘭式(RPN，Reverse Polish Notation))。

3 數(shù)學(xué)表達(dá)式轉(zhuǎn)換到表達(dá)式樹(二叉樹)

將數(shù)學(xué)表達(dá)式表示為表達(dá)式樹，關(guān)鍵問題是:最后進(jìn)行運(yùn)算的運(yùn)算符作為二叉樹(表達(dá)式樹)的樹根，以該運(yùn)算符作為界線，在其前面的部分(這里稱子表達(dá)式1)為二叉樹的左子樹的表達(dá)式，在運(yùn)算符后面的部分(這里稱子表達(dá)式2)為右子樹的表達(dá)式，再分別對子表達(dá)式1、子表達(dá)式2遞歸使用以上規(guī)則構(gòu)建左、右子樹。

例如:將表達(dá)式:((a+b)+c*(d+e)+f)*(g+h)表示成表達(dá)樹。

其構(gòu)造過程如下:

首先，先確定二叉的根。根據(jù)數(shù)學(xué)運(yùn)算順序知:“g”前面的“*”是最后運(yùn)算的運(yùn)算符，因此該“*”作為二叉樹的樹根如圖3。子表達(dá)式1為:(a+b)+c*(d+e)+f;子表達(dá)式2為:g+h。分別遞歸構(gòu)造左、右子樹。

其次，構(gòu)造二叉樹的左子樹。根據(jù)子表達(dá)式1:(a+b)+c*(d+e)+f，分析知:f前的“+”為整個(gè)左子樹的樹根，f為左子樹的右子樹。

再分析其左子樹部分:(a+b)+c*(d+e) 如圖5。

子表達(dá)式1 :(a+b)+c*(d+e)+f 所構(gòu)成的左子樹為圖6。

再次，構(gòu)造二叉樹的右子樹。由子表達(dá)式2:g+h，分析知:右子樹的根為:“+”，右子樹的左葉子為“g”，而右葉子為:“h”。

從而得如圖7。

根據(jù)圖3、圖6和圖7。得出表達(dá)式:((a+b)+c*(d+e)+f)*(g+h)的表達(dá)式樹為圖8。

對圖8的前根遍歷得:*+++ab*c+bef+gh.。即表達(dá)式:((a+b)+c*(d+e)+f)*(g+h)的前綴表達(dá)式(波蘭式)為:*+++ab*c+bef+gh.。

對圖8的中根遍歷得:a+b+c*d+e+f*g+h。即表達(dá)式:((a+b)+c*(d+e)+f)*(g+h)的中綴表達(dá)式為:a+b+c*d+e+f*g+h。

對圖8的后根遍歷得:ab+cde+*+f+gh+*。即表達(dá)式:((a+b)+c*(d+e)+f)*(g+h)的后綴表達(dá)式(逆波蘭式)為:ab+cbe+*+f+gh+*。

4 前綴算術(shù)表達(dá)式(波蘭式)到表達(dá)式樹。

由于前綴算術(shù)表達(dá)式(波蘭式)的運(yùn)算符(操作符)在兩個(gè)操作數(shù)(操作對象)之前，非葉子結(jié)點(diǎn)全為運(yùn)算符。因此，可按如下規(guī)則進(jìn)行構(gòu)造二叉樹(表達(dá)式樹):

第一個(gè)運(yùn)算符作為二叉樹的樹根;緊接著選擇其后第一次滿足運(yùn)算符個(gè)數(shù)比操作數(shù)個(gè)數(shù)少1的部分表達(dá)式作為左子樹的表達(dá)式;剩下的部分表達(dá)式為右子樹的表達(dá)式。再分別對分出的兩表達(dá)式遞歸使用以上規(guī)劃。

例2:寫出前綴表達(dá)式:-*a^b-+c*defg的表達(dá)式樹。

解題過程如下:

第一個(gè)“-”為樹根:如圖9。

根據(jù)以上規(guī)則:左子樹部的表達(dá)式為:*a^b-+c*def;右子樹部分的表達(dá)式為:g。

構(gòu)造左子樹:左子樹樹根為:“*”，“*”的左子樹為“a”如圖9;右子樹表達(dá)式為:^b-+c*def。遞歸構(gòu)造可得如圖10。

將圖10、圖11組合得左子樹為:圖12。

再由圖9、圖12以及右子樹“g”得“-*a^b-+c*defg”的表達(dá)式樹為圖13。

對該樹后序遍歷可得后綴表達(dá)式(逆波蘭式):abcde*+f-^*g-。

同樣對該樹中序遍歷可得中綴表達(dá)式:a*b^c+d*e-f-g。

當(dāng)然真正的數(shù)學(xué)表達(dá)式為:a*(b^((c+d*e)-f))-g

5 由后綴表達(dá)式(逆波蘭式)到表達(dá)式樹

由于后綴算術(shù)表達(dá)式(逆波蘭式)的運(yùn)算符(操作符)在兩個(gè)操作數(shù)(操作對象)之后，非葉子結(jié)點(diǎn)全為運(yùn)算符。因此，可按如下規(guī)則進(jìn)行構(gòu)造二叉樹:

最后一個(gè)運(yùn)算符作為二叉樹的樹根;緊接著從后往前選擇第一次滿足運(yùn)算符個(gè)數(shù)比操作數(shù)個(gè)數(shù)少1的部分表達(dá)式作為右子樹部分的表達(dá)式;剩下的部分表達(dá)式為左子樹的表達(dá)式。再分別對兩表達(dá)式遞歸使用以上規(guī)劃;對于簡單表達(dá)式(一個(gè)運(yùn)算符，兩個(gè)運(yùn)算對象)從后往前分別是:根、右孩子、左孩子的順序構(gòu)造。

例3:用后綴表達(dá)式:ab+cde+*+f+gh+*構(gòu)造表達(dá)式樹，并求出其前綴和中綴表達(dá)式。

解:第一步:根據(jù)以上規(guī)則:最后一個(gè)“*”為樹根; 如圖14。

“gh+”為表達(dá)式樹的右子樹部分的表達(dá)式;

“ab+cde+*+f+”為表達(dá)式樹左子樹部分的表達(dá)式。

第二步:右子樹為:根為:“+”;右孩子為:“h”;

左孩子為:“g”;如圖15。

第三步:左子樹為:根為:“+”;右子樹為:“f”

如圖16， 其左子樹的表達(dá)式為:

“ab+cde+*+”;再對“ab+cde+*+”

構(gòu)造子二叉樹。由上規(guī)則得:該子二叉樹的根為:“+”，右子樹部分的表達(dá)式為:“cde+*”;左子樹部分的表達(dá)式為:“ab+”，即如右圖17。

綜合上面四個(gè)圖，表達(dá)式“ab+cde+*+f+gh+*”的二叉樹為如圖18所示。

因此，對該二叉樹的前序遍歷可得波蘭式:*+++ab*c+def+gh.。對該二叉樹中序遍歷可得中綴表達(dá)式:a+b+c*d+e+f*g+h.。當(dāng)然真正的數(shù)學(xué)表達(dá)式為:(a+b+c*(d+e)+f)*(g+h)。

6 小結(jié)

運(yùn)用該文中所介紹的三種表達(dá)式與二叉樹的轉(zhuǎn)換規(guī)則，能順利地由一種表達(dá)式將其轉(zhuǎn)化為二叉樹(表達(dá)式樹)，再對該二叉樹(表達(dá)式樹)的遍歷，可得到其他的兩種表達(dá)式，最后將這些表達(dá)式用于棧的操作可研制出三種不同的計(jì)算器(前綴計(jì)算器、中綴計(jì)算器(常見的計(jì)算器)和后綴計(jì)算器);為教師和學(xué)生在解答數(shù)據(jù)結(jié)構(gòu)(或編譯原理)中由一種表達(dá)式得出其他兩種表達(dá)式的題目提供了一種構(gòu)思;進(jìn)一步完善了數(shù)學(xué)表達(dá)式、棧的應(yīng)用、二叉樹的遍歷這三者之間的關(guān)系的轉(zhuǎn)換過程。本文中所介紹的規(guī)則構(gòu)思巧妙，但通俗易懂，實(shí)用性強(qiáng)。

參考文獻(xiàn):

[1] 晉良穎.數(shù)據(jù)結(jié)構(gòu)[M].北京:人民郵電出版社，2002.

[2] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社，1997.

[3] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)題集[M].北京:清華大學(xué)出版社，1999.

[4] 王開鑄，俞經(jīng)善.C語言數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)[M].哈爾濱:哈工大出版社，2003