使用BFS遍历创建树的镜像副本并显示的Python程序

二叉树镜像是一种简单的树遍历操作，其目的是将每个父节点的左右子树进行交换，从而生成树的镜像副本。本文将介绍如何使用BFS算法创建一个树的镜像副本，并通过Python程序进行展示。

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

读取二叉树数据

在Python程序中，我们可以通过定义类来表示一个树节点。在本例中，我们定义了一个名为Node的类，其中包含了节点值和左右子节点的信息。同时，我们将全局变量root指定为二叉树根节点。

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

root = Node(4)
root.left = Node(2)
root.right = Node(7)
root.left.left = Node(1)
root.left.right = Node(3)
root.right.left = Node(6)
root.right.right = Node(9)

以上代码创建了一棵由7个节点构成的二叉树，其中根节点的值为4。

BFS遍历生成镜像副本

接下来的目标是生成该二叉树的镜像副本。由于BFS遍历是对树进行层级遍历的过程，因此我们可以在遍历的过程中不断地对每个父节点的左右子节点进行交换操作。

具体实现如下：

def mirror(root):
    if root is None:
        return root

    queue = [root]

    while queue:
        node = queue.pop(0)

        if node.left is not None:
            queue.append(node.left)

        if node.right is not None:
            queue.append(node.right)

        node.left, node.right = node.right, node.left

    return root

mirror(root)

以上代码中，我们定义了一个名为mirror的函数，该函数接收一个根节点作为参数，遍历整个树进行子节点交换，并返回经过操作之后的根节点。

显示二叉树镜像副本

在得到二叉树镜像副本之后，我们可以通过使用Graphviz库来将树进行图形化显示。Graphviz是一种开源的图形可视化工具，可以将文本文件转换为图形格式。

首先，需要安装Graphviz库：

pip install graphviz

接下来，我们可以基于已有的Node类来创建一个名为Graph的类，该类包含了创建可视化图形的方法。

from graphviz import Digraph

class Graph:
    def __init__(self):
        self.graph = Digraph('G', filename='tree.gv', node_attr={'shape': 'record', 'height': '.1'})

    def add(self, node):
        if node is None:
            return

        self.graph.node(str(node.val), label='<f0>|<f1> %d |<f2>' % node.val)

        if node.left is not None:
            self.graph.edge(str(node.val), str(node.left.val), constraint='true')
            self.add(node.left)

        if node.right is not None:
            self.graph.edge(str(node.val), str(node.right.val), constraint='true')
            self.add(node.right)

    def view(self):
        self.graph.view()

以上代码创建了一个名为Graph的类，该类中包含了用于创建可视化图形的add()和view()方法。add()方法接收一个节点作为输入，并将它添加到可视化图形中；view()方法用于显示可视化图形，可直接运行。

接下来，我们通过如下代码创建一个Graph实例并对其调用add()方法：

graph = Graph()
graph.add(root)
graph.view()

当程序运行完成后，会自动跳出一个名为“tree.gv”的图形窗口，展示出生成的树形图。

可以发现，经过镜像副本操作后，左右子树已经交换位置，树形结构变为了原来的镜像。

完整代码

from graphviz import Digraph

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

class Graph:
    def __init__(self):
        self.graph = Digraph('G', filename='tree.gv', node_attr={'shape': 'record', 'height': '.1'})

    def add(self, node):
        if node is None:
            return

        self.graph.node(str(node.val), label='<f0>|<f1> %d |<f2>' % node.val)

        if node.left is not None:
            self.graph.edge(str(node.val), str(node.left.val), constraint='true')
            self.add(node.left)

        if node.right is not None:
            self.graph.edge(str(node.val), str(node.right.val), constraint='true')
            self.add(node.right)

    def view(self):
        self.graph.view()

def mirror(root):
    if root is None:
        return root

    queue = [root]

    while queue:
        node = queue.pop(0)

        if node.left is not None:
            queue.append(node.left)

        if node.right is not None:
            queue.append(node.right)

        node.left, node.right = node.right, node.left

    return root

root = Node(4)
root.left = Node(2)
root.right = Node(7)
root.left.left = Node(1)
root.left.right = Node(3)
root.right.left = Node(6)
root.right.right = Node(9)

mirror(root)

graph = Graph()
graph.add(root)
graph.view()