Python 구문 분석 트리 및 트리 순회에 대한 자세한 그래픽 설명

이 글은 파싱 트리 구현과 이진 트리의 세 가지 순회(선순서 순회, 순차 순회, 후순 순회)를 구현하는 Python 예제를 소개하기 위한 것입니다. 필요한 경우 파트너가 이를 참조하여 도움을 드릴 수 있습니다.

파싱 트리

트리 구현을 완료한 후 이제 트리를 사용하여 몇 가지 실제 문제를 해결하는 방법을 보여주는 예제를 살펴보겠습니다. 이번 장에서는 파싱 트리(Parse Tree)에 대해 공부합니다. 구문 분석 트리는 종종 문장이나 수학적 표현과 같은 실제 구조를 나타내는 데 사용됩니다.

그림 1: 간단한 문장의 구문 분석 트리

그림 1은 간단한 문장의 계층 구조를 보여줍니다. 문장을 트리로 표현하면 하위 트리를 사용하여 문장의 각 독립적인 구조를 처리할 수 있습니다.

그림 2: ((7+3)*(5−2))의 구문 분석 트리 ​​

그림 2에서 볼 수 있듯이, ((7+3)*(5−2)) ​​와 같은 수학 표현식은 구문 분석 트리를 나타냅니다. 지금까지 대괄호 표현식을 살펴보았는데, 이 표현식을 어떻게 이해할까요? 우리는 곱셈이 덧셈이나 뺄셈보다 우선순위가 높다는 것을 알고 있습니다. 괄호 사이의 관계로 인해 곱셈 연산을 수행하기 전에 괄호 안의 덧셈이나 뺄셈을 계산해야 합니다. 트리의 계층 구조는 전체 표현식의 작동 순서를 이해하는 데 도움이 됩니다. 최상위 곱셈 연산을 계산하기 전에 먼저 하위 트리에서 덧셈과 뺄셈 연산을 계산해야 합니다. 왼쪽 하위 트리의 덧셈 결과는 10, 오른쪽 하위 트리의 뺄셈 결과는 3입니다. 트리의 계층 구조를 활용하여 하위 노드의 표현식 결과를 계산한 후 전체 하위 트리를 단일 노드로 대체할 수 있습니다. 이 대체 단계를 적용하면 그림 3과 같은 간단한 트리를 얻을 수 있습니다.

그림 3: ((7+3)*(5−2))의 축소된 구문 분석 트리 ​​

이 장의 나머지 부분에서는 구문 분석 트리를 더 자세히 살펴보겠습니다. 특히:

대괄호 수식을 기반으로 해당 구문 분석 트리를 구축하는 방법

분석 트리에서 수식의 값을 계산하는 방법

방법 트리 축소 수식

을 기반으로 한 구문 분석 구문 분석 트리를 설정하는 첫 번째 단계는 표현식

문자열

을 기호로 분해하여 목록에 저장하는 것입니다. 여기서 고려해야 할 네 가지 기호는 왼쪽 괄호, 연산자 및 피연산자입니다. 우리는 왼쪽 괄호를 읽을 때 새로운 표현식을 시작한다는 것을 알고 있으므로 이 새로운 표현식에 대응하는 하위 트리를 만듭니다. 대신, 닫는 괄호를 읽을 때마다 표현식을 종료해야 합니다. 또한 피연산자는 자신이 속한 연산자의 리프 노드 및 하위 노드가 됩니다. 마지막으로, 우리는 각 연산자가 왼쪽 자식과 오른쪽 자식을 가져야 한다는 것을 알고 있습니다. 위의 분석을 통해 다음과 같은 4가지 규칙을 정의합니다. 현재 읽은 문자가

이면 현재 노드의 왼쪽 자식 노드로 새 노드를 추가하고 왼쪽 자식 노드에 놓습니다.

'('현재 읽은 문자가 목록에 있으면

현재 노드의 루트 값을 현재 읽은 문자로 설정합니다. 현재 노드의 오른쪽 자식으로 새 노드를 추가하고 오른쪽 자식으로 내려갑니다.

['+', '-', '/', '*']현재 읽은 문자가 숫자인 경우 현재 노드의 루트 값을 해당 숫자로 설정하고 상위 노드로 반환합니다.

현재 읽은 문자가 ')'인 경우 현재 노드의 상위 노드를 반환합니다.

파이썬 코드를 작성하기 전에 위의 예를 살펴보겠습니다. (3+(4*5))

라는 표현을 사용하겠습니다. 표현식을

과 같은 문자 목록으로 나눕니다. 처음에는 빈 루트 노드만 포함하는 구문 분석 트리로 시작합니다. 그림 4는 각각의 새로운 문자를 읽을 때 구문 분석 트리의 내용과 구조를 보여줍니다.

그림 4: 트리 구조 구문 분석 단계 다이어그램

그림 4를 살펴보고 단계별로 살펴보겠습니다.

1. 빈 트리를 만듭니다.

2. 은 다음과 같이 읽습니다(첫 번째 문자로 규칙 1에 따라 현재 노드의 왼쪽 자식 노드로 새 노드를 생성하고 현재 노드를 이 새 자식 노드로 변경). .

3. 은 규칙 3에 따라 3을 읽고 현재 노드의 상위 노드를 반환합니다. +를 다음 문자로 사용합니다. 규칙 2에 따라 현재 노드의 루트 값을 +에 할당한 다음 새 노드를 오른쪽 하위 노드로 추가하고 현재 노드를 이 새 하위 노드로 변경합니다.

은 (를 다음 문자로 읽습니다. 규칙 1에 따라 현재 노드의 왼쪽 자식 노드로 새 노드를 생성하고 현재 노드를 이 새 자식 노드로 변경합니다.
은 4를 다음 문자로 읽습니다. 규칙 3에 따라 현재 노드의 루트 값을 4에 할당하고 현재 노드의 상위 노드를 반환합니다.
읽기 * 규칙 2에 따라 현재 노드의 루트 값을 *에 할당한 다음 새 노드를 오른쪽 하위 노드로 추가하고 현재 노드를 이 새 하위 노드로 변경합니다.
6. 은 5를 다음 문자로 읽습니다. 규칙 3에 따라 현재 노드의 루트 값을 5에 할당하고 현재 노드의 상위 노드를

7. Read in)으로 반환합니다. 다음 문자. 규칙 4에 따라 현재 노드를 현재 노드의 상위 노드로 변경합니다. *.다음 문자로 읽어옵니다. 규칙 4에 따르면 현재 노드를 현재 노드 +의 부모 노드로 변경하는데, 현재 노드에는 부모 노드가 없기 때문에 파싱 트리의 구축이 완료되었다.

8. 위에 주어진 예를 보면 현재 노드와 현재 노드의 상위 노드를 추적해야 한다는 것이 분명합니다. 트리는

   및

   메서드를 통해 하위 노드를 얻는 방법을 제공하지만 노드의 상위 노드를 어떻게 추적합니까? 이를 수행하는 간단한 방법은 전체 트리를 탐색하면서 상위 노드의 스택 추적을 사용하는 것입니다. 현재 노드의 하위 노드로 내려오려면 먼저 현재 노드를 스택에 푸시합니다. 현재 노드의 부모를 반환하려면 해당 부모를 스택에서 팝합니다.
9. 위의 규칙을 사용하고 스택과 바이너리 트리를 사용하여 작동함으로써 이제

   함수

   를 작성하여 구문 분석 트리를 만듭니다. 파스 트리 생성 기능에 대한 코드는 다음과 같습니다.

10. 아아앙

这四条建立解析树的规则体现在四个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 중국어 웹사이트의 기타 관련 기사를 참조하세요!