Explication graphique détaillée de l'arbre d'analyse Python et de la traversée de l'arbre

Cet article a pour but de vous présenter des exemples Python d'implémentation d'arbres d'analyse et d'implémentation de trois parcours d'arbres binaires, un parcours pré-ordre, un parcours dans l'ordre et un parcours post-commande. Il est très détaillé. et pourra vous aider si nécessaire. Les partenaires pourront s'y référer.

Analyser l'arbre

Après avoir terminé la mise en œuvre de l'arbre, regardons maintenant un exemple pour vous montrer comment utiliser l'arbre pour résoudre quelques problèmes pratiques. Dans ce chapitre, nous étudions les arbres d’analyse. Les arbres d'analyse sont souvent utilisés pour représenter des structures du monde réel, telles que des phrases ou des expressions mathématiques.

Figure 1 : Arbre d'analyse d'une phrase simple

La figure 1 montre la structure hiérarchique d'une phrase simple. Représenter une phrase sous forme d'arbre nous permet de gérer chaque structure indépendante de la phrase en utilisant des sous-arbres.

Figure 2 : L'arbre d'analyse de ((7 3)*(5−2)) ​​​​

Comme le montre la figure 2, nous pouvons convertir un similaire L'expression mathématique dans ((7 3)*(5−2)) ​​​​​​représente un arbre d'analyse. Nous avons examiné les expressions entre crochets, alors comment comprendre cette expression ? Nous savons que la multiplication a une priorité plus élevée que l’addition ou la soustraction. En raison de la relation entre les parenthèses, nous devons calculer l’addition ou la soustraction entre parenthèses avant d’effectuer l’opération de multiplication. La structure hiérarchique de l'arborescence nous aide à comprendre l'ordre des opérations de l'expression entière. Avant de calculer l’opération de multiplication la plus élevée, nous devons d’abord calculer les opérations d’addition et de soustraction dans le sous-arbre. Le résultat de l’addition au sous-arbre de gauche est 10 et le résultat de la soustraction au sous-arbre de droite est 3. En profitant de la structure hiérarchique de l'arbre, une fois que nous avons calculé le résultat d'une expression dans un nœud enfant, nous pouvons remplacer l'ensemble du sous-arbre par un seul nœud. En appliquant cette étape de substitution, nous obtenons un arbre simple comme le montre la figure 3.

Figure 3 : Arbre d'analyse réduit de ((7 3)*(5−2)) ​​​​

Dans la suite de ce chapitre, nous Les arbres d'analyse seront étudiés plus en détail. En particulier :

Comment construire l'arbre d'analyse correspondant basé sur une expression mathématique entre parenthèses

Comment calculer la valeur de l'expression mathématique dans l'arbre d'analyse

Comment analyse basée sur une expression mathématique de réduction d'arbre

La première étape dans l'établissement d'un arbre d'analyse consiste à décomposer l'expression

chaîne

en symboles et à les enregistrer dans une liste. Il y a quatre symboles que nous devons considérer ici : la parenthèse gauche, l'opérateur et l'opérande. Nous savons que lorsque nous lisons une parenthèse gauche, nous démarrons une nouvelle expression, nous créons donc un sous-arbre pour correspondre à cette nouvelle expression. Au lieu de cela, chaque fois que nous lisons une parenthèse fermante, nous devons terminer l’expression. De plus, les opérandes deviendront des nœuds feuilles et des enfants des opérateurs auxquels ils appartiennent. Enfin, nous savons que chaque opérateur doit avoir un enfant gauche et un enfant droit. Grâce à l'analyse ci-dessus, nous définissons les quatre règles suivantes : Si le caractère actuellement lu est

, ajoutez un nouveau nœud comme nœud enfant gauche du nœud actuel et déposez-le sur le nœud enfant gauche.

'('Si le caractère actuellement lu est dans la liste

, définissez la valeur racine du nœud actuel sur le caractère actuellement lu. Ajoute un nouveau nœud en tant qu'enfant droit du nœud actuel et descend jusqu'au bon enfant.

[' ', '-', '/', '*']Si le caractère actuellement lu est un nombre, définissez la valeur racine du nœud actuel sur ce nombre et renvoyez-le à son nœud parent.

Si le caractère actuellement lu est ')', renvoie le nœud parent du nœud actuel.

Avant d'écrire du code Python, regardons un exemple ci-dessus. Nous utiliserons l'expression (3 (4*5))

. Nous divisons l'expression en une liste de caractères comme ceci :

. Initialement, nous commençons avec un arbre d'analyse qui contient uniquement un nœud racine vide. La figure 4 illustre le contenu et la structure de l'arbre d'analyse à mesure que chaque nouveau caractère est lu.

Figure 4 : Diagramme des étapes d'analyse de la structure arborescente

Observez la figure 4, parcourons-la étape par étape :

1. Créez un arbre vide.

2. est lu comme (comme premier caractère, selon la règle 1, créer un nouveau nœud en tant que nœud enfant gauche du nœud actuel et changer le nœud actuel en ce nouveau nœud enfant .

3. lit 3 comme caractère suivant, selon la règle 3, attribuez la valeur racine du nœud actuel à 3 et renvoie le nœud parent du nœud actuel >

   . lire comme le caractère suivant. Selon la règle 2, attribuez la valeur racine du nœud actuel, puis ajoutez un nouveau nœud comme nœud enfant droit et remplacez le nœud actuel par ce nouveau nœud enfant >
4. .

   Lire (comme caractère suivant. Selon la règle 1, créez un nouveau nœud comme nœud enfant gauche du nœud actuel et changez le nœud actuel en ce nouveau nœud enfant.

5. lit 4 comme caractère suivant. Selon la règle 3, attribuez la valeur racine du nœud actuel à 4 et renvoie le nœud parent du nœud actuel

6. Lisez * comme prochain. Selon la règle 2, attribuez la valeur racine du nœud actuel à *, puis ajoutez un nouveau nœud comme nœud enfant droit et remplacez le nœud actuel par ce nouveau nœud enfant 🎜>

lit 5. comme caractère suivant. Selon la règle 3, attribuez la valeur racine du nœud actuel à 5 ​​et renvoyez le nœud parent du nœud actuel
lit. ) comme caractère suivant. . Selon la règle 4, nous changeons le nœud actuel en nœud parent du nœud actuel *
et lisons) comme caractère suivant. Selon la règle 4, nous changeons le nœud actuel en nœud parent du nœud actuel , car le nœud actuel n'a pas de nœud parent, nous avons donc terminé la construction de l'arbre d'analyse.
Avec l'exemple donné ci-dessus, il est évident que nous devons garder une trace du nœud actuel et du nœud parent du nœud actuel. Les arbres nous fournissent un moyen d'obtenir des nœuds enfants - via les méthodes
10. et

    , mais comment suivre le nœud parent d'un nœud ? Un moyen simple de procéder consiste à utiliser une trace de pile du nœud parent lorsque nous parcourons l'ensemble de l'arborescence. Lorsque nous voulons descendre vers un enfant du nœud actuel, nous poussons d'abord le nœud actuel sur la pile. Lorsque nous voulons renvoyer le parent du nœud actuel, nous retirons ce parent de la pile.

En utilisant les règles ci-dessus et en utilisant des piles et des arbres binaires pour fonctionner, nous écrivons maintenant la

fonction

pour créer un arbre d'analyse. Le code de la fonction de génération d’arbre d’analyse est le suivant. getLeftChildgetRightChild

这四条建立解析树的规则体现在四个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函数对每个数字也加了括号，这些括号显然没必要加。

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!