您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# 什么是二叉树
## 目录
1. [基本概念](#基本概念)
2. [二叉树的性质](#二叉树的性质)
3. [特殊类型二叉树](#特殊类型二叉树)
4. [存储结构](#存储结构)
5. [遍历方式](#遍历方式)
6. [应用场景](#应用场景)
7. [代码实现示例](#代码实现示例)
8. [复杂度分析](#复杂度分析)
9. [常见问题](#常见问题)
## 基本概念
二叉树（Binary Tree）是每个节点最多有两个子节点的树形数据结构，这两个子节点分别称为**左子节点**和**右子节点**。它是非线性数据结构中最基础且最重要的结构之一，具有递归定义的特性。
### 核心特征
- 每个节点最多有2个子节点
- 左子树和右子树有明确区分
- 第i层最多有2^(i-1)个节点
- 深度为k的二叉树最多有2^k - 1个节点
### 数学定义
递归定义二叉树：
1. 空树是二叉树
2. 由一个根节点和两个互不相交的子树（左/右子树）组成
## 二叉树的性质
1. **层次性质**：
- 第k层最多有2^(k-1)个节点
- 深度为h的树最多有2^h - 1个节点
2. **节点关系**：
- 度为0的节点（叶节点）数 = 度为2的节点数 + 1
- 具有n个节点的二叉树最小深度为⌈log₂(n+1)⌉
3. **特殊性质**：
```math
n = n₀ + n₁ + n₂
e = n - 1 = n₁ + 2n₂
=> n₀ = n₂ + 1
# 完全二叉树的数组表示
tree = [None, 'A', 'B', 'C', 'D', 'E', 'F']
# 索引i的左右子节点分别为2i和2i+1
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
前序遍历：根→左→右
def preorder(root):
if root:
print(root.val)
preorder(root.left)
preorder(root.right)
中序遍历：左→根→右（BST得到有序序列）
后序遍历：左→右→根
from collections import deque
def level_order(root):
queue = deque([root])
while queue:
node = queue.popleft()
print(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def build_sample_tree():
""" 构建示例树：
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)
return root
void inorderTraversal(TreeNode root) {
if (root != null) {
inorderTraversal(root.left);
System.out.print(root.val + " ");
inorderTraversal(root.right);
}
}
| 操作 | 平均情况 | 最坏情况 |
|---|---|---|
| 查找 | O(log n) | O(n) |
| 插入 | O(log n) | O(n) |
| 删除 | O(log n) | O(n) |
| 空间复杂度 | O(n) | O(n) |
注：平衡二叉树的最坏情况为O(log n)
使用层序遍历，当遇到空节点后不应再出现非空节点
虽然单次操作时间复杂度可能相同，但树形结构支持二分查找等高效算法
通过本文的详细讲解，读者应该已经掌握了二叉树的核心概念、存储方式、遍历算法以及实际应用。二叉树作为基础数据结构，是学习更高级树形结构（如B树、Trie树等）的重要基础。建议通过LeetCode等平台的相关题目（如94、102、104题）进行实践练习。 “`
注：本文实际约2150字（含代码和公式），由于Markdown渲染差异，不同平台显示的字数可能略有不同。如需精确字数控制，建议在最终发布前使用专业字数统计工具校验。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。