解析樹

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

圖 1：一個簡單句的解析樹

圖 1 顯示了一個簡單句的層級結(jié)構(gòu)。將一個句子表示為一個樹，能使我們通過利用子樹來處理句子中的每個獨立的結(jié)構(gòu)。

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

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

圖 3： ((7+3)*(5−2)) 的化簡后的解析樹

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

怎樣根據(jù)一個全括號數(shù)學(xué)表達式來建立其對應(yīng)的解析樹

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

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

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

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

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

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

如果當前讀入的字符是')'，返回當前節(jié)點的父節(jié)點。

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

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

觀察圖 4，讓我們一步一步地過一遍：

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

通過上面給出的例子，很明顯我們需要跟蹤當前節(jié)點和當前節(jié)點的父節(jié)點。樹提供給我們一個獲得子節(jié)點的方法——通過getLeftChild和getRightChild方法，但是我們怎么樣來跟蹤一個節(jié)點的父節(jié)點呢？一個簡單的方法就是在我們遍歷整個樹的過程中利用棧跟蹤父節(jié)點。當我們想要下降到當前節(jié)點的子節(jié)點時，我們先將當前節(jié)點壓入棧。當我們想要返回當前節(jié)點的父節(jié)點時，我們從棧中彈出該父節(jié)點。

通過上述的規(guī)則，使用棧和二叉樹來操作，我們現(xiàn)在編寫函數(shù)來創(chuàng)建解析樹。解析樹生成函數(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

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

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

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

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

為了實現(xiàn)這個算法，我們使用了字典，鍵值分別為'+'，'-'，'*'和'/'。存在字典里的值是 Python 的操作數(shù)模塊中的函數(shù)。這個操作數(shù)模塊為我們提供了很多常用函數(shù)的操作符。當我們在字典中查找一個操作符時，相應(yīng)的操作數(shù)變量被取回。既然是函數(shù)，我們可以通過調(diào)用函數(shù)的方式來計算算式，如function(param1,param2)。所以查找opers['+'](2,2)就等價于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)建的解析樹上遍歷求值。當我們第一次調(diào)用求值函數(shù)時，我們傳遞解析樹參數(shù)parseTree，作為整個樹的根。然后我們獲得左右子樹的引用來確保它們一定存在。遞歸調(diào)用在第 9 行。我們從查看樹根中的操作符開始，這是一個'+'。這個'+'操作符找到operator.add函數(shù)調(diào)用，且有兩個參數(shù)。通常對一個 Python 函數(shù)調(diào)用而言，Python 第一件做的事情就是計算傳給函數(shù)的參數(shù)值。通過從左到右的求值過程，第一個遞歸調(diào)用從左邊開始。在第一個遞歸調(diào)用中，求值函數(shù)用來計算左子樹。我們發(fā)現(xiàn)這個節(jié)點沒有左、右子樹，所以我們在一個葉節(jié)點上。當我們在葉節(jié)點上時，我們僅僅是返回這個葉節(jié)點存儲的數(shù)值作為求值函數(shù)的結(jié)果。因此我們返回整數(shù) 3。

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

樹的遍歷

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

先序遍歷

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

中序遍歷

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

后序遍歷

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

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

圖 5：用樹結(jié)構(gòu)來表示一本書

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

由于用遞歸來編寫遍歷，先序遍歷的代碼異常的簡潔優(yōu)雅。Listing 2 給出了一個二叉樹的先序遍歷的 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)生的變化。一般來說，我們只是將tree換成了self。但是我們也要修改代碼的基點。內(nèi)置方法在遞歸進行先序遍歷之前必須檢查左右子樹是否存在。

Listing 3

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

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

Listing 4

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

我們已經(jīng)見過了后序遍歷的一般應(yīng)用，也就是通過表達式樹求值。我們再來看 Listing 1，我們先求左子樹的值，再求右子樹的值，然后將它們利用根節(jié)點的運算連在一起。假設(shè)我們的二叉樹只存儲表達式樹的數(shù)據(jù)。我們來改寫求值函數(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 中我們返回鍵值。這使我們可以通過第 6 行和第 7 行將遞歸得到的值存儲起來。之后我們利用這些保存起來的值和第 9 行的運算符一起運算。

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

Listing 6

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

當我們對一個解析樹作中序遍歷時，得到表達式的原來形式，沒有任何括號。我們嘗試修改中序遍歷的算法使我們得到全括號表達式。只要做如下修改：在遞歸訪問左子樹之前輸出左括號，然后在訪問右子樹之后輸出右括號。修改的代碼見 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ù)對每個數(shù)字也加了括號，這些括號顯然沒必要加。