解析樹

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

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

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

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

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

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

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

怎樣根據一個全括號數學表達式來建立其對應的解析樹

怎樣計算解析樹中數學表達式的值

怎樣根據一個解析樹還原數學表達式

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

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

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

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

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

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

圖 4：解析樹結構的步驟圖

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

1. 創建一個空的樹。
2. 讀如(作為第一個字符，根據規則 1，創建一個新的節點作為當前節點的左子結點，并將當前節點變為這個新的子節點。
3. 讀入3作為下一個字符。根據規則 3，將當前節點的根值賦值為3然后返回當前節點的父節點。
4. 讀入+作為下一個字符。根據規則 2，將當前節點的根值賦值為+，然后添加一個新的節點作為其右子節點，并且將當前節點變為這個新的子節點。
5. 讀入(作為下一個字符。根據規則 1，創建一個新的節點作為當前節點的左子結點，并將當前節點變為這個新的子節點。
6. 讀入4作為下一個字符。根據規則 3，將當前節點的根值賦值為4然后返回當前節點的父節點
7. 讀入*作為下一個字符。根據規則 2，將當前節點的根值賦值為*，然后添加一個新的節點作為其右子節點，并且將當前節點變為這個新的子節點。
8. 讀入5作為下一個字符。根據規則 3，將當前節點的根值賦值為5然后返回當前節點的父節點
9. 讀入)作為下一個字符。根據規則 4，我們將當前節點變為當前節點*的父節點。
10. 讀入)作為下一個字符。根據規則 4，我們將當前節點變為當前節點+的父節點，因為當前節點沒有父節點，所以我們已經完成解析樹的構建。

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

通過上述的規則，使用棧和二叉樹來操作，我們現在編寫函數來創建解析樹。解析樹生成函數的代碼如下所示。

            
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
          

這四條建立解析樹的規則體現在四個 if 從句，它們分別在第 11,15,19,24 行。如上面所說的，在這幾處你都能看到規則的代碼實現，并需要調用一些 BinaryTree 和 Stack 的方法。這個函數中唯一的錯誤檢查是在 else 語句中，一旦我們從列表中讀入的字符不能辨認，我們就會報一個 ValueError 的異常。現在我們已經建立了一個解析樹，我們能用它來干什么呢？第一個例子，我們寫一個函數來計算解析樹的值，并返回該計算的數字結果。為了實現這個函數要利用樹的層級結構。重新看一下圖 2，回想一下我們能夠將原始的樹替換為簡化后的樹（圖 3）。這提示我們寫一個通過遞歸計算每個子樹的值來計算整個解析樹的值。

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

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

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

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

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

樹的遍歷

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

先序遍歷

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

中序遍歷

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

后序遍歷

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

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

圖 5：用樹結構來表示一本書

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

由于用遞歸來編寫遍歷，先序遍歷的代碼異常的簡潔優雅。Listing 2 給出了一個二叉樹的先序遍歷的 Python 代碼。

Listing 2

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

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

Listing 3

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

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

Listing 4

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

我們已經見過了后序遍歷的一般應用，也就是通過表達式樹求值。我們再來看 Listing 1，我們先求左子樹的值，再求右子樹的值，然后將它們利用根節點的運算連在一起。假設我們的二叉樹只存儲表達式樹的數據。我們來改寫求值函數并盡量模仿后序遍歷的代碼，如 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()
          

我們發現 Listing 5 的形式和 Listing 4 是一樣的，區別在于 Listing 4 中我們輸出鍵值而在 Listing 5 中我們返回鍵值。這使我們可以通過第 6 行和第 7 行將遞歸得到的值存儲起來。之后我們利用這些保存起來的值和第 9 行的運算符一起運算。

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

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
          

我們發現 printexp 函數對每個數字也加了括號，這些括號顯然沒必要加。