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.树的应用场景
文件系统：Windows/Linux 目录结构
HTML DOM：网页标签层级
数据库索引：MySQL B + 树、MongoDB 索引
路由管理：前端路由、后端接口路由
AI 决策树：机器学习分类模型
公司组织架构：层级管理
7.总结
