用Python实现二叉树、二叉树非递归遍历及绘制的例子

下面为你详细讲解Python实现二叉树、二叉树非递归遍历及绘制的攻略。

实现二叉树

1. 定义节点类

二叉树是由多个节点组成的，因此我们需要先定义一个节点类，代码如下：

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

在节点类中，每个节点包含一个值val，以及左子节点left和右子节点right。同时，我们也提供了一个构造函数，可以用来初始化一个节点。

2. 构建二叉树

构建二叉树的方法有很多，这里介绍一种常用的方式——通过列表递归地创建二叉树。

具体实现思路是：
* 若当前列表为空，则返回None；
* 取列表的第一个值作为根节点的值，创建一个根节点；
* 将根节点的左子树设为列表中下标从1开始的所有元素构成的列表，即左子节点为列表的第二个元素（如果存在），右子节点为列表的第三个元素（如果存在）；
* 递归地对左子树和右子树进行构建；
* 返回当前二叉树的根节点。

代码如下：

def createTree(nums):
    if not nums:
        return None
    root = TreeNode(nums[0])
    left_nums = [num for num in nums[1:] if num < root.val]
    right_nums = [num for num in nums[1:] if num > root.val]
    root.left = createTree(left_nums)
    root.right = createTree(right_nums)
    return root

3. 遍历二叉树

二叉树的遍历方法有三种：前序遍历、中序遍历和后序遍历。下面分别介绍如何在二叉树上进行这三种遍历。

前序遍历

前序遍历的实现方法是：先访问根节点，再递归遍历左子树，最后递归遍历右子树。

代码如下：

def preorderTraversal(root):
    if not root:
        return []
    res = []
    stack = [root]
    while stack:
        cur = stack.pop()
        res.append(cur.val)
        if cur.right:
            stack.append(cur.right)
        if cur.left:
            stack.append(cur.left)
    return res

中序遍历

中序遍历的实现方法是：先递归遍历左子树，再访问根节点，最后递归遍历右子树。

代码如下：

def inorderTraversal(root):
    if not root:
        return []
    res = []
    stack = []
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        res.append(root.val)
        root = root.right
    return res

后序遍历

后序遍历的实现方法是：先递归遍历左子树，再递归遍历右子树，最后访问根节点。

代码如下：

def postorderTraversal(root):
    if not root:
        return []
    res = []
    stack = [root]
    while stack:
        cur = stack.pop()
        res.append(cur.val)
        if cur.left:
            stack.append(cur.left)
        if cur.right:
            stack.append(cur.right)
    return res[::-1]

绘制二叉树

Python中有很多工具可以用来绘制二叉树，比如graphviz、matplotlib等。这里以graphviz为例介绍如何绘制二叉树。

安装graphviz

首先，需要安装graphviz。在Windows系统中，可以在graphviz官网下载对应的安装包，并进行安装。安装完成后，将graphviz加入系统的PATH环境变量中，以便于之后命令行调用。

在Linux系统中，可以使用类似于下面的命令进行安装：

sudo apt-get install graphviz

安装graphviz插件

在Python中，可以使用graphviz的Python插件pydot和graphviz来将二叉树绘制出来。首先需要安装这两个插件：

pip install pydot
pip install graphviz

绘制二叉树代码示例

下面给出一个二叉树绘制的示例代码：

import os
from graphviz import Digraph


def draw_tree(root, filename):
    dot = Digraph(comment="Binary Tree")
    tree2graph(root, dot)
    filepath = os.path.join(os.getcwd(), filename)
    dot.render(filepath, view=True)


def tree2graph(node, dot):
    if node.left:
        dot.edge(str(node.val), str(node.left.val))
        tree2graph(node.left, dot)

    if node.right:
        dot.edge(str(node.val), str(node.right.val))
        tree2graph(node.right, dot)

其中，draw_tree函数用于绘制二叉树，tree2graph函数用于将二叉树转换为graphviz的图形对象（Digraph）。最后将绘制后的图像保存为指定的文件，保存路径为当前工作目录。

至此，Python实现二叉树、二叉树非递归遍历及绘制的攻略介绍完毕。