Python 树和图数据结构详解

文件信息

• 文件名: 02_树和图.py
• 开发思路和开发过程:
  1. 首先介绍树的基本概念和二叉树实现
  2. 然后演示二叉树的遍历方法
  3. 接着展示二叉搜索树的实现
  4. 最后介绍图的基本概念和实现
• 代码功能: 演示树和图数据结构的实现和使用，包括二叉树、二叉搜索树和图。

代码实现

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
文件名: 02_树和图.py
开发思路和开发过程:
1. 首先介绍树的基本概念和二叉树实现
2. 然后演示二叉树的遍历方法
3. 接着展示二叉搜索树的实现
4. 最后介绍图的基本概念和实现

代码功能: 演示树和图数据结构的实现和使用，包括二叉树、二叉搜索树和图。
"""

print("=== 树和图数据结构详解 ===\n")

# 1. 树的基本概念和二叉树实现
print("1. 树的基本概念和二叉树实现:")


class TreeNode:
  """二叉树节点类"""

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

  def __str__(self):
    return str(self.val)


# 构建示例二叉树:
#       1
#      / \
#     2   3
#    / \
#   4   5

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

print("构建二叉树:")
print("       1")
print("      / \\")
print("     2   3")
print("    / \\")
print("   4   5")

# 2. 二叉树的遍历方法
print("\n2. 二叉树的遍历方法:")


def preorder_traversal(root):
  """前序遍历（根-左-右）"""
  result = []
  if root:
    result.append(root.val)
    result.extend(preorder_traversal(root.left))
    result.extend(preorder_traversal(root.right))
  return result


def inorder_traversal(root):
  """中序遍历（左-根-右）"""
  result = []
  if root:
    result.extend(inorder_traversal(root.left))
    result.append(root.val)
    result.extend(inorder_traversal(root.right))
  return result


def postorder_traversal(root):
  """后序遍历（左-右-根）"""
  result = []
  if root:
    result.extend(postorder_traversal(root.left))
    result.extend(postorder_traversal(root.right))
    result.append(root.val)
  return result


def level_order_traversal(root):
  """层序遍历（广度优先遍历）"""
  if not root:
    return []

  result = []
  queue = [root]

  while queue:
    node = queue.pop(0)
    result.append(node.val)

    if node.left:
      queue.append(node.left)
    if node.right:
      queue.append(node.right)

  return result


# 测试遍历方法
print(f"前序遍历: {preorder_traversal(root)}")  # 1, 2, 4, 5, 3
print(f"中序遍历: {inorder_traversal(root)}")  # 4, 2, 5, 1, 3
print(f"后序遍历: {postorder_traversal(root)}")  # 4, 5, 2, 3, 1
print(f"层序遍历: {level_order_traversal(root)}")  # 1, 2, 3, 4, 5

# 3. 二叉搜索树（BST）
print("\n3. 二叉搜索树（BST）:")


class BSTNode:
  """二叉搜索树节点类"""

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


class BinarySearchTree:
  """二叉搜索树类"""

  def __init__(self):
    self.root = None

  def insert(self, val):
    """插入节点"""
    if not self.root:
      self.root = BSTNode(val)
    else:
      self._insert_recursive(self.root, val)

  def _insert_recursive(self, node, val):
    """递归插入节点"""
    if val < node.val:
      if node.left is None:
        node.left = BSTNode(val)
      else:
        self._insert_recursive(node.left, val)
    elif val > node.val:
      if node.right is None:
        node.right = BSTNode(val)
      else:
        self._insert_recursive(node.right, val)
    # 如果val等于node.val，则不插入（避免重复）

  def search(self, val):
    """搜索节点"""
    return self._search_recursive(self.root, val)

  def _search_recursive(self, node, val):
    """递归搜索节点"""
    if not node or node.val == val:
      return node is not None

    if val < node.val:
      return self._search_recursive(node.left, val)
    else:
      return self._search_recursive(node.right, val)

  def inorder_traversal(self):
    """中序遍历（对于BST，结果是有序的）"""
    result = []
    self._inorder_recursive(self.root, result)
    return result

  def _inorder_recursive(self, node, result):
    """递归中序遍历"""
    if node:
      self._inorder_recursive(node.left, result)
      result.append(node.val)
      self._inorder_recursive(node.right, result)

  def delete(self, val):
    """删除节点"""
    self.root = self._delete_recursive(self.root, val)

  def _delete_recursive(self, node, val):
    """递归删除节点"""
    if not node:
      return node

    if val < node.val:
      node.left = self._delete_recursive(node.left, val)
    elif val > node.val:
      node.right = self._delete_recursive(node.right, val)
    else:
      # 找到要删除的节点
      if not node.left:
        return node.right
      elif not node.right:
        return node.left

      # 节点有两个子节点，找到右子树的最小节点替代
      min_node = self._find_min(node.right)
      node.val = min_node.val
      node.right = self._delete_recursive(node.right, min_node.val)

    return node

  def _find_min(self, node):
    """找到最小节点"""
    while node.left:
      node = node.left
    return node


# 使用二叉搜索树
bst = BinarySearchTree()
values = [5, 3, 7, 2, 4, 6, 8]
print(f"插入值: {values}")

for val in values:
  bst.insert(val)

print(f"中序遍历结果（有序）: {bst.inorder_traversal()}")

search_val = 4
found = bst.search(search_val)
print(f"搜索值 {search_val}: {'找到' if found else '未找到'}")

delete_val = 3
bst.delete(delete_val)
print(f"删除值 {delete_val} 后的中序遍历: {bst.inorder_traversal()}")

# 4. 图（Graph）
print("\n4. 图（Graph）:")


class Graph:
  """图类（使用邻接表表示）"""

  def __init__(self):
    self.vertices = {}  # 字典存储顶点和其邻居

  def add_vertex(self, vertex):
    """添加顶点"""
    if vertex not in self.vertices:
      self.vertices[vertex] = []

  def add_edge(self, vertex1, vertex2, directed=False):
    """添加边"""
    # 确保两个顶点都存在
    self.add_vertex(vertex1)
    self.add_vertex(vertex2)

    # 添加边
    self.vertices[vertex1].append(vertex2)
    if not directed:
      self.vertices[vertex2].append(vertex1)

  def get_neighbors(self, vertex):
    """获取邻居顶点"""
    return self.vertices.get(vertex, [])

  def dfs(self, start_vertex):
    """深度优先搜索"""
    visited = set()
    result = []
    self._dfs_recursive(start_vertex, visited, result)
    return result

  def _dfs_recursive(self, vertex, visited, result):
    """递归DFS"""
    visited.add(vertex)
    result.append(vertex)

    for neighbor in self.vertices[vertex]:
      if neighbor not in visited:
        self._dfs_recursive(neighbor, visited, result)

  def bfs(self, start_vertex):
    """广度优先搜索"""
    visited = set()
    queue = [start_vertex]
    result = []

    while queue:
      vertex = queue.pop(0)
      if vertex not in visited:
        visited.add(vertex)
        result.append(vertex)

        # 将未访问的邻居加入队列
        for neighbor in self.vertices[vertex]:
          if neighbor not in visited:
            queue.append(neighbor)

    return result

  def display(self):
    """显示图的结构"""
    for vertex, neighbors in self.vertices.items():
      print(f"{vertex}: {neighbors}")


# 使用图
print("创建图:")
graph = Graph()

# 添加顶点
vertices = ['A', 'B', 'C', 'D', 'E']
for vertex in vertices:
  graph.add_vertex(vertex)

# 添加边 (无向图)
edges = [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'E'), ('D', 'E')]
for edge in edges:
  graph.add_edge(edge[0], edge[1])

print("图的结构:")
graph.display()

print(f"从A开始的深度优先搜索: {graph.dfs('A')}")
print(f"从A开始的广度优先搜索: {graph.bfs('A')}")

print("\n=== 树和图数据结构详解结束 ===")

树的遍历方式

二叉树遍历方式
├── 深度优先遍历
│   ├── 前序遍历 (根-左-右)
│   ├── 中序遍历 (左-根-右)
│   └── 后序遍历 (左-右-根)
└── 广度优先遍历
    └── 层序遍历 (从上到下，从左到右)

图的遍历算法

图遍历算法
├── 深度优先搜索DFS
│   ├── 使用栈或递归
│   ├── 沿着一条路径深入
│   └── 回溯并探索其他分支
└── 广度优先搜索BFS
    ├── 使用队列
    ├── 按层次遍历
    └── 先访问相邻节点

二叉搜索树操作说明

二叉搜索树操作流程:

插入值 5:
  └── 设置为根节点

插入值 3:
  ├── 根节点(5) > 3
  └── 插入到左子树

插入值 7:
  ├── 根节点(5) < 7
  └── 插入到右子树

搜索值 3:
  ├── 从根节点开始比较
  ├── 5 > 3，搜索左子树
  └── 找到节点3

删除值 3:
  ├── 找到节点3
  └── 节点无子节点，直接删除