解析樹(shù)

完成樹(shù)的實(shí)現(xiàn)之后，現(xiàn)在我們來(lái)看一個(gè)例子，告訴你怎么樣利用樹(shù)去解決一些實(shí)際問(wèn)題。在這個(gè)章節(jié)，我們來(lái)研究解析樹(shù)。解析樹(shù)常常用于真實(shí)世界的結(jié)構(gòu)表示，例如句子或數(shù)學(xué)表達(dá)式。

圖 1：一個(gè)簡(jiǎn)單句的解析樹(shù)

圖 1 顯示了一個(gè)簡(jiǎn)單句的層級(jí)結(jié)構(gòu)。將一個(gè)句子表示為一個(gè)樹(shù)，能使我們通過(guò)利用子樹(shù)來(lái)處理句子中的每個(gè)獨(dú)立的結(jié)構(gòu)。

圖 2： ((7+3)*(5−2)) 的解析樹(shù)

如圖 2 所示，我們能將一個(gè)類似于 ((7+3)*(5−2)) 的數(shù)學(xué)表達(dá)式表示出一個(gè)解析樹(shù)。我們已經(jīng)研究過(guò)全括號(hào)表達(dá)式，那么我們?cè)鯓永斫膺@個(gè)表達(dá)式呢？我們知道乘法比加或者減有著更高的優(yōu)先級(jí)。因?yàn)槔ㄌ?hào)的關(guān)系，我們?cè)谧龀朔ㄟ\(yùn)算之前，需要先計(jì)算括號(hào)內(nèi)的加法或者減法。樹(shù)的層級(jí)結(jié)構(gòu)幫我們理解了整個(gè)表達(dá)式的運(yùn)算順序。在計(jì)算最頂上的乘法運(yùn)算前，我們先要計(jì)算子樹(shù)中的加法和減法運(yùn)算。左子樹(shù)的加法運(yùn)算結(jié)果為 10，右子樹(shù)的減法運(yùn)算結(jié)果為 3。利用樹(shù)的層級(jí)結(jié)構(gòu)，一旦我們計(jì)算出了子節(jié)點(diǎn)中表達(dá)式的結(jié)果，我們能夠?qū)⒄麄€(gè)子樹(shù)用一個(gè)節(jié)點(diǎn)來(lái)替換。運(yùn)用這個(gè)替換步驟，我們得到一個(gè)簡(jiǎn)單的樹(shù)，如圖 3 所示。

圖 3： ((7+3)*(5−2)) 的化簡(jiǎn)后的解析樹(shù)

在本章的其余部分，我們將更加詳細(xì)地研究解析樹(shù)。尤其是：

怎樣根據(jù)一個(gè)全括號(hào)數(shù)學(xué)表達(dá)式來(lái)建立其對(duì)應(yīng)的解析樹(shù)

怎樣計(jì)算解析樹(shù)中數(shù)學(xué)表達(dá)式的值

怎樣根據(jù)一個(gè)解析樹(shù)還原數(shù)學(xué)表達(dá)式

建立解析樹(shù)的第一步，將表達(dá)式字符串分解成符號(hào)保存在列表里。這里有四種符號(hào)需要我們考慮：左括號(hào)，操作符和操作數(shù)。我們知道讀到一個(gè)左括號(hào)時(shí)，我們將開(kāi)始一個(gè)新的表達(dá)式，因此我們創(chuàng)建一個(gè)子樹(shù)來(lái)對(duì)應(yīng)這個(gè)新的表達(dá)式。相反，每當(dāng)我們讀到一個(gè)右括號(hào)，我們就得結(jié)束這個(gè)表達(dá)式。另外，操作數(shù)將成為葉節(jié)點(diǎn)和他們所屬的操作符的子節(jié)點(diǎn)。最后，我們知道每個(gè)操作符都應(yīng)該有一個(gè)左子節(jié)點(diǎn)和一個(gè)右子節(jié)點(diǎn)。通過(guò)上面的分析我們定義以下四條規(guī)則：

如果當(dāng)前讀入的字符是'('，添加一個(gè)新的節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)，并下降到左子節(jié)點(diǎn)處。

如果當(dāng)前讀入的字符在列表['+', '-', '/', '*']中，將當(dāng)前節(jié)點(diǎn)的根值設(shè)置為當(dāng)前讀入的字符。添加一個(gè)新的節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)，并下降到右子節(jié)點(diǎn)處。

如果當(dāng)前讀入的字符是一個(gè)數(shù)字，將當(dāng)前節(jié)點(diǎn)的根值設(shè)置為該數(shù)字，并返回到它的父節(jié)點(diǎn)。

如果當(dāng)前讀入的字符是')'，返回當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)。

在我們編寫 Python 代碼之前，讓我們一起看一個(gè)上述的例子。我們將使用 (3+(4*5))
這個(gè)表達(dá)式。我們將表達(dá)式分解為如下的字符列表：['(', '3', '+', '(', '4', '*', '5' ,')',')']。一開(kāi)始，我們從一個(gè)僅包括一個(gè)空的根節(jié)點(diǎn)的解析樹(shù)開(kāi)始。如圖 4，該圖說(shuō)明了隨著每個(gè)新的字符被讀入后該解析樹(shù)的內(nèi)容和結(jié)構(gòu)。

圖 4：解析樹(shù)結(jié)構(gòu)的步驟圖

觀察圖 4，讓我們一步一步地過(guò)一遍：

1. 創(chuàng)建一個(gè)空的樹(shù)。
2. 讀如(作為第一個(gè)字符，根據(jù)規(guī)則 1，創(chuàng)建一個(gè)新的節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)的左子結(jié)點(diǎn)，并將當(dāng)前節(jié)點(diǎn)變?yōu)檫@個(gè)新的子節(jié)點(diǎn)。
3. 讀入3作為下一個(gè)字符。根據(jù)規(guī)則 3，將當(dāng)前節(jié)點(diǎn)的根值賦值為3然后返回當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)。
4. 讀入+作為下一個(gè)字符。根據(jù)規(guī)則 2，將當(dāng)前節(jié)點(diǎn)的根值賦值為+，然后添加一個(gè)新的節(jié)點(diǎn)作為其右子節(jié)點(diǎn)，并且將當(dāng)前節(jié)點(diǎn)變?yōu)檫@個(gè)新的子節(jié)點(diǎn)。
5. 讀入(作為下一個(gè)字符。根據(jù)規(guī)則 1，創(chuàng)建一個(gè)新的節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)的左子結(jié)點(diǎn)，并將當(dāng)前節(jié)點(diǎn)變?yōu)檫@個(gè)新的子節(jié)點(diǎn)。
6. 讀入4作為下一個(gè)字符。根據(jù)規(guī)則 3，將當(dāng)前節(jié)點(diǎn)的根值賦值為4然后返回當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)
7. 讀入*作為下一個(gè)字符。根據(jù)規(guī)則 2，將當(dāng)前節(jié)點(diǎn)的根值賦值為*，然后添加一個(gè)新的節(jié)點(diǎn)作為其右子節(jié)點(diǎn)，并且將當(dāng)前節(jié)點(diǎn)變?yōu)檫@個(gè)新的子節(jié)點(diǎn)。
8. 讀入5作為下一個(gè)字符。根據(jù)規(guī)則 3，將當(dāng)前節(jié)點(diǎn)的根值賦值為5然后返回當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)
9. 讀入)作為下一個(gè)字符。根據(jù)規(guī)則 4，我們將當(dāng)前節(jié)點(diǎn)變?yōu)楫?dāng)前節(jié)點(diǎn)*的父節(jié)點(diǎn)。
10. 讀入)作為下一個(gè)字符。根據(jù)規(guī)則 4，我們將當(dāng)前節(jié)點(diǎn)變?yōu)楫?dāng)前節(jié)點(diǎn)+的父節(jié)點(diǎn)，因?yàn)楫?dāng)前節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn)，所以我們已經(jīng)完成解析樹(shù)的構(gòu)建。

通過(guò)上面給出的例子，很明顯我們需要跟蹤當(dāng)前節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)。樹(shù)提供給我們一個(gè)獲得子節(jié)點(diǎn)的方法——通過(guò)getLeftChild和getRightChild方法，但是我們?cè)趺礃觼?lái)跟蹤一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)呢？一個(gè)簡(jiǎn)單的方法就是在我們遍歷整個(gè)樹(shù)的過(guò)程中利用棧跟蹤父節(jié)點(diǎn)。當(dāng)我們想要下降到當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)時(shí)，我們先將當(dāng)前節(jié)點(diǎn)壓入棧。當(dāng)我們想要返回當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)時(shí)，我們從棧中彈出該父節(jié)點(diǎn)。

通過(guò)上述的規(guī)則，使用棧和二叉樹(shù)來(lái)操作，我們現(xiàn)在編寫函數(shù)來(lái)創(chuàng)建解析樹(shù)。解析樹(shù)生成函數(shù)的代碼如下所示。

from pythonds.basic.stack import Stack
from pythonds.trees.binaryTree import BinaryTree

def buildParseTree(fpexp):
  fplist = fpexp.split()
  pStack = Stack()
  eTree = BinaryTree('')
  pStack.push(eTree)
  currentTree = eTree
  for i in fplist:
    if i == '(':
      currentTree.insertLeft('')
      pStack.push(currentTree)
      currentTree = currentTree.getLeftChild()
    elif i not in ['+', '-', '*', '/', ')']:
      currentTree.setRootVal(int(i))
      parent = pStack.pop()
      currentTree = parent
    elif i in ['+', '-', '*', '/']:
      currentTree.setRootVal(i)
      currentTree.insertRight('')
      pStack.push(currentTree)
      currentTree = currentTree.getRightChild()
    elif i == ')':
      currentTree = pStack.pop()
    else:
      raise ValueError
  return eTree

pt = buildParseTree("( ( 10 + 5 ) * 3 )")
pt.postorder() #defined and explained in the next section

這四條建立解析樹(shù)的規(guī)則體現(xiàn)在四個(gè)if從句，它們分別在第 11,15,19,24 行。如上面所說(shuō)的，在這幾處你都能看到規(guī)則的代碼實(shí)現(xiàn)，并需要調(diào)用一些BinaryTree和Stack的方法。這個(gè)函數(shù)中唯一的錯(cuò)誤檢查是在else語(yǔ)句中，一旦我們從列表中讀入的字符不能辨認(rèn)，我們就會(huì)報(bào)一個(gè)ValueError的異?！，F(xiàn)在我們已經(jīng)建立了一個(gè)解析樹(shù)，我們能用它來(lái)干什么呢？第一個(gè)例子，我們寫一個(gè)函數(shù)來(lái)計(jì)算解析樹(shù)的值，并返回該計(jì)算的數(shù)字結(jié)果。為了實(shí)現(xiàn)這個(gè)函數(shù)要利用樹(shù)的層級(jí)結(jié)構(gòu)。重新看一下圖 2，回想一下我們能夠?qū)⒃嫉臉?shù)替換為簡(jiǎn)化后的樹(shù)（圖 3）。這提示我們寫一個(gè)通過(guò)遞歸計(jì)算每個(gè)子樹(shù)的值來(lái)計(jì)算整個(gè)解析樹(shù)的值。

就像我們以前實(shí)現(xiàn)遞歸算法那樣，我們將從基點(diǎn)來(lái)設(shè)計(jì)遞歸計(jì)算表達(dá)式值的函數(shù)。這個(gè)遞歸算法的自然基點(diǎn)是檢查操作符是否為葉節(jié)點(diǎn)。在解析樹(shù)中，葉節(jié)點(diǎn)總是操作數(shù)。因?yàn)閿?shù)字變量如整數(shù)和浮點(diǎn)數(shù)不需要更多的操作，這個(gè)求值函數(shù)只需要簡(jiǎn)單地返回葉節(jié)點(diǎn)中存儲(chǔ)的數(shù)字就可以。使函數(shù)走向基點(diǎn)的遞歸過(guò)程就是調(diào)用求值函數(shù)計(jì)算當(dāng)前節(jié)點(diǎn)的左子樹(shù)、右子樹(shù)的值。遞歸調(diào)用使我們朝著葉節(jié)點(diǎn)，沿著樹(shù)下降。

為了將兩個(gè)遞歸調(diào)用的值整合在一起，我們只需簡(jiǎn)單地將存在父節(jié)點(diǎn)中的操作符應(yīng)用到兩個(gè)子節(jié)點(diǎn)返回的結(jié)果。在圖 3 中，我們能看到兩個(gè)子節(jié)點(diǎn)的值，分別為 10 和 3。對(duì)他們使用乘法運(yùn)算得到最終結(jié)果 30。

遞歸求值函數(shù)的代碼如 Listing1 所示，我們得到當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)、右子節(jié)點(diǎn)的參數(shù)。如果左右子節(jié)點(diǎn)的值都是 None，我們就能知道這個(gè)當(dāng)前節(jié)點(diǎn)是一個(gè)葉節(jié)點(diǎn)。這個(gè)檢查在第 7 行。如果當(dāng)前節(jié)點(diǎn)不是一個(gè)葉節(jié)點(diǎn)，查找當(dāng)前節(jié)點(diǎn)的操作符，并用到它左右孩子的返回值上。

為了實(shí)現(xiàn)這個(gè)算法，我們使用了字典，鍵值分別為'+'，'-'，'*'和'/'。存在字典里的值是 Python 的操作數(shù)模塊中的函數(shù)。這個(gè)操作數(shù)模塊為我們提供了很多常用函數(shù)的操作符。當(dāng)我們?cè)谧值渲胁檎乙粋€(gè)操作符時(shí)，相應(yīng)的操作數(shù)變量被取回。既然是函數(shù)，我們可以通過(guò)調(diào)用函數(shù)的方式來(lái)計(jì)算算式，如function(param1,param2)。所以查找opers['+'](2,2)就等價(jià)于operator.add(2,2)。

Listing 1

def evaluate(parseTree):
  opers = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv}

  leftC = parseTree.getLeftChild()
  rightC = parseTree.getRightChild()

  if leftC and rightC:
    fn = opers[parseTree.getRootVal()]
    return fn(evaluate(leftC),evaluate(rightC))
  else:
    return parseTree.getRootVal()

最后，我們將在圖 4 中創(chuàng)建的解析樹(shù)上遍歷求值。當(dāng)我們第一次調(diào)用求值函數(shù)時(shí)，我們傳遞解析樹(shù)參數(shù)parseTree，作為整個(gè)樹(shù)的根。然后我們獲得左右子樹(shù)的引用來(lái)確保它們一定存在。遞歸調(diào)用在第 9 行。我們從查看樹(shù)根中的操作符開(kāi)始，這是一個(gè)'+'。這個(gè)'+'操作符找到operator.add函數(shù)調(diào)用，且有兩個(gè)參數(shù)。通常對(duì)一個(gè) Python 函數(shù)調(diào)用而言，Python 第一件做的事情就是計(jì)算傳給函數(shù)的參數(shù)值。通過(guò)從左到右的求值過(guò)程，第一個(gè)遞歸調(diào)用從左邊開(kāi)始。在第一個(gè)遞歸調(diào)用中，求值函數(shù)用來(lái)計(jì)算左子樹(shù)。我們發(fā)現(xiàn)這個(gè)節(jié)點(diǎn)沒(méi)有左、右子樹(shù)，所以我們?cè)谝粋€(gè)葉節(jié)點(diǎn)上。當(dāng)我們?cè)谌~節(jié)點(diǎn)上時(shí)，我們僅僅是返回這個(gè)葉節(jié)點(diǎn)存儲(chǔ)的數(shù)值作為求值函數(shù)的結(jié)果。因此我們返回整數(shù) 3。

現(xiàn)在，為了頂級(jí)調(diào)用operator.add函數(shù)，我們計(jì)算好其中一個(gè)參數(shù)了，但我們還沒(méi)有完。繼續(xù)從左到右計(jì)算參數(shù)，現(xiàn)在遞歸調(diào)用求值函數(shù)用來(lái)計(jì)算根節(jié)點(diǎn)的右子節(jié)點(diǎn)。我們發(fā)現(xiàn)這個(gè)節(jié)點(diǎn)既有左節(jié)點(diǎn)又有右節(jié)點(diǎn)，所以我們查找這個(gè)節(jié)點(diǎn)中存儲(chǔ)的操作符，是'*'，然后調(diào)用這個(gè)操作數(shù)函數(shù)并將它的左右子節(jié)點(diǎn)作為函數(shù)的兩個(gè)參數(shù)。此時(shí)再對(duì)它的兩個(gè)節(jié)點(diǎn)調(diào)用函數(shù)，這時(shí)發(fā)現(xiàn)它的左右子節(jié)點(diǎn)是葉子，分別返回兩個(gè)整數(shù) 4 和 5。求出這兩個(gè)參數(shù)值后，我們返回operator.mul(4,5)的值。此時(shí)，我們已經(jīng)計(jì)算好了頂級(jí)操作符'+'的兩個(gè)操作數(shù)了，所有需要做的只是完成調(diào)用函數(shù)operator.add(3,20)即可。這個(gè)結(jié)果就是整個(gè)表達(dá)式樹(shù) (3+(4*5)) 的值，這個(gè)值是 23。

樹(shù)的遍歷

之前我們已經(jīng)了解了樹(shù)的基本功能，現(xiàn)在我們來(lái)看一些應(yīng)用模式。按照節(jié)點(diǎn)的訪問(wèn)方式不同，模式可分為 3 種。這三種方式常被用于訪問(wèn)樹(shù)的節(jié)點(diǎn)，它們之間的不同在于訪問(wèn)每個(gè)節(jié)點(diǎn)的次序不同。我們把這種對(duì)所有節(jié)點(diǎn)的訪問(wèn)稱為遍歷（traversal）。這三種遍歷分別叫做先序遍歷（preorder），中序遍歷（inorder）和后序遍歷（postorder）。我們來(lái)給出它們的詳細(xì)定義，然后舉例看看它們的應(yīng)用。

先序遍歷

在先序遍歷中，我們先訪問(wèn)根節(jié)點(diǎn)，然后遞歸使用先序遍歷訪問(wèn)左子樹(shù)，再遞歸使用先序遍歷訪問(wèn)右子樹(shù)。

中序遍歷

在中序遍歷中，我們遞歸使用中序遍歷訪問(wèn)左子樹(shù)，然后訪問(wèn)根節(jié)點(diǎn)，最后再遞歸使用中序遍歷訪問(wèn)右子樹(shù)。

后序遍歷

在后序遍歷中，我們先遞歸使用后序遍歷訪問(wèn)左子樹(shù)和右子樹(shù)，最后訪問(wèn)根節(jié)點(diǎn)。

現(xiàn)在我們用幾個(gè)例子來(lái)說(shuō)明這三種不同的遍歷。首先我們先看看先序遍歷。我們用樹(shù)來(lái)表示一本書(shū)，來(lái)看看先序遍歷的方式。書(shū)是樹(shù)的根節(jié)點(diǎn)，每一章是根節(jié)點(diǎn)的子節(jié)點(diǎn)，每一節(jié)是章節(jié)的子節(jié)點(diǎn)，每一小節(jié)是每一章節(jié)的子節(jié)點(diǎn)，以此類推。圖 5 是一本書(shū)只取了兩章的一部分。雖然遍歷的算法適用于含有任意多子樹(shù)的樹(shù)結(jié)構(gòu)，但我們目前為止只談二叉樹(shù)。

圖 5：用樹(shù)結(jié)構(gòu)來(lái)表示一本書(shū)

設(shè)想你要從頭到尾閱讀這本書(shū)。先序遍歷恰好符合這種順序。從根節(jié)點(diǎn)（書(shū)）開(kāi)始，我們按照先序遍歷的順序來(lái)閱讀。我們遞歸地先序遍歷左子樹(shù)，在這里是第一章，我們繼續(xù)遞歸地先序遍歷訪問(wèn)左子樹(shù)第一節(jié) 1.1。第一節(jié) 1.1 沒(méi)有子節(jié)點(diǎn)，我們不再遞歸下去。當(dāng)我們閱讀完 1.1 節(jié)后我們回到第一章，這時(shí)我們還需要遞歸地訪問(wèn)第一章的右子樹(shù) 1.2 節(jié)。由于我們先訪問(wèn)左子樹(shù)，我們先看 1.2.1 節(jié)，再看 1.2.2 節(jié)。當(dāng) 1.2 節(jié)讀完后，我們又回到第一章。之后我們?cè)俜祷馗?jié)點(diǎn)（書(shū)）然后按照上述步驟訪問(wèn)第二章。

由于用遞歸來(lái)編寫遍歷，先序遍歷的代碼異常的簡(jiǎn)潔優(yōu)雅。Listing 2 給出了一個(gè)二叉樹(shù)的先序遍歷的 Python 代碼。

Listing 2

def preorder(tree):
  if tree:
    print(tree.getRootVal())
    preorder(tree.getLeftChild())
    preorder(tree.getRightChild())

我們也可以把先序遍歷作為BinaryTree類中的內(nèi)置方法，這部分代碼如 Listing 3 所示。注意這一代碼從外部移到內(nèi)部所產(chǎn)生的變化。一般來(lái)說(shuō)，我們只是將tree換成了self。但是我們也要修改代碼的基點(diǎn)。內(nèi)置方法在遞歸進(jìn)行先序遍歷之前必須檢查左右子樹(shù)是否存在。

Listing 3

def preorder(self):
  print(self.key)
  if self.leftChild:
    self.leftChild.preorder()
  if self.rightChild:
    self.rightChild.preorder()

內(nèi)置和外置方法哪種更好一些呢？一般來(lái)說(shuō)preorder作為一個(gè)外置方法比較好，原因是，我們很少是單純地為了遍歷而遍歷，這個(gè)過(guò)程中總是要做點(diǎn)其他事情。事實(shí)上我們馬上就會(huì)看到后序遍歷的算法和我們之前寫的表達(dá)式樹(shù)求值的代碼很相似。只是我們接下來(lái)將按照外部函數(shù)的形式書(shū)寫遍歷的代碼。后序遍歷的代碼如 Listing 4 所示，它除了將print語(yǔ)句移到末尾之外和先序遍歷的代碼幾乎一樣。

Listing 4

def postorder(tree):
  if tree != None:
    postorder(tree.getLeftChild())
    postorder(tree.getRightChild())
    print(tree.getRootVal())

我們已經(jīng)見(jiàn)過(guò)了后序遍歷的一般應(yīng)用，也就是通過(guò)表達(dá)式樹(shù)求值。我們?cè)賮?lái)看 Listing 1，我們先求左子樹(shù)的值，再求右子樹(shù)的值，然后將它們利用根節(jié)點(diǎn)的運(yùn)算連在一起。假設(shè)我們的二叉樹(shù)只存儲(chǔ)表達(dá)式樹(shù)的數(shù)據(jù)。我們來(lái)改寫求值函數(shù)并盡量模仿后序遍歷的代碼，如 Listing 5 所示。

Listing 5

def postordereval(tree):
  opers = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv}
  res1 = None
  res2 = None
  if tree:
    res1 = postordereval(tree.getLeftChild())
    res2 = postordereval(tree.getRightChild())
    if res1 and res2:
      return opers[tree.getRootVal()](res1,res2)
    else:
      return tree.getRootVal()

我們發(fā)現(xiàn) Listing 5 的形式和 Listing 4 是一樣的，區(qū)別在于 Listing 4 中我們輸出鍵值而在 Listing 5 中我們返回鍵值。這使我們可以通過(guò)第 6 行和第 7 行將遞歸得到的值存儲(chǔ)起來(lái)。之后我們利用這些保存起來(lái)的值和第 9 行的運(yùn)算符一起運(yùn)算。

在這節(jié)的最后我們來(lái)看看中序遍歷。在中序遍歷中，我們先訪問(wèn)左子樹(shù)，之后是根節(jié)點(diǎn)，最后訪問(wèn)右子樹(shù)。 Listing 6 給出了中序遍歷的代碼。我們發(fā)現(xiàn)這三種遍歷的函數(shù)代碼只是調(diào)換了輸出語(yǔ)句的位置而不改動(dòng)遞歸語(yǔ)句。

Listing 6

def inorder(tree):
 if tree != None:
   inorder(tree.getLeftChild())
   print(tree.getRootVal())
   inorder(tree.getRightChild())

當(dāng)我們對(duì)一個(gè)解析樹(shù)作中序遍歷時(shí)，得到表達(dá)式的原來(lái)形式，沒(méi)有任何括號(hào)。我們嘗試修改中序遍歷的算法使我們得到全括號(hào)表達(dá)式。只要做如下修改：在遞歸訪問(wèn)左子樹(shù)之前輸出左括號(hào)，然后在訪問(wèn)右子樹(shù)之后輸出右括號(hào)。修改的代碼見(jiàn) Listing 7。

Listing 7

def printexp(tree):
 sVal = ""
 if tree:
   sVal = '(' + printexp(tree.getLeftChild())
   sVal = sVal + str(tree.getRootVal())
   sVal = sVal + printexp(tree.getRightChild())+')'
 return sVal

我們發(fā)現(xiàn)printexp函數(shù)對(duì)每個(gè)數(shù)字也加了括號(hào)，這些括號(hào)顯然沒(méi)必要加。

最新評(píng)論