Python の解析ツリーとツリー トラバーサルの詳細な図による説明

この記事では、Pythonの解析ツリーの実装と、プリオーダートラバーサル、インオーダートラバーサル、ポストオーダートラバーサルの3種類の例を紹介します。必要な方はぜひご覧ください。それを参照してください。

解析ツリー

ツリーの実装が完了したら、次に、いくつかの実際的な問題を解決するためにツリーを使用する方法を示す例を見てみましょう。この章では、解析木について学びます。解析ツリーは、文や数式などの実世界の構造を表すためによく使用されます。

図 1: 単文の解析木

図 1 は、単文の階​​層構造を示しています。文をツリーとして表現すると、サブツリーを使用して文内のそれぞれの独立した構造を処理できるようになります。

図 2: ((7+3)*(5−2)) の解析木を図 2 に示します。((7+3)* と同様の解析木を変換できます) (5-2) ) は解析木を表します。完全な括弧の式について見てきましたが、この式をどのように理解すればよいでしょうか?乗算は加算や減算よりも優先されることがわかっています。括弧間の関係により、乗算演算を実行する前に括弧内の加算または減算を計算する必要があります。ツリーの階層構造は、式全体の演算順序を理解するのに役立ちます。最上位の乗算演算を計算する前に、まずサブツリー内の加算演算と減算演算を計算する必要があります。左側のサブツリーへの加算の結果は 10 で、右側のサブツリーへの減算の結果は 3 です。ツリーの階層構造を利用して、子ノードの式の結果を計算したら、サブツリー全体を単一のノードに置き換えることができます。この置換ステップを適用すると、図 3 に示すような単純なツリーが得られます。

図 3: ((7+3)*(5−2)) の縮小された解析ツリー

この章の残りの部分では、解析ツリーについて詳しく見ていきます。特に:

完全な括弧の数式に基づいて対応する解析ツリーを構築する方法

解析ツリー内の数式の値を計算する方法

解析ツリーに基づいて数式を復元する方法

確立解析ツリーの 3 番目 最初のステップでは、式

string

がシンボルに分解され、リストに格納されます。ここで考慮する必要がある記号は 4 つあります: 左括弧、

演算子

、オペランドです。左括弧を読み取ると新しい式が開始されることがわかっているので、この新しい式に対応するサブツリーを作成します。代わりに、右括弧を読み取るたびに、式を終了する必要があります。さらに、オペランドはリーフ ノードになり、オペランドが属する演算子の子になります。最後に、各演算子には左の子と右の子が必要であることがわかります。上記の分析を通じて、次の 4 つのルールを定義します: 現在読み取られている文字が '(' の場合、現在のノードの左の子ノードとして新しいノードを追加し、左の子にドロップします現在読み取られている文字がリスト ['+', '-', '/', '*'] にある場合、現在のノードのルート値を現在読み取られている文字に設定します。現在のノードの右の子ノードとして新しいノードを追加し、右の子ノードに降下します。

現在読み取られている文字が数値の場合、現在のノードのルート値をその数値に設定して返します。親ノード '('，添加一个新的节点作为当前节点的左子节点，并下降到左子节点处。

如果当前读入的字符在列表['+', '-', '/', '*']中，将当前节点的根值设置为当前读入的字符。添加一个新的节点作为当前节点的右子节点，并下降到右子节点处。

如果当前读入的字符是一个数字，将当前节点的根值设置为该数字，并返回到它的父节点。

如果当前读入的字符是')'，返回当前节点的父节点。

在我们编写 Python 代码之前，让我们一起看一个上述的例子。我们将使用 (3+(4*5))
这个表达式。我们将表达式分解为如下的字符列表：['(', '3', '+', '(', '4', '*', '5' ,')',')']

現在読み取られている文字が ')' の場合、現在のノードの親ノードを返します。 🎜🎜Python コードを書く前に、上記の例を見てみましょう。 (3+(4*5))
という式を使います。次のように式を文字のリストに分解します: ['(', '3', '+', '(', '4', '*', '5' ,')',') ' ]コード>。最初に、空のルート ノードのみを含む解析ツリーから開始します。図 4 は、新しい文字が読み取られるときの解析ツリーの内容と構造を示しています。 🎜<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/013/bb64251671a2876c672cd89025c91d17-3.png?x-oss-process=image/resize,p_40" class="lazy" alt="Python の解析ツリーとツリー トラバーサルの詳細な図による説明" style="max-width:90%" style="max-width:90%" title="Python の解析ツリーとツリー トラバーサルの詳細な図による説明"><br><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/013/bb64251671a2876c672cd89025c91d17-4.png?x-oss-process=image/resize,p_40" class="lazy" alt="Python の解析ツリーとツリー トラバーサルの詳細な図による説明" style="max-width:90%" style="max-width:90%" title="Python の解析ツリーとツリー トラバーサルの詳細な図による説明"><br><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/013/8be6abb03d320946c0c53c1a6ca5a35a-5.png?x-oss-process=image/resize,p_40" class="lazy" alt="Python の解析ツリーとツリー トラバーサルの詳細な図による説明" style="max-width:90%" style="max-width:90%" title="Python の解析ツリーとツリー トラバーサルの詳細な図による説明"><br><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/013/8be6abb03d320946c0c53c1a6ca5a35a-6.png?x-oss-process=image/resize,p_40" class="lazy" alt="Python の解析ツリーとツリー トラバーサルの詳細な図による説明" style="max-width:90%" style="max-width:90%" title="Python の解析ツリーとツリー トラバーサルの詳細な図による説明"><br><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/013/d02fa57b806db1f4194a9bb866107d11-7.png?x-oss-process=image/resize,p_40" class="lazy" alt="Python の解析ツリーとツリー トラバーサルの詳細な図による説明" style="max-width:90%" style="max-width:90%" title="Python の解析ツリーとツリー トラバーサルの詳細な図による説明"><br><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/013/d02fa57b806db1f4194a9bb866107d11-8.png?x-oss-process=image/resize,p_40" class="lazy" alt="Python の解析ツリーとツリー トラバーサルの詳細な図による説明" style="max-width:90%" style="max-width:90%" title="Python の解析ツリーとツリー トラバーサルの詳細な図による説明"><br><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/013/d3d9f311383347e2bfb259e774458859-9.png?x-oss-process=image/resize,p_40" class="lazy" alt="Python の解析ツリーとツリー トラバーサルの詳細な図による説明" style="max-width:90%" style="max-width:90%" title="Python の解析ツリーとツリー トラバーサルの詳細な図による説明"><br><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/013/d3d9f311383347e2bfb259e774458859-10.png?x-oss-process=image/resize,p_40" class="lazy" alt="Python の解析ツリーとツリー トラバーサルの詳細な図による説明" style="max-width:90%" style="max-width:90%" title="Python の解析ツリーとツリー トラバーサルの詳細な図による説明"></p> <p>図 4: ツリー構造を解析するステップ図 </p> <p>図 4 を観察して、ステップごとに見てみましょう: </p> <ol class=" list-paddingleft-2"> <li><p>空のを作成する木 。 </p></li> <li><p>は次のように読み取られます(最初の文字として、ルール1に従って、現在のノードの左側の子ノードとして新しいノードを作成し、現在のノードをこの新しい子ノードに変更します。</p></li> <li><p>は次のように読み取られます) 3 次の文字として、ルール 3 に従って、現在のノードのルート値を 3 に割り当て、次に、ルール 2 に従って、現在のノードの親ノードを返します。現在のノードを 3.+ に変更し、新しいノードをその右側の子ノードとして追加し、現在のノードをこの新しい子ノード </p></li> <li><p> (次の文字として。ルール 1 に従って、現在のノードとして新しいノードを作成します)の左の子ノードで、現在のノードをこの新しい子ノードに変更します。 </p></li> <li><p> は、ルール 3 に従って、現在のノードのルート値を 4 に代入し、親ノードを返します。現在のノードの </p></li> <li><p>ルール 2 に従って、現在のノードのルート値を * に割り当て、新しいノードをその右の子ノードとして追加し、現在のノードをこれに変更します。新しい子ノード </p></li> <li><p> は次の文字として 5 を読み込みます。ルール 3 に従って、現在のノードのルート値を 5 に割り当て、現在のノードの親ノードを返します。ルール 4 に従って、現在のノードが次の文字として読み込まれる * </p></li> <li><p> の親ノードになります。ルール 4 に従って、現在のノードを現在のノードの親ノード + に変更します。これは、現在のノードには親ノードがないため、解析木の構築が完了したためです。 </p></li> <li> <p>上記の例では、現在のノードと現在のノードの親ノードを追跡する必要があることは明らかです。ツリーは、</p> メソッドを通じて子ノードを取得する方法を提供しますが、ノードの親ノードを追跡するにはどうすればよいでしょうか?これを行う簡単な方法は、ツリー全体を走査するときに親ノードのスタック トレースを使用することです。現在のノードの子に降りる場合は、まず現在のノードをスタックにプッシュします。現在のノードの親を返したい場合は、その親をスタックからポップします。 </li> <li>上記のルールを使用し、スタックとバイナリ ツリーを使用して操作することで、解析ツリーを作成するための <p>関数</p>を作成します。解析木生成関数のコードは以下のとおりです。 </li> </ol> <p><code>getLeftChild和getRightChildりー

这四条建立解析树的规则体现在四个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 中国語 Web サイトの他の関連記事を参照してください。