二叉树 python

二叉树是一种常见的数据结构，它由节点和边组成，每个节点最多有两个子节点，左子节点和右子节点。在 Python 中，我们可以使用类来表示二叉树，如下所示：

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

其中，`val` 表示节点的值，`left` 表示左子节点，`right` 表示右子节点。如果一个节点没有子节点，则对应的 `left` 或 `right` 值为 `None`。

下面是一个实例，构建一棵二叉树：

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

这棵树的结构如下所示：

     1
   /   \
  2     3
 / \
4   5

我们可以通过递归的方式进行二叉树的遍历，包括前序遍历、中序遍历和后序遍历。下面是一个实现前序遍历的例子：

def preorder_traversal(root):
    if not root:
        return
    print(root.val)
    preorder_traversal(root.left)
    preorder_traversal(root.right)

这个函数的作用是先输出当前节点的值，然后遍历左子树，最后遍历右子树。我们可以使用这个函数来遍历上面构建的二叉树：

preorder_traversal(root)

输出结果为：

1
2
4
5
3

中序遍历和后序遍历的实现方式类似，只需要改变遍历顺序即可。