使用Python编写程序以查找两个表达式树是否相等

更多Python相关文章，请阅读：Python 教程

背景

当处理表达式时，我们通常需要比较两个表达式是否相等，但是如果表达式是以树的形式表示，就需要找到一种方法来比较两个表达式树是否相等。

例如，以下两个表达式：

(a+b)-c

(a+b)-(c+0)

以表达式树的形式表示如下：

      -
     / \
    +   c
   / \
  a   b

        -
       / \
      +   +
     / \ / \
    a  b c 0

尽管这两个表达式看起来不同，但它们都表示相同的运算，因此我们希望能够编写一个程序来比较这两个表达式树是否相等。

方法

我们可以通过遍历表达式树来比较它们之间的差异。我们从根节点开始遍历两个树，并比较它们的节点类型、值、以及它们的子节点。

首先，我们需要定义一个节点类来表示表达式树的节点：

class TreeNode:
    def __init__(self, val=''):
        self.val = val
        self.left = None
        self.right = None

然后，我们可以定义一个比较函数来递归地比较两个树的节点：

def compare_trees(node1, node2):
    # 如果节点类型不同或值不同，两个树不相等
    if type(node1) != type(node2) or node1.val != node2.val:
        return False

    # 如果节点是叶子节点，两个树相等
    if node1.left is None and node1.right is None:
        return True

    # 递归比较左右子树
    return compare_trees(node1.left, node2.left) and compare_trees(node1.right, node2.right)

最后，我们可以使用以上函数来比较两个表达式树是否相等：

# 构建第一个表达式树
root1 = TreeNode('-')
root1.left = TreeNode('+')
root1.left.left = TreeNode('a')
root1.left.right = TreeNode('b')
root1.right = TreeNode('c')

# 构建第二个表达式树
root2 = TreeNode('-')
root2.left = TreeNode('+')
root2.left.left = TreeNode('a')
root2.left.right = TreeNode('b')
root2.right = TreeNode('+')
root2.right.left = TreeNode('c')
root2.right.right = TreeNode('0')

# 比较两个表达式树是否相等
if compare_trees(root1, root2):
    print('两个表达式树相等')
else:
    print('两个表达式树不相等')

输出结果为：