二叉树

Jessica Gracewell2023-09-162023-09-28

二叉树

二叉树是计算机科学中的基础数据结构，用于表示具有层级关系的数据。本文将向您展示如何使用 Python 对二叉树进行各种遍历。

1. 基础知识

二叉树遍历方法：

前序遍历：先访问根节点，再前序遍历左子树，最后前序遍历右子树。
中序遍历：先中序遍历左子树，再访问根节点，最后中序遍历右子树。
后序遍历：先后序遍历左子树，再后序遍历右子树，最后访问根节点。

注意点：

遍历的命名是基于访问根节点的顺序。
左子树总是优先于右子树

2. 代码实现

首先，我们需要定义一个二叉树节点的数据结构：


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

1. 前序遍历

递归实现：

def preorderTraversal_recursive(root):
    if not root:
        return
    print(root.val)  # 先访问根节点
    preorderTraversal_recursive(root.left)  # 然后访问左子树
    preorderTraversal_recursive(root.right)  # 最后访问右子树

2. 中序遍历 (非递归)

非递归实现：

def preorderTraversal(root):
 if not root:
     return []
 result = []
 stack = []
 while root or stack:
     while root:
         result.append(root.val)  # 先保存结果
         stack.append(root)
         root = root.left
     root = stack.pop()
     root = root.right
 return result

3. 后序遍历 (非递归)

def postorderTraversal(root):
    if not root:
        return []
    result, stack, lastVisit = [], [], None
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        node = stack[-1]
        # 根节点必须在右节点弹出之后，再弹出
        if not node.right or node.right == lastVisit:
            result.append(node.val)
            lastVisit = stack.pop()
        else:
            root = node.right
    return result

4. DFS深度优先搜索 - 从上到下

def dfs_preorder(root):
    result = []
    dfs_helper(root, result)
    return result

def dfs_helper(root, result):
    if not root:
        return
    result.append(root.val)
    dfs_helper(root.left, result)
    dfs_helper(root.right, result)

5. DFS深度优先搜索 - 分治法 (从下向上)

def divide_and_conquer(root):
    if not root:
        return []
    # 分
    left = divide_and_conquer(root.left)
    right = divide_and_conquer(root.right)
    # 治
    return [root.val] + left + right

6. BFS层次遍历

def levelOrder(root):
    result, queue = [], [root]
    while queue:
        level, size = [], len(queue)
        for i in range(size):
            node = queue.pop(0)
            if node:
                level.append(node.val)
                queue.append(node.left)
                queue.append(node.right)
        if level:
            result.append(level)
    return result