圖文詳解Python解析樹及樹的遍歷

本篇是給大家介紹的Python實作解析樹以及實作二元樹的三種遍歷，先序遍歷，中序遍歷，後序遍歷的例子，非常的詳細，有需要的小夥伴可以參考下。

解析樹

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

圖 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：解析樹結構的步驟圖

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

2. 建立一個空的樹。

3. 讀如(作為第一個字符，根據規則1，創建一個新的節點作為當前節點的左子結點，並將當前節點變為這個新的子節點。

   #讀入+作為下一個字元。

4. 讀入(作為下一個字元。根據規則1，建立一個新的節點作為目前節點的左子結點，並將目前節點變成這個新的子節點。

5. 讀入4作為下一個字元。 ##讀入*作為下一個字元。

6. #讀入5作為下一個字元。讀入)作為下一個字元。根據規則 4，我們將目前節點變成目前節點+的父節點，因為目前節點沒有父節點，所以我們已經完成解析樹的建置。

7. 透過上面給出的例子，很明顯我們需要追蹤目前節點和目前節點的父節點。樹提供給我們一個獲得子節點的方法－透過

   getLeftChild

   和
getRightChild
8. 方法，但是我們怎麼樣來追蹤一個節點的父節點呢？一個簡單的方法就是在我們遍歷整個樹的過程中利用堆疊追蹤父節點。當我們想要下降到目前節點的子節點時，我們先將目前節點壓入堆疊。當我們想要返回目前節點的父節點時，我們會從堆疊中彈出該父節點。
   透過上述的規則，使用堆疊和二元樹來操作，我們現在寫
函數
9. 來建立解析樹。解析樹產生函數的程式碼如下所示。

10. 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.truep}

  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.truep}
  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函数对每个数字也加了括号，这些括号显然没必要加。

以上是圖文詳解Python解析樹及樹的遍歷的詳細內容。更多資訊請關注PHP中文網其他相關文章！