【数据结构python版-01】树形结构 (概念 + 完整代码)

1.什么是树？

树是由节点（Node）和边（Edge）组成的层级结构，有且只有一个根节点，除根节点外每个节点只有一个父节点，可以有多个子节点。

1.1核心术语

• 根节点：最顶层节点，没有父节点

• 父节点：拥有子节点的节点

• 子节点：被父节点指向的节点

• 叶子节点：没有子节点的节点

• 深度：从根到该节点的层数

• 高度：从该节点到最深叶子节点的层数

2.二叉树（每个节点最多 2 个子节点）

2.1. 定义二叉树节点

classTreeNode:
"""二叉树节点类"""
def__init__(self, val=0, left=None, right=None):
self.val=val# 节点值
self.left=left# 左子节点
self.right=right# 右子节点

2.2. 手动构建一棵二叉树

# 构建如下树结构
#        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)

3.二叉树遍历（面试必考 4 种）

遍历就是按顺序访问树中所有节点，Python 代码直接复制运行。

3.1. 前序遍历（根 → 左 → 右）

defpreorder(root):
result= []
defdfs(node):
ifnotnode:
return
result.append(node.val)  # 根
dfs(node.left)           # 左
dfs(node.right)          # 右
dfs(root)
returnresult

# 输出：[1,2,4,5,3]
print("前序遍历：", preorder(root))

3.2. 中序遍历（左 → 根 → 右）

definorder(root):
result= []
defdfs(node):
ifnotnode:
return
dfs(node.left)
result.append(node.val)
dfs(node.right)
dfs(root)
returnresult

# 输出：[4,2,5,1,3]
print("中序遍历：", inorder(root))

3.3. 后序遍历（左 → 右 → 根）

defpostorder(root):
result= []
defdfs(node):
ifnotnode:
return
dfs(node.left)
dfs(node.right)
result.append(node.val)
dfs(root)
returnresult

# 输出：[4,5,2,3,1]
print("后序遍历：", postorder(root))

3.4. 层序遍历（按层访问，BFS）

fromcollectionsimportdeque

deflevelorder(root):
ifnotroot:
return []
queue=deque([root])
result= []
whilequeue:
level= []
size=len(queue)
for_inrange(size):
node=queue.popleft()
level.append(node.val)
ifnode.left:
queue.append(node.left)
ifnode.right:
queue.append(node.right)
result.append(level)
returnresult

# 输出：[[1],[2,3],[4,5]]
print("层序遍历：", levelorder(root))

4.二叉树常用工具方法（工作直接用）

4.1. 求树的高度

deftree_height(root):
ifnotroot:
return0
left_h=tree_height(root.left)
right_h=tree_height(root.right)
returnmax(left_h, right_h) +1

print("树高度：", tree_height(root))  # 3

4.2. 统计节点总数

defcount_nodes(root):
ifnotroot:
return0
return1+count_nodes(root.left) +count_nodes(root.right)

print("节点总数：", count_nodes(root))  # 5

4.3. 判断是否为叶子节点

defis_leaf(node):
returnnodeandnotnode.leftandnotnode.right

5.通用多叉树（N-ary Tree）

适合文件目录、组织架构等场景。

classNode:
def__init__(self, val=None, children=None):
self.val=val
self.children=childrenifchildrenelse []

# 构建多叉树
root=Node(1)
root.children= [Node(2), Node(3), Node(4)]
root.children[0].children= [Node(5), Node(6)]

6.树的应用场景

1. 文件系统：Windows/Linux 目录结构

2. HTML DOM：网页标签层级

3. 数据库索引：MySQL B + 树、MongoDB 索引

4. 路由管理：前端路由、后端接口路由

5. AI 决策树：机器学习分类模型

6. 公司组织架构：层级管理

7.总结

• 树是层级结构，非线性，用途极广

• 二叉树是重点：前 / 中 / 后 / 层序遍历必须掌握

• Python 实现树非常简洁，递归是最常用写法

• 工作中树常用于层级数据、搜索、索引